Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
東西に細長い土地があります。 この土地は、N 個の区画が東西に並んだ形をしており、西から i 番目の区画は区画 i と呼ばれます。
それぞれの区画には地下資源があることがわかっており、区画 i の資源埋蔵量は A_i です。
1 以上 N 以下のそれぞれの整数 k について、次の問題の答えを求めてください。
- 連続する k 個の区画を選んだとき、それらの区画の資源埋蔵量の総和として考えられる最大値はいくらか。
制約
- 1 \leq N \leq 3000
- 1 \leq A_i \leq 10^9
- 入力される値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \cdots A_N
出力
N 行出力せよ。 k 行目には、連続する k 個の区画の資源埋蔵量の総和の最大値を出力せよ。
入力例 1
4 4 1 3 3
出力例 1
4 6 8 11
k=1 のとき、区画 1 を選ぶと資源埋蔵量の総和は 4 となり、これが最大です。
k=2 のとき、区画 3,4 を選ぶと資源埋蔵量の総和は 3+3=6 となり、これが最大です。
k=3 のとき、区画 1,2,3 を選ぶと資源埋蔵量の総和は 4+1+3=8 となり、これが最大です。
k=4 のとき、区画 1,2,3,4 を選ぶと資源埋蔵量の総和は 4+1+3+3=11 となり、これが最大です。
入力例 2
5 10 20 30 40 50
出力例 2
50 90 120 140 150
入力例 3
10 61049214 115057849 356385814 932678664 505961980 877482753 476308661 571830644 210047210 873430114
出力例 3
932678664 1438640644 2316123397 2792432058 3364262702 3720648516 4447740026 4804125840 4919183689 4980232903
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
長さ N の整数列 A、長さ M の整数列 B、整数 K が与えられます。 値 X,Y を以下のように定義します。
- X= \sum_{i=1}^N A_i \times K^{N-i} = A_1 \times K^{N-1} + A_2 \times K^{N-2} + ... + A_N \times K^0
- Y= \sum_{i=1}^M B_i \times K^{M-i} = B_1 \times K^{M-1} + B_2 \times K^{M-2} + ... + B_M \times K^0
X と Y のどちらが小さいかを求めてください。
制約
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 2 \leq K \leq 10^9
- 0 \leq A_i \leq K-1
- 1 \leq A_1
- 0 \leq B_i \leq K-1
- 1 \leq B_1
- 入力される値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N M K A_1 A_2 \cdots A_N B_1 B_2 \cdots B_M
出力
X < Y のときは X
、X > Y のときは Y
、X = Y のときは Same
と出力せよ。
入力例 1
3 3 10 1 2 3 1 2 4
出力例 1
X
X=123,Y=124 であり、 X<Y であるので X
と出力します。
入力例 2
4 3 13 1 2 3 4 4 5 6
出力例 2
Y
入力例 3
4 4 2 1 1 0 1 1 1 0 1
出力例 3
Same
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
縦 H 行、横 W 列のマス目があります。 上から i 行目、左から j 列目のマスをマス (i,j) と呼ぶことにします。
それぞれのマスには、1 つの駒が置いてあります。 ショウさんは、このうち K 個の駒をマス目上から取り除きました。 i 番目の取り除いた駒は、マス (R_i,C_i) にあった駒です。
今からショウさんは、次の操作を 0 回以上行います。
- 駒を 1 つ選び、その駒が現在置かれているマスから、隣接する別のマスへと移動させる。 このとき、移動先のマスに別の駒があっても構わない。 なお、2 つのマスが隣接するとは、2 つのマスが辺を共有することを意味する。
ショウさんの目的は、マス目上のすべての駒が同じマスに置いてあるようにすることです。 ショウさんが目的を達成するために必要な最小の操作回数を求めてください。
制約
- 1 \leq H \leq 10^5
- 1 \leq W \leq 10^5
- 0 \leq K \leq \min(10^5,H \times W -1)
- 1\leq R_i \leq H
- 1\leq C_i \leq W
- (R_i,C_i) \neq (R_j,C_j) (i\neq j)
- 入力される値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
H W K R_1 C_1 R_2 C_2 \vdots R_K C_K
出力
マス目上のすべての駒が同じマスに置いてあるようにするために必要な最小の操作回数を出力せよ。
入力例 1
2 3 3 1 2 2 1 2 2
出力例 1
3
操作を行う前の段階で駒が置かれているマスは、マス (1,1), (1,3), (2,3) の 3 つです。 次のように 3 回操作することで、すべての駒が同じマスに置かれます。
- マス (1,1) に置いてある駒をマス (1,2) へ移動させる。
- マス (1,2) に置いてある駒をマス (1,3) へ移動させる。
- マス (2,3) に置いてある駒をマス (1,3) へ移動させる。
2 回以下の操作で目的を達成することはできないので、3 が答えとなります。
入力例 2
5 5 10 2 2 2 5 1 3 2 4 2 3 1 5 2 1 1 4 1 2 1 1
出力例 2
28
入力例 3
100000 100000 0
出力例 3
500000000000000
入力例 4
2 2 3 1 2 2 1 2 2
出力例 4
0
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
N 本の竹があり、1 から N までの番号がつけられています。 時刻 0 において、すべての竹の高さは 0 です。 それぞれの竹は、時刻が 1 経過するごとに高さが 1 増えます。
ナオさんが竹を伐採するイベントが M 回予定されています。 i 番目のイベントは時刻 T_i に行われ、このイベントでは番号が L_i 以上 R_i 以下の竹をすべて伐採します。 ナオさんが高さ x の竹を伐採するとき、彼女は x 点を得ます。 また、伐採された竹は高さが 0 になりますが、その竹はこれ以降も伸び続けます。
M 回のイベントでナオさんが得る得点の総和を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq T_1 < T_2 < \cdots < T_M \leq 10^9
- 1 \leq L_i \leq R_i \leq N
- 入力される値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N M T_1 L_1 R_1 T_2 L_2 R_2 \vdots T_M L_M R_M
出力
M 回のイベントでナオさんが得る得点の総和を出力せよ。
入力例 1
4 2 2 1 2 5 2 3
出力例 1
12
1 番目のイベントが行われる時刻 2 では、竹の高さはそれぞれ 2,2,2,2 です。 竹 1 と 2 を伐採すると、竹の高さはそれぞれ 0,0,2,2 になります。
2 番目のイベントが行われる時刻 5 では、竹の高さはそれぞれ 3,3,5,5 です。 竹 2 と 3 を伐採すると、竹の高さはそれぞれ 3,0,0,5 になります。
2 回のイベントで伐採した竹の高さはそれぞれ 2,2,3,5 なので、その総和である 12 が答えです。
入力例 2
10 5 8 1 4 11 6 7 20 1 1 31 9 9 36 1 1
出力例 2
113
入力例 3
10 10 76724435 3 4 118633459 1 2 288866156 6 9 470883673 6 10 521545097 2 4 827053186 1 1 856004743 2 4 873331881 1 1 909855542 6 10 916091889 8 9
出力例 3
8003096514
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
1 から N までの番号のついた N 個のブロックがあります。 また、整数 K が与えられます。
魔法使いのコウさんは、魔法を唱えてこれらのブロックを消し去ろうとしています。 彼は、以下のような魔法を唱えることができます。
- 1 \leq l \leq r \leq N, r-l \geq K を満たす整数の組 (l,r) を選び、 番号が l 以上 r 以下の(まだ消されていない)ブロックをすべて消す。
つまり、彼が唱えられる魔法は (l,rの選び方の総数) =(N-K) \times (N-K+1) / 2 種類あります。
それぞれの魔法を唱えるか唱えないかの組み合わせは全部で 2^{(N-K) \times (N-K+1) / 2} 通りあります。 コウさんは、このうち最終的にブロックをすべて消し去ることのできる組み合わせが何通りあるかに興味を持っています。
コウさんのために、最終的にブロックをすべて消し去ることのできる組み合わせが何通りあるかを求めてください。 ただし、答えは非常に大きくなることがあるので、答えを 10^9+7 で割ったあまりを求めてください。
制約
- 1 \leq N \leq 5000
- 0 \leq K \leq N-1
- 入力される値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N K
出力
最終的にブロックをすべて消し去ることのできる組み合わせの個数を 10^9+7 で割ったあまりを出力せよ。
入力例 1
3 1
出力例 1
5
コウさんが唱えられる魔法は、(l,r)=(1,2),(2,3),(1,3) の 3 種類です。 最終的にブロックをすべて消し去ることのできる組み合わせは、以下の 5 通りです。
- (1,2) と (2,3)
- (1,2) と (1,3)
- (1,2) と (2,3) と (1,3)
- (2,3) と (1,3)
- (1,3)
入力例 2
10 5
出力例 2
30784
入力例 3
5000 250
出力例 3
844653816
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 900 点
問題文
2 次元平面上に、1 から N までの番号のついた N 個の国があります。 国 i は座標 (X_i,Y_i) にあります。
それぞれの国には航空会社があります。 国 i の航空会社は、X_j \leq X_i かつ Y_j \leq Y_i を満たすすべての j (j \neq i) について、 国 j との間に直通便を運航しています。 この直通便は双方向です。 つまり、国 i の航空会社の飛行機を利用して、国 i から国 j へ移動することも、 国 j から国 i へ移動することも可能です。 国 i の航空会社の飛行機は、1 度利用するたびに C_i 円の料金がかかります。
ケンさんは現在国 S にいて、国 T まで移動したいです。 飛行機を利用して移動するとき、飛行機の料金の合計の最小値を求めてください。
制約
- 2 \leq N \leq 10^5
- 0 \leq X_i \leq 10^9
- 0 \leq Y_i \leq 10^9
- 1 \leq C_i \leq 10^9
- (X_i,Y_i) \neq (X_j,Y_j) (i \neq j)
- 1 \leq S \leq N
- 1 \leq T \leq N
- S \neq T
- 飛行機のみを利用して国 S から国 T まで移動することができる。
- 入力される値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N S T X_1 Y_1 C_1 X_2 Y_2 C_2 \vdots X_N Y_N C_N
出力
国 S から国 T へ移動する際の、飛行機の料金の合計の最小値を出力せよ。
入力例 1
4 1 4 0 1 3 1 1 6 0 0 4 1 0 8
出力例 1
11
この例では、直通便は以下の 5 種類が存在します。
- 国 1 と国 3 を結ぶ直通便。国 1 の航空会社が運航しており、一度利用するのに 3 円かかる。
- 国 1 と国 2 を結ぶ直通便。国 2 の航空会社が運航しており、一度利用するのに 6 円かかる。
- 国 2 と国 3 を結ぶ直通便。国 2 の航空会社が運航しており、一度利用するのに 6 円かかる。
- 国 2 と国 4 を結ぶ直通便。国 2 の航空会社が運航しており、一度利用するのに 6 円かかる。
- 国 3 と国 4 を結ぶ直通便。国 4 の航空会社が運航しており、一度利用するのに 8 円かかる。
国 1 から国 4 へ移動する場合は、国 1→3→4 と移動すると料金の合計が 11 円になり、これが最小です。
入力例 2
9 3 6 2 3 9 1 4 2 0 4 16 1 3 77 3 3 12 4 0 96 4 2 41 2 1 17 3 4 45
出力例 2
104
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 1200 点
問題文
N 頂点の木があり、頂点には 1 から N までの番号が、辺には 1 から N-1 までの番号がついています。 辺 i は頂点 A_i と B_i を結ぶ辺です。
1 から M までの番号のついた M 人の人が、今からこの木の上を移動します。 人 i は、頂点 V_i から出発し、以下の操作をちょうど L_i 回行います。
- 今いる頂点に繋がっている辺を自由に一つ選び、その辺を通って隣の頂点へ移動する。 このとき、通った辺の番号が x なら、C_x 点を得る。
すべての i について、人 i が L_i 回の操作で得られる得点の総和の最大値を求めてください。
制約
- 2 \leq N \leq 10^5
- 1 \leq A_i < B_i \leq N
- 1 \leq C_i \leq 10^9
- 1 \leq M \leq 10^5
- 1 \leq V_i \leq N
- 1 \leq L_i \leq 10^9
- 入力で与えられるグラフは木である。
- 入力される値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N A_1 B_1 C_1 A_2 B_2 C_2 \vdots A_{N-1} B_{N-1} C_{N-1} M V_1 L_1 V_2 L_2 \vdots V_M L_M
出力
M 行出力せよ。 i 行目には、人 i が L_i 回の操作で得られる得点の総和の最大値を出力せよ。
入力例 1
5 1 2 5 2 3 2 3 4 4 3 5 2 3 5 3 2 1 5 5
出力例 1
10 5 19
人 1 は、次のように行動すると 3 回の操作で得られる得点の総和を最大化できます。
- 辺 4 を使って移動し、頂点 5 から頂点 3 に移動する。2 点を得る。
- 辺 3 を使って移動し、頂点 3 から頂点 4 に移動する。4 点を得る。
- 辺 3 を使って移動し、頂点 4 から頂点 3 に移動する。4 点を得る。
人 2 は、次のように行動すると 1 回の操作で得られる得点の総和を最大化できます。
- 辺 1 を使って移動し、頂点 2 から頂点 1 に移動する。5 点を得る。
人 3 は、次のように行動すると 5 回の操作で得られる得点の総和を最大化できます。
- 辺 4 を使って移動し、頂点 5 から頂点 3 に移動する。2 点を得る。
- 辺 2 を使って移動し、頂点 3 から頂点 2 に移動する。2 点を得る。
- 辺 1 を使って移動し、頂点 2 から頂点 1 に移動する。5 点を得る。
- 辺 1 を使って移動し、頂点 1 から頂点 2 に移動する。5 点を得る。
- 辺 1 を使って移動し、頂点 2 から頂点 1 に移動する。5 点を得る。
入力例 2
12 9 10 13 5 8 78 1 7 96 3 5 56 7 9 99 4 12 36 7 12 45 7 11 37 8 9 69 2 7 60 6 7 71 10 9 7 8 1 1 2 11 18 1 18 3 5 9 17 9 13 9 16 5 5
出力例 2
693 78 195 1720 1779 401 1683 1287 1584 444
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 1500 点
問題文
今日から数えて i 日目のことを Day i と呼ぶことにします。 例えば、今日は Day 1、明日は Day 2 です。
マコさんは、1 から N までの番号がついた N 個の宿題を課されています。 彼女は、Day 1 から始めて 1 日あたり 1 個の宿題を選んで終わらせます。 宿題 i を Day A_i またはそれ以前に終わらせると、彼女は X_i 点を得ます。 また、Day (A_i+1) またはそれ以降に終わらせると、Y_i 点を得ます。 ここで、X_i > Y_i です。
マコさんは、それぞれの k (1 \leq k \leq N) について、Day k までに得られる得点の総和の最大値を知りたいです。 彼女の代わりにこれを求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq N
- 1 \leq Y_i < X_i \leq 10^9
- 入力される値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N A_1 X_1 Y_1 A_2 X_2 Y_2 \vdots A_N X_N Y_N
出力
N 行出力せよ。 k 行目には、Day k までに得られる得点の総和の最大値を出力せよ。
入力例 1
3 1 10 9 1 7 4 2 3 2
出力例 1
10 16 19
各 k における最適な宿題の終わらせ方は、以下のようになります。
k=1 の場合、Day 1 に宿題 1 を終わらせれば、10 点を得ます。
k=2 の場合、Day 1 に宿題 2 を、Day 2 に宿題 1 を終わらせれば、7+9=16 点を得ます。
k=3 の場合、Day 1 に宿題 2 を、Day 2 に宿題 3 を、Day 3 に宿題 1 を終わらせれば、7+3+9=19 点を得ます。
入力例 2
6 2 58 37 2 67 12 3 82 79 4 23 6 4 82 64 1 40 17
出力例 2
82 164 231 289 309 328
入力例 3
15 9 605824191 280849371 4 596581791 33288517 9 721865638 162970480 3 973186445 472655273 6 305716162 49621035 8 630727512 144854327 5 314582040 241964889 2 837187623 326231876 1 619623058 10421080 9 938725073 25997036 2 256037683 12811156 8 930775386 430074396 9 724058993 159628544 9 519111960 59073187 3 157350380 35127939
出力例 3
973186445 1911911518 2842686904 3679874527 4403933520 5125799158 5756526670 6376149728 6981973919 7253580890 7495545779 7554618966 7604240001 7639367940 7652179096