Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
BPM (Beat Per Minute) とは、楽曲の速さを表す数値です。
Kenkoooo さんは、BPM が 140 以上 170 未満の中速曲が好きです。 また、BPM を何回か 2 で割ると 140 以上 170 未満となる曲も好きです。 このどちらにも当てはまらない曲は好きではありません。
例えば、Kenkoooo さんは BPM が 679 (2 で 2 回割ると 169.75) の曲は好きですが、 BPM が 680 (2 で 2 回割ると 170) の曲は好きではありません。
ここに 1 枚の CD があり、D - C 曲の楽曲が収録されています。 これらの曲の BPM はそれぞれ C, C+1, C+2, ..., D-2, D-1 です。 このうち、Kenkoooo さんが好きな曲は何曲あるでしょうか？
制約
- 140 ≤ C < D ≤ 10^{15}
- C, D は整数である。
入力
入力は以下の形式で標準入力から与えられる。
C D
出力
CD に収録された曲のうち Kenkoooo さんが好きな曲の数を出力せよ。
入力例 1
160 300
出力例 1
30
この例では、CD には BPM 160, 161, 162, ..., 298, 299 の 140 曲が収録されています。 このうち、Kenkoooo さんが好きな曲は BPM 160, 161, 162, ..., 168, 169 の 10 曲と BPM 280, 281, 282, ..., 298, 299 の 20 曲、合計 30 曲です。
入力例 2
340 560
出力例 2
0
Kenkoooo さんの好みに合わないアルバムです。
入力例 3
140 1000000000000000
出力例 3
263882790666210
Kenkoooo さんの世界の CD の容量に上限はなく、収録曲数が 32 bit 整数型に収まらないこともあります。
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
N 個の薬品が横一列に並んでいます。それぞれの薬品には 効用 という整数値が定まっており、左から i 番目の薬品の現在の効用は b_i です。これらの値は正とは限りません。
Kenkoooo さんは、横長の特殊な装置を用いて次の操作を何回でも行えます（行わなくても構いません）。
- 連続して並ぶ K 個の薬品を選ぶ。選ばれた薬品の効用はすべて 0 となる。
なお、薬品を移動させることは危険を伴うためできません。
その後、Kenkoooo さんは N 個の薬品すべてを飲み干します。その前に、N 個の薬品の効用の和を可能な限り大きくしておきたいです。操作後のこの和の最大値を求めてください。
制約
- 1 ≤ K ≤ N ≤ 2 × 10^5
- -10^9 ≤ b_i ≤ 10^9
- 入力中の値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N K b_1 : b_N
出力
操作後の N 個の薬品の効用の和の最大値を出力せよ。
入力例 1
9 3 -1 -2 -3 4 5 -6 -7 -8 -9
出力例 1
9
最適な手順の例を示します。
- 1 回目の操作: 左から 1, 2, 3 番目の薬品を選ぶ。
- 2 回目の操作: 左から 6, 7, 8 番目の薬品を選ぶ。
- 3 回目の操作: 左から 7, 8, 9 番目の薬品を選ぶ。
このとき、9 個の薬品の効用の和は 0 + 0 + 0 + 4 + 5 + 0 + 0 + 0 + 0 = 9 となります。
入力例 2
5 4 -1 -1 5 -1 -1
出力例 2
1
何もせずこのまま薬品を飲み干すべきです。
入力例 3
9 5 30 -20 40 60 -90 50 -40 10 70
出力例 3
120
入力例 4
10 1 1000000000 -1000000000 1000000000 -1000000000 1000000000 -1000000000 1000000000 -1000000000 1000000000 -1000000000
出力例 4
5000000000
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
N 頂点の無向グラフであって、以下の条件をすべて満たすものの個数を 10^9 + 7 で割った余りを求めてください。
- N 個の頂点には 1 から N までの番号が振られている。
- グラフは自己辺や多重辺を持たない（連結である必要はない）。
- すべての辺の長さを 1 とすると、頂点 1, 2 間の最短距離は D である。
注記
二つのグラフ G_1, G_2 は、以下が満たされる場合に異なるとみなされ、満たされない場合に同一とみなされます。
- ある整数の組 (i, j) (1 ≤ i < j ≤ N) が存在し、頂点 i, j を直接結ぶ辺が G_1, G_2 のうち一方のみに存在する。
制約
- 1 ≤ D < N ≤ 30
- N, D は整数である。
入力
入力は以下の形式で標準入力から与えられる。
N D
出力
条件をすべて満たすグラフの個数を 10^9 + 7 で割った余りを出力せよ。
入力例 1
4 3
出力例 1
2
条件を満たすグラフは下図の 2 通りです。
入力例 2
4 2
出力例 2
14
条件を満たすグラフは下図の 14 通りです。
入力例 3
30 15
出力例 3
313862829
mod (10^9 + 7) にご注意ください。
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
N 頂点 0 辺の無向グラフが与えられます。以下のクエリを Q 個処理して下さい。
- addクエリ(type = 1, u, v): u と v の間に辺が無ければ辺を貼る。
- completeクエリ(type = 2, u, v = 0): 全ての頂点対 a, b について以下を行う, u, a, b がすべて連結で，かつ a, b 間に辺がない場合，a, b の間に辺を貼る。
- checkクエリ(type = 3, u, v): u, v が与えられる。u と v を直接結ぶ辺がある場合
Yes、そうでない場合Noを出力する。
制約
- 2 \leq N \leq 100,000
- 1 \leq Q \leq 200,000
- type_i = 1, 2, 3
- 1 \leq u_i \leq N
- add, checkクエリにおいて 1 \leq v_i \leq N かつ u_i \neq v_i
- completeクエリにおいて v_i = 0
- 入力される値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N Q type_1 u_1 v_1 type_2 u_2 v_2 : type_Q u_Q v_Q
出力
各checkクエリに対し、YesかNoを出力してください。
入力例 1
3 6 1 1 2 1 2 3 3 1 2 3 1 3 2 1 0 3 1 3
出力例 1
Yes No Yes
1, 2 つ目のクエリで(1, 2), (2, 3)に辺が張られます。 そして、5 つ目のクエリで(1, 3) 間に辺が張られます。
入力例 2
3 6 2 3 0 3 1 3 1 3 1 2 3 0 1 1 2 3 2 1
出力例 2
No Yes
入力例 3
8 20 1 3 6 2 6 0 2 2 0 2 7 0 1 7 3 3 2 6 1 4 2 3 3 7 1 2 6 2 4 0 2 2 0 3 3 1 2 8 0 2 8 0 1 8 2 2 7 0 3 5 4 1 4 2 3 5 7 3 2 3
出力例 3
No Yes No No No Yes
Time Limit: 6 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
英小文字からなる長さNの文字列が M 個与えられ、 S_1, S_2, ..., S_M とします。以下のクエリを Q 個処理して下さい。
- swapクエリ(type = 1, x, y, l, r): S_x[l..r] とS_y[l..r] をswapする。
- hashクエリ(type = 2, x, y = 0, l, r): h(S_x[l..r]) を求め，出力する。
なお、
- 文字列 S に対し、S[l..r] を、Sのl文字目からr文字目まで(両端含む)の部分文字列を表すこととします。
- 英小文字 a に対し、ord(a) = 1, ord(b) = 2, ..., ord(z) = 26 とします。
- 文字列 S = c_1c_2...c_k に対し、\sum_{i=1..k} {\rm ord}(c_i)(1,000,000)^{i-1} を 10^9 + 7 で割ったあまりを h(S) とします。
制約
- 1 \leq N \leq 200,000
- 1 \leq M \leq 20
- S_i は英小文字のみからなる
- 1 \leq Q \leq 200,000
- type_i = 1, 2
- 1 \leq x_i \leq M
- swapクエリのとき, x_i < y_i \leq M
- hashクエリのとき、y_i = 0
- 1 \leq l_i \leq r_i \leq N
入力
入力は以下の形式で標準入力から与えられる。
N M S_1 S_2 : S_M Q type_1 x_1 y_1 l_1 r_1 type_2 x_2 y_2 l_2 r_2 : type_Q x_Q y_Q l_Q r_Q
出力
各hashクエリに対し、h(S_x[l..r]) を出力してください。
入力例 1
5 2 abcde fghij 8 2 1 0 2 3 2 2 0 1 5 1 1 2 2 2 2 1 0 2 3 2 2 0 1 5 1 1 2 1 3 2 1 0 2 3 2 2 0 1 5
出力例 1
3000002 496944447 3000007 491944447 8000002 496979442
それぞれ、
- h("bc") = 3000002
- h("fghij") = 496944447
- h("gc") = 3000007
- h("fbhij") = 491944447
- h("bh") = 8000002
- h("agcij") = 496979442
を出力しています。
入力例 2
7 3 pzocuwt ghqsktw ogvyhak 13 2 1 0 1 2 1 1 2 5 6 1 1 3 3 6 1 2 3 4 5 1 2 3 5 6 1 1 2 1 6 1 1 2 5 6 2 2 0 5 5 2 1 0 2 3 1 2 3 1 4 1 1 2 2 7 2 3 0 1 6 2 3 0 1 4
出力例 2
26000016 21 17000008 556958241 25847241