A - ぐっすり

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋くんはこれから N 日間の睡眠の予定を建てることにしました。 i 日目には t_i 分だけ寝る予定です。

また、高橋くんは連続した 3 日間の睡眠時間の合計が K 分を下回ると、その連続した3日目に睡眠不足になります。 厳密に言うと、 x≧3 のとき x-2 日目、 x-1 日目、 x 日目の睡眠時間の合計が K を下回ると、 x 日目に睡眠不足になります。 合計がちょうど Kになった場合は睡眠不足になりません。

あらかじめ高橋くんの睡眠の予定を与えるので、高橋くんが睡眠不足になるかどうかを求めてください。 もし睡眠不足になるならば、何日目に睡眠不足になるか求めてください。 答えが複数通り考えられるならば、最初に睡眠不足になる日を求めてください。

高橋くんは 1 日目と 2 日目には睡眠不足にならないものとします。 また、高橋くんは昼寝しかしないので、睡眠により日をまたぐことは考えなくて良いです。

入力

入力は以下の形式で標準入力から与えられる

N K
t_1
t_2
:
t_N
  • 1 行目には高橋くんが予定を建てた日数 N(3 ≦ N ≦ 10^5) と睡眠不足の基準を表す整数 K(0 ≦ K ≦ 4,320) が空白区切りで与えられる。
  • 2 行目からの N 行のうち i 行目には i 日目に予定している睡眠時間を表す整数 t_i(0 ≦ t_i ≦ 1,440) が与えられる。

出力

もし高橋くんがN日の間に睡眠不足にならないならば -1 を 1 行に出力せよ。 もしなるならば、最初になる日を 1 行に出力せよ。

入力例1

5 1080
300
420
420
180
360

出力例1

4

2, 3, 4 日目の睡眠時間の合計は 1020 分となっており K を下回っています。 この日以前に睡眠不足になっている日はありません。 よって高橋くんは 4 日目に初めて睡眠不足になります。

入力例2

5 180
60
60
60
60
60

出力例2

-1

3 日間の睡眠時間の合計がちょうど K の場合は睡眠不足にならないことに注意してください。

入力例3

5 4230
360
360
360
360
360

出力例3

3
B - 山のデータ

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋くんは、東西方向に並んだ地点の高さをまとめたデータを持っている。西から i (1 ≦ i ≦ N) 番目の地点の高さは h_i である。このデータの中には同じ高さの地点は存在しなかった。

高橋くんはデータに対し、以下のように「山」および「山の大きさ」を定義することにした。

3 つの整数の組 (s,t,u) (1 ≦ s ≦ t ≦ u ≦ N) について、以下の条件を満たすとき、この組は山を表しているとする。

  • 山の西側に関する条件 : s ≦ i ≦ t-1 を満たす任意の整数 i に関して、h_i ＜ h_{i+1}が成立する。
  • 山の東側に関する条件 : t ≦ i ≦ u-1 を満たす任意の整数 i に関して、h_i ＞ h_{i+1}が成立する。

このような条件を満たす整数組 (s,t,u) に関して、山の大きさは、u-s+1 で定義される。

高橋くんは、データ中にある山の中で、山の大きさの最大値がいくらになるのかを調査することにした。

山の大きさとして考えられる最大値を求めるプログラムを作成せよ。

入力

入力は以下の形式で標準入力から与えられる。

N
h_1
h_2
:
h_N
  • 1 行目には、データの要素数を表す整数 N (1 ≦ N ≦ 3×10^5) が与えられる。
  • 2 行目から N 行では、地点の高さを表す整数が与えられる。N 行のうち i 行目では、整数 h_i (1 ≦ h_i ≦ 10^9) が与えられる。
  • 1 ≦ i ＜ j ≦ N を満たす任意の整数 i,j に関して、h_i ≠ h_j である。

部分点

この問題には部分点が設定されている。

  • N ≦ 20 を満たすデータセットに正解した場合は、30 点が与えられる。
  • 追加制約のないデータセットに正解した場合は、上記とは別に 70 点が与えられる。

出力

山の大きさとして考えられる最大値を 1 行に出力せよ。出力の末尾には改行を入れること。

入力例1

6
4
5
1
6
9
7

出力例1

4

山のデータは、[4, 5, 1, 6, 9, 7] です。このうち、整数組 (3, 5, 6) を考えてみると、

  • 1(=h_3) ＜ 6(=h_4) ＜ 9(=h_5) より山の西側に関する条件は成立。
  • 9(=h_5) ＞ 7(=h_6) より山の東側に関する条件は成立。
以上より整数組 (3, 5, 6) は大きさ 6 - 3 + 1 = 4 の山を表します。大きさ 5 以上の山は存在しないため、4 が正解となります。

入力例2

7
90
70
50
30
20
10
5

出力例2

7
C - 偶然ジェネレータ

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋くんはゲーム会社に勤めている。

高橋くんは上司から、乱数表を作るよう指示を受けた。

乱数表は 0,1 のいずれかでのみ構成される長さ N の数列で、そのうちいくつかの要素には、どちらの値が入るかが決まっている。

ところで高橋くんは、上司から「あまり分布が偏った乱数表は作らないでほしい」という注文も受けている。具体的には、乱数表からどのような連続する部分列を取り出しても、その部分列に含まれる 0 の個数と 1 の個数の差が K 以下でなければならない。

高橋くんはこのような条件を満たす乱数表が全部でいくつあるのか数えることにした。

入力

入力は以下の形式で標準入力から与えられる。

N K
S
  • 1 行目には、2 つの整数 N (1 ≦ N ≦ 300) と K (1 ≦ K ≦ N) が空白区切りで書かれている。これは、乱数表の長さが N で、許容される最大の差が K であることを表す。
  • 2 行目には、乱数表に関する情報を表す長さ N の文字列 S が与えられる。文字列 S は 0,1,? のみで構成されており、左から i (1 ≦ i ≦ N) 文字目は乱数表の左から i 番目の要素についての情報を表す。
    • 左から i 文字目が 0 なら、乱数表の i 番目の要素が 0 でなければならないことを表す。
    • 左から i 文字目が 1 なら、乱数表の i 番目の要素が 1 でなければならないことを表す。
    • 左から i 文字目が ? なら、乱数表の i 番目の要素が 0 と 1 のどちらでも良いことを表す。

部分点

この問題には部分点が設定されている。

  • N ≦ 12 を満たすデータセットに正解した場合は、10 点が与えられる。
  • K ≦ 5 を満たすデータセットに正解した場合は、上記とは別に 30 点が与えられる。
  • 追加制約のないデータセットに正解した場合は、上記とは別に 60 点が与えられる。

出力

考えられる乱数表の総数を 1,000,000,007(= 1000000007) で割った余りを 1 行に出力せよ。出力の末尾には改行を入れること。

入力例1

9 4
?011?1110

出力例1

2

乱数表として [0, 0, 1, 1, 0, 1, 1, 1, 0] を考えます。この乱数表では、0 の個数と 1 の個数の差として考えられる最大値は、左から 3 番目の要素を先頭、8 番目の要素を末尾とした長さ 6 の数列 [1, 1, 0, 1, 1, 1] における差 4(= 5 - 1) です。

他にも乱数表 [1, 0, 1, 1, 0, 1, 1, 1, 0] が条件を満たします。

入力例2

9 3
?011?1110

出力例2

0

条件を満たす乱数表は存在しません。

入力例3

9 1
???1?????

出力例3

1

入力例4

12 5
???0??1??11?

出力例4

172
D - 偶数メートル

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋くんの住む国には N 個の街があります。それぞれ 1 から N の整数で番号付けされています。 しかし、これらの街の間を移動する手段がまだありません。 そこで国が補助金を出して、異なる 2 つの街を結ぶ道路を、いくつか敷設することになりました。 各道路は個別の長さを持っています。 敷設される道路は結んだ 2 つの国のどちらからでも、もう一方の国に移動することが出来ます。つまり双方向に移動できる道路です。

ところで、高橋くんは偶数が大好きです。 高橋くんは道路を使って、たとえそれが遠回りになろうとも、同じ道を何度通ろうとも、移動距離の合計が偶数メートルになるように移動しようとします。 また、高橋くんは中途半端なことが嫌いなので、道の途中で来た道を引き返すことはしません。

高橋君はときどき、2 つの街を指定して、その間を偶数メートルで移動できるかどうかあなたに質問します。 先述の通り、今は道路を増やしている最中なので、質問のタイミングによっては新しく敷設された道路の影響で、偶数メートルで移動できるかどうかが変わり得るに注意してください。

なお、街の中での移動は移動距離の合計に含まないものとします。

道路の敷設と、高橋くんの質問の情報を時系列順に与えるので、高橋くんの質問に答えるプログラムを作成してください。

入力

入力は以下の形式で標準入力から与えられる

N Q
w_1 x_1 y_1 z_1
w_2 x_2 y_2 z_2
:
w_Q x_Q y_Q z_Q
  • 1 行目には高橋くんの住む国にある街の個数 N (1 ≦ N ≦ 10^5) と与えられる情報の個数 Q (1 ≦ Q ≦ 10^5) が空白区切りで与えられる。
  • 2 行目からの Q 行のうち i 行目には i 番目の情報を表す整数 w_i, x_i, y_i, z_i が空白区切りに与えられる。各変数は以下の制約を満たす。
    • 1 ≦ w_i ≦ 2
    • 1 ≦ x_i, y_i ≦ N
    • x_i ≠ y_i
    • 1 ≦ z_i ≦ 10^5
  • w_i = 1 のとき、街 x_i と街 y_i の間に長さ z_i メートルの道路を敷くことを表す。
  • w_i = 2 のとき、高橋くんが 街 x_i と 街 y_i を偶数メートルで移動できるか質問したことを表す。このとき z_i は常に 1 である。
  • 同じ 2 つの街に複数本の道が敷かれることがある。
  • 高橋くんが質問した時点では、それ以前の入力の全ての道路の敷設が完了されているものとする。

部分点

この問題には部分点が設定されている。

  • 1 ≦ N ≦ 3,000 , 1 ≦ Q ≦ 3,000 を満たすデータセットに正解した場合は 30 点が与えられる。
  • 1 ≦ N ≦ 10^5 , 1 ≦ Q ≦ 10^5 を満たすデータセットに正解した場合はさらに 70 点が与えられる。合計で100点となる。

出力

出力は複数行からなる。 高橋くんが質問するたびに、高橋くんが街 x_i と街 y_i の間を偶数メートルで移動できるならば YES 、移動できないならば NO と1行に出力せよ。

入力例1

5 9
1 1 2 3
1 1 3 2
1 3 5 5
2 1 5 1
2 2 5 1
1 2 4 4
1 1 4 6
2 1 5 1
2 3 5 1

出力例1

NO
YES
YES
YES

各質問時点での街と道路の様子は以下のようになります。 左が 1, 2 つ目の質問の時の様子で、右が 3, 4 つ目の質問の時の様子です。

2 つ目の質問に対しては 2, 1, 3, 5 という順に道路を進むと移動距離の合計が 10 になります。

3 つ目の質問に対しては 1, 4, 2, 1, 3, 5 という順に道路を進むと移動距離の合計が 20 になります。

4 つ目の質問に対しては 3, 1, 2, 4, 1, 3, 5 という順に道路を進むと移動距離の合計が 22 になります。

入力例2

5 7
1 1 2 3
1 2 4 4
1 5 3 1
2 1 3 1
2 5 3 1
1 3 1 2
2 3 4 1

出力例2

NO
NO
NO

1 つ目の質問の時点では、そもそも街 1 から街 3 に行く方法がありません。よって答えは NO になります。

入力例3

3 6
1 1 2 1
1 1 3 3
1 2 3 2
1 2 1 2
2 1 3 1
2 2 3 1

出力例3

YES
YES

同じ 2 つの街に複数本の道路が敷設され得ることに注意してください。