競プロ典型 90 問

001 - Yokan Party（★4）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 4 点

問題文

左右の長さが L [cm] のようかんがあります。 N 個の切れ目が付けられており、左から i 番目の切れ目は左から A_i [cm] の位置にあります。

あなたは N 個の切れ目のうち K 個を選び、ようかんを K+1 個のピースに分割したいです。そこで、以下の値を スコア とします。

K+1 個のピースのうち、最も短いものの長さ（cm 単位）

スコアが最大となるように分割する場合に得られるスコアを求めてください。

制約

1 \leq K \leq N \leq 100000
0 \lt A_1 \lt A_2 \lt \cdots \lt A_N \lt L \leq 10^9
入力はすべて整数

入力

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

N L
K
A_1 A_2 \cdots A_N

出力

求めるスコアを出力してください。

入力例 1

3 34
1
8 13 26

出力例 1

左から 2 番目の切れ目で分割すると、長さ 13 [cm] のピースと長さ 21 [cm] のピースに分かれ、スコア 13 を達成できます。

入力例 2

7 45
2
7 11 16 20 28 34 38

出力例 2

左から 3 番目と 5 番目の切れ目で分割すると、スコア 12 を達成できます。

入力例 3

3 100
1
28 54 81

出力例 3

左から 2 番目の切れ目で分割すると、スコア 46 を達成できます。

入力例 4

3 100
2
28 54 81

出力例 4

入力例 5

20 1000
4
51 69 102 127 233 295 350 388 417 466 469 523 553 587 720 739 801 855 926 954

出力例 5

Source Name

「競プロ典型90問」1日目

002 - Encyclopedia of Parentheses（★3）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 3 点

問題文

長さ N の正しいカッコ列をすべて、辞書順に出力してください。

ただし、正しいカッコ列は次のように定義されています :

() は正しいカッコ列である
S が正しいカッコ列であるとき、文字列 ( +S+ ) は正しいカッコ列である
S,T が正しいカッコ列であるとき、文字列 S+T は正しいカッコ列である
それ以外の文字列はすべて、正しいカッコ列でない

例えば、

()()
(()())(())
()()()()()()()()

は正しいカッコ列ですが、

)(
)))()(((
((((a))))

は正しいカッコ列ではありません。

また、 ( の方が ) よりも辞書順で早いものとします。

制約

1 \leq N \leq 20
N は整数

入力

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

出力

長さ N の正しいカッコ列をすべて、辞書順に、改行区切りで出力してください。

入力例 1

出力例 1

()

長さ 2 の正しいカッコ列は () のみです。

入力例 2

出力例 2

※何も出力しない場合もあります。

入力例 3

出力例 3

(())
()()

入力例 4

出力例 4

((((()))))
(((()())))
(((())()))
(((()))())
(((())))()
((()(())))
((()()()))
((()())())
((()()))()
((())(()))
((())()())
((())())()
((()))(())
((()))()()
(()((())))
(()(()()))
(()(())())
(()(()))()
(()()(()))
(()()()())
(()()())()
(()())(())
(()())()()
(())((()))
(())(()())
(())(())()
(())()(())
(())()()()
()(((())))
()((()()))
()((())())
()((()))()
()(()(()))
()(()()())
()(()())()
()(())(())
()(())()()
()()((()))
()()(()())
()()(())()
()()()(())
()()()()()

Source Name

「競プロ典型90問」2日目

003 - Longest Circular Road（★4）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 4 点

問題文

N 個の都市があり、それぞれの都市に 1 から N までの番号が付けられています。また、N-1 本の道路があり、i 本目 (1 \leq i \leq N-1) の道路は都市 A_i と都市 B_i を双方向に結んでいます。どの都市の間も、いくつかの道路を通って移動可能なものとなっています。

さて、あなたは整数 u, v (1 \leq u \lt v \leq N) を自由に選び、都市 u と都市 v を双方向に結ぶ道路を 1 本だけ新設することができます。そこで、以下で定められる値を スコア とします。

同じ道を 2 度通らずにある都市から同じ都市に戻ってくる経路における、通った道の本数（この値はただ 1 つに定まる）

スコアとして考えられる最大の値を出力してください。

制約

3 \leq N \leq 100000
1 \leq A_i \lt B_i \leq N (1 \leq i \leq N-1)
どの都市の間も、いくつかの道路を通って移動可能
与えられる入力は全て整数

入力

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

N
A_1 B_1
\vdots
A_{N-1} B_{N-1}

出力

問題文で定義されたスコアとして考えられる最大値を出力してください。

入力例 1

3
1 2
2 3

出力例 1

都市 1 と都市 3 の間に道路を建設します。そうすると、都市 1 → 都市 2 → 都市 3 → 都市 1 という経路で通る道の本数が 3 本となり、スコア 3 を達成できます。

入力例 2

出力例 2

都市 1 と都市 5 の間に道路を建設します。そうすると、都市 1 → 都市 2 → 都市 3 → 都市 5 → 都市 1 という経路で通る道の本数が 4 本となり、スコア 4 を達成できます。

入力例 3

出力例 3

入力例 4

出力例 4

Source Name

「競プロ典型90問」3日目

004 - Cross Sum（★2）

Time Limit: 5 sec / Memory Limit: 1024 MB

配点: 2 点

問題文

H 行 W 列のマス目があります。上から i\ (1 \leq i \leq H) 行目、左から j\ (1 \leq j \leq W) 列目にあるマス (i, j) には、整数 A_{i, j} が書かれています。すべてのマス (i, j)\ (1 \leq i \leq H, 1 \leq j \leq W) について、以下の値を求めてください。

マス (i, j) と同じ行または同じ列にあるマス（自分自身を含む）に書かれている整数をすべて合計した値

制約

2 \leq H, W \leq 2000
1 \leq A_{i, j} \leq 99
入力は全て整数

入力

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

H W
A_{1, 1} A_{1, 2} \cdots A_{1, W}
A_{2, 1} A_{2, 2} \cdots A_{2, W}
\vdots
A_{H, 1} A_{H, 2} \cdots A_{H, W}

出力

マス (i, j) と同じ行または同じ列にあるマス（自分自身を含む）に書かれている整数をすべて合計した値を B_{i, j} として、以下の形式で出力してください。

B_{1, 1} B_{1, 2} \cdots B_{1, W}
B_{2, 1} B_{2, 2} \cdots B_{2, W}
\vdots
B_{H, 1} B_{H, 2} \cdots B_{H, W}

入力例 1

出力例 1

5 5 5
5 5 5
5 5 5

入力例 2

出力例 2

28 28 25 26
39 33 40 34
38 38 36 31
41 41 39 43

マス (1, 1) と同じ行または同じ列にあるマスに書かれている整数の合計は次の通りです。

3+1+4+1+5+5+9=28

入力例 3

2 10
31 41 59 26 53 58 97 93 23 84
62 64 33 83 27 95 2 88 41 97

出力例 3

627 629 598 648 592 660 567 653 606 662
623 633 651 618 645 650 689 685 615 676

入力例 4

10 10
83 86 77 65 93 85 86 92 99 71
62 77 90 59 63 76 90 76 72 86
61 68 67 79 82 80 62 73 67 85
79 52 72 58 69 67 93 56 61 92
79 73 71 69 84 87 98 74 65 70
63 76 91 80 56 73 62 70 96 81
55 75 84 77 86 55 96 79 63 57
74 95 82 95 64 67 84 64 93 50
87 58 76 78 88 84 53 51 54 99
82 60 76 68 89 62 76 86 94 89

出力例 4

1479 1471 1546 1500 1518 1488 1551 1466 1502 1546
1414 1394 1447 1420 1462 1411 1461 1396 1443 1445
1388 1376 1443 1373 1416 1380 1462 1372 1421 1419
1345 1367 1413 1369 1404 1368 1406 1364 1402 1387
1416 1417 1485 1429 1460 1419 1472 1417 1469 1480
1410 1392 1443 1396 1466 1411 1486 1399 1416 1447
1397 1372 1429 1378 1415 1408 1431 1369 1428 1450
1419 1393 1472 1401 1478 1437 1484 1425 1439 1498
1366 1390 1438 1378 1414 1380 1475 1398 1438 1409
1425 1442 1492 1442 1467 1456 1506 1417 1452 1473

Source Name

「競プロ典型90問」4日目

005 - Restricted Digits（★7）

Time Limit: 5 sec / Memory Limit: 1024 MB

配点: 7 点

問題文

数字 c_1,c_2, \dots ,c_K のみを使うことで作れる N 桁の正の整数のうち B の倍数であるものは何個あるでしょうか。 10^9 + 7 で割った余りを求めてください。

制約

1 \leq K \leq 9
1 \leq c_1 \lt c_2 \lt \cdots \lt c_K \leq 9
1 \leq N \leq 10^{18}
2 \leq B \leq 1000
入力はすべて整数

小課題・得点

この問題はいくつかの小課題に分けられ、その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます。
提出したソースコードの得点は、正解した小課題の点数の合計となります。

(1 点)： N \leq 10000, \ B \leq 30
(3 点)： B \leq 30
(3 点)：追加の制約はない。

入力

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

N B K
c_1 c_2 \cdots c_K

出力

答えを 10^9 + 7 で割った余りを出力してください。

入力例 1

3 7 3
1 4 9

出力例 1

1, 4, 9 から作れる 3 桁の 7 の倍数は 119, 441, 994 の 3 個です。

入力例 2

5 2 3
1 4 9

出力例 2

入力例 3

10000 27 7
1 3 4 6 7 8 9

出力例 3

989112238

入力例 4

1000000000000000000 29 6
1 2 4 5 7 9

出力例 4

853993813

※この入力例は小課題 2, 3 のみの制約を満たします。

入力例 5

1000000000000000000 957 7
1 2 3 5 6 7 9

出力例 5

205384995

※この入力例は小課題 3 のみの制約を満たします。

Source Name

「競プロ典型90問」5日目

006 - Smallest Subsequence（★5）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 5 点

問題文

英小文字のみからなる、長さ N の文字列 S が与えられます。

長さが K である S の部分列のうち、辞書順で最小であるものを出力してください。

注意

文字列 T の 部分列 とは、T から 0 個以上の文字を取り除いた後、残りの文字を元の順序を保ったまま連結して得られる文字列を指します。

「辞書順」での大小の定義

X = x_1 x_2 \ldots x_n, Y = y_1 y_2 \ldots y_m を二つの異なる文字列とするとき、X が Y の接頭辞であるか、j を x_j \neq y_j であるような最小の整数として x_j < y_j である場合、そしてその場合に限って「X は Y より辞書順で小さい」と言います。

制約

1 \leq K \leq N \leq 100000
S は英小文字のみからなる長さ N の文字列
N, K は整数

入力

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

N K
S

出力

答えとなる文字列を出力してください。

入力例 1

7 3
atcoder

出力例 1

acd

1, 3, 5 文字目のみを取り出すことで文字列 acd ができます。
この文字列はあり得る 3 文字の部分列のなかで辞書順最小です。

入力例 2

14 5
kittyonyourlap

出力例 2

inlap

Source Name

「競プロ典型90問」6日目

007 - CP Classes（★3）

Time Limit: 3 sec / Memory Limit: 1024 MB

配点: 3 点

問題文

ABC 競技プログラミング塾には N 個のクラスがあり、番号 i (1 \leq i \leq N) のクラスはレーティング A_i の生徒を対象としています。

今、Q 人の生徒がこの塾に入塾しようとしています。番号 j (1 \leq j \leq Q) の生徒のレーティングは B_j です。各生徒は自分に合わないレベルのクラスに行くと不満になります。各生徒について、その不満度は次のように定義されます。

対象レーティング a と自分のレーティング b の差の絶対値、すなわち |a-b|

j=1,2,3,\ldots,Q それぞれについて、番号 j の生徒の不満度として考えられる最小値を求めてください。ただし、1 人も入らないクラス、複数人から成るクラスがあっても良いものとします。

制約

1\leq N \leq 300000
1\leq Q \leq 300000
0\leq A_i \leq 10^9
0\leq B_j \leq 10^9
入力はすべて整数

入力

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

N
A_1 A_2 A_3 \cdots A_N
Q
B_1
B_2
B_3
\vdots
B_Q

出力

j=1,2,3,\ldots,Q それぞれについて、標準出力に答えを一行ずつ、総計 Q 行に出力してください。

入力例 1

4
4000 4400 5000 3200
3
3312
2992
4229

出力例 1

112
208
171

入力例 2

出力例 2

入力例 3

10
869120000 998244353 777777777 123456789 100100100 464646464 987654321 252525252 869120001 1000000000
10
4229
20210406
1
268435456
3582
536870912
1000000000
869120
99999999
869120001

出力例 3

入力例 4

100
298750376 229032640 602876667 944779015 909539868 533609371 231368330 445484152 408704870 850216874 349286798 30417810 807260002 554049450 40706045 380488344 749325840 801881841 459457853 66691229 5235900 8100458 46697277 997429858 827651689 790051948 981897272 271364774 536232393 997361572 449659237 602191750 294800444 346669663 792837293 277667068 997282249 468293808 444906878 702693341 894286137 845317003 27053625 926547765 739689211 447395911 902031510 326127348 582956343 842918193 235655766 844300842 438389323 406413067 862896425 464876303 68833418 76340212 911399808 745744264 551223563 854507876 196296968 52144186 431165823 275217640 424495332 847375861 337078801 83054466 648322745 694789156 301518763 319851750 432518459 772897937 630628124 581390864 313132255 350770227 642944345 677742851 448945480 688009163 160941957 290297295 5532462 823543277 19634445 15791361 193309093 66202596 72364149 743270896 297240520 264035189 898589962 59916738 307942952 403411309
30
930579110
22697034
44652533
280533771
753567118
684927419
923477579
557613803
779616458
389130756
323671659
3117850
408004003
224808850
18421958
359047808
364572866
334631363
854759331
647435074
826055423
668443532
620408208
32237184
67299071
251185742
217292659
16181227
850865411
218577687

出力例 4

Source Name

「競プロ典型90問」7日目

008 - AtCounter（★4）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 4 点

問題文

英小文字のみからなる、長さ N の文字列 S が与えられます。S の i 文字目を s_i とします。

S から 0 個以上の文字を取り出す方法は 2^{N} 通りありますが、そのうち以下の条件を満たすものは何通りあるでしょうか？答えは非常に大きくなる可能性があるため、答えを 10^9 + 7 で割った余りを出力してください。

取り出した文字を順番を変えずに結合して出来た文字列が "atcoder" となる

ただし「文字を取り出す方法」は、どちらか一方でのみ取り出しているような文字 s_i (1 \leq i \leq N) が少なくとも一つ存在する場合に区別されます。

制約

1 \leq N \leq 100{,}000
|S| = N
文字列 S は英小文字のみからなる

入力

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

N
S

出力

答えを 10^9 + 7 で割った余りを出力してください。

入力例 1

10
attcordeer

出力例 1

部分列が "atcoder" となるものの一例として、S の (1, 2, 4, 5, 7, 8, 10) 番目の文字を採用するものが考えられます。この他にも条件を満たす部分列が 3 通り存在するため、答えは 4 通りです。

入力例 2

41
btwogablwetwoiehocghiewobadegwhoihegnldir

出力例 2

入力例 3

140
aaaaaaaaaaaaaaaaaaaattttttttttttttttttttccccccccccccccccccccooooooooooooooooooooddddddddddddddddddddeeeeeeeeeeeeeeeeeeeerrrrrrrrrrrrrrrrrrrr

出力例 3

279999993

10^9 + 7 で割った余りを出力してください。

Source Name

「競プロ典型90問」8日目

009 - Three Point Angle（★6）

Time Limit: 3 sec / Memory Limit: 1024 MB

配点: 6 点

問題文

座標平面上に相異なる N 個の点 P_1, \dots, P_N があり、点 P_i の座標は (X_i, Y_i) です。

この N 個の点から相異なる3点 P_i, P_j, P_k を選び、\angle P_i P_j P_k を最大にしたいです。この最大値を度数法で出力してください。

ただし、0^\circ \leq \angle P_i P_j P_k \leq 180^{\circ} とします。

\angle P_i P_j P_kとは

点 P_i \to 点 P_j \to 点 P_k の折れ線で構成される角の大きさのことです。

制約

3 \leq N \leq 2000
0 \leq X_i, Y_i \leq 10^9 (1 \leq i \leq N)
(X_i, Y_i) \neq (X_j, Y_j) (1 \leq i < j \leq N)
入力される値は全て整数である

入力

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

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

出力

\angle P_i P_j P_k の最大値を度数法で出力してください。ただし、相対誤差または絶対誤差が 10^{-7} 以下であれば正解として扱われます。

入力例 1

出力例 1

P_1, P_2, P_3 の座標はそれぞれ (0, 0), (0, 10), (10, 10) です。

\angle P_1 P_2 P_3=90^\circ
\angle P_2 P_3 P_1=45^\circ
\angle P_3 P_1 P_2=45^\circ

であり、 \angle P_1 P_2 P_3=90^\circ が最大なので、90 と出力すればよいです。

入力例 2

出力例 2

171.869897645844

\angle P_2 P_3 P_4 = 171.869\cdots^\circ が最大です。

入力例 3

出力例 3

\angle P_1 P_6 P_{10}=180^\circ が最大です。

入力例 4

40
298750376 229032640
602876667 944779015
909539868 533609371
231368330 445484152
408704870 850216874
349286798 30417810
807260002 554049450
40706045 380488344
749325840 801881841
459457853 66691229
5235900 8100458
46697277 997429858
827651689 790051948
981897272 271364774
536232393 997361572
449659237 602191750
294800444 346669663
792837293 277667068
997282249 468293808
444906878 702693341
894286137 845317003
27053625 926547765
739689211 447395911
902031510 326127348
582956343 842918193
235655766 844300842
438389323 406413067
862896425 464876303
68833418 76340212
911399808 745744264
551223563 854507876
196296968 52144186
431165823 275217640
424495332 847375861
337078801 83054466
648322745 694789156
301518763 319851750
432518459 772897937
630628124 581390864
313132255 350770227

出力例 4

179.9834340684232

Source Name

「競プロ典型90問」9日目

010 - Score Sum Queries（★2）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 2 点

問題文

ABC 大学には N 人の一年生が在籍しています。クラスは 2 つあり、学籍番号 i 番の生徒のクラスは C_i 組です。今日は期末試験が返却され、学籍番号 i 番の生徒の点数は P_i 点でした。

以下の形式の質問が Q 個与えられます。j = 1, 2, \dots, Q それぞれについて答えてください。

学籍番号 L_j \sim R_j 番の 1 組生徒における、期末試験点数の合計
学籍番号 L_j \sim R_j 番の 2 組生徒における、期末試験点数の合計
これら 2 つの値をそれぞれ求めよ。

制約

1 \leq N \leq 100000
1 \leq C_i \leq 2
0 \leq P_i \leq 100
1 \leq Q \leq 100000
1 \leq L_j \leq R_j \leq N
入力は全て整数

入力

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

N
C_1 P_1
C_2 P_2
\vdots
C_N P_N
Q
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q

出力

学籍番号 L_j \sim R_j 番の 1 組生徒における期末試験点数の合計を A_j、学籍番号 L_j \sim R_j 番の 2 組生徒における期末試験点数の合計を B_j として、以下の形式で出力してください。

A_1 B_1
A_2 B_2
\vdots
A_Q B_Q

入力例 1

出力例 1

63 261

学籍番号 2 \sim 6 番の 1 組生徒における、期末試験合計点は 23+40=63 です。
また、学籍番号 2 \sim 6 番の 2 組生徒における、期末試験合計点は 78+94+89=261 です。

入力例 2

出力例 2

入力例 3

出力例 3

100 0
100 0
100 0

一方の組の生徒が存在しないケースもあります。

入力例 4

出力例 4

Source Name

「競プロ典型90問」10日目

011 - Gravy Jobs（★6）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 6 点

問題文

ABC 君にお仕事の依頼が N 件来ました。各仕事には 1, 2, \cdots, N と番号が付けられています。

仕事 i は締切が D_i 日目の終わりであり、連続する C_i 日間を使うことで完了できます。それ以外の方法で仕事を完了することはできません。

より正確には、仕事 i を締切までに完了するためには、C_i\leq k\leq D_i を満たすある整数 k について k-C_i+1 日目の始めから k 日目の終わりまで i 番目の仕事を続けなければなりません。

仕事 i を締切までに完了すると S_i 円の報酬がもらえます。1 日には高々 1 種類しか仕事を行うことができません。

現在は 1 日目の始まりです。ABC 君が上手く取り掛かる仕事を選んでスケジュールを組んだ場合、彼が得られる報酬の金額として考えられる最大値を求めてください。

制約

1 \leq N \leq 5000
1 \leq D_i \leq 5000\ (1\leq i\leq N)
1 \leq C_i \leq 5000\ (1\leq i\leq N)
1 \leq S_i \leq 10^9\ (1\leq i\leq N)
入力は全て整数

小課題・得点

この問題はいくつかの小課題に分けられ、その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます。
提出したソースコードの得点は、正解した小課題の点数の合計となります。
それぞれの小課題は上の制約に加えて、それぞれ次の制約を満たします。

(2 点): N\leq8
(2 点): N\leq20
(2 点): 追加の制約はない。

入力

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

N
D_1 C_1 S_1
D_2 C_2 S_2
\vdots
D_N C_N S_N

出力

ABC君が得られる報酬の金額として考えられる最大値を一行に出力してください。

入力例 1

1
12 3 69853

出力例 1

1 日目から 3 日目までの 3 日をかけて 1 番目の仕事を完了することで 69853 円を得ることができます。

69853 円より多く報酬を得ることはできないため、答えは 69853 円です。

入力例 2

出力例 2

2 日目から 4 日目までの 3 日をかけて 3 番目の仕事を、5 日目から 7 日目までの 3 日をかけて 1 番目の仕事を完了することで 350000 円を得ることができます。

350000 円より多く報酬を得ることはできないため、答えは 350000 円です。

入力例 3

8
376 640 602876667
4015 1868 533609371
3330 152 408704870
1874 798 30417810
2 1450 40706045
3344 1840 801881841
2853 1229 5235900
458 1277 997429858

出力例 3

1744196082

入力例 4

20
376 640 602876667
4015 868 533609371
3330 152 408704870
1874 798 30417810
2 450 40706045
3344 840 801881841
2853 229 5235900
458 277 997429858
1689 948 981897272
4774 393 997361572
4237 750 294800444
4663 293 277667068
2249 808 444906878
3341 137 845317003
3625 765 739689211
911 510 326127348
1343 193 235655766
842 323 406413067
1425 303 68833418
212 808 745744264

出力例 4

6583558066

この入力例は小課題 1 の制約を満たしませんが、小課題 2,3 の制約を満たします。

入力例 5

30
376 140 602876667
4015 368 533609371
3330 152 408704870
1874 298 30417810
2 450 40706045
3344 340 801881841
2853 229 5235900
458 277 997429858
1689 448 981897272
4774 393 997361572
4237 250 294800444
4663 293 277667068
2249 308 444906878
3341 137 845317003
3625 265 739689211
911 10 326127348
1343 193 235655766
842 323 406413067
1425 303 68833418
212 308 745744264
3563 376 196296968
4186 323 275217640
332 361 337078801
4466 245 694789156
3763 250 432518459
2937 124 581390864
2255 227 642944345
2851 480 688009163
1957 295 5532462
3277 445 15791361

出力例 5

11420667389

この入力例は小課題 1,2 の制約を満たしませんが、小課題 3 の制約を満たします。

Source Name

「競プロ典型90問」11日目

012 - Red Painting（★4）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 4 点

問題文

H 行 W 列のマス目があり、上から i (1 \leq i \leq H) 行目、左から j (1 \leq j \leq W) 列目のマスを (i, j) と表します。

最初すべてのマスは白いです。ここで、Q 個のクエリが以下の形式で与えられます。

i (1 \leq i \leq Q) 番目のクエリについて：

t_i = 1 のとき
- 整数 r_i, c_i が与えられる。
- 白いマス (r_i, c_i) が赤色で塗られる。
t_i = 2 のとき
- 整数 {ra}_i, {ca}_i, {rb}_i, {cb}_i が与えられる。
- 次の 2 つの条件両方を満たすとき Yes、そうでなければ No と出力する。
  - マス ({ra}_i, {ca}_i) とマス ({rb}_i, {cb}_i) が赤色で塗られている。
  - マス ({ra}_i, {ca}_i) からマス ({rb}_i, {cb}_i) まで赤色マス上を上下左右に移動することで辿り着ける。

以上の Q 個のクエリを順に処理してください。

制約

1 \leq H, W \leq 2000
1 \leq Q \leq 100000
1 \leq t_i \leq 2
t_i = 1 のとき、1 \leq r_i \leq H、1 \leq c_i \leq W
t_i = 2 のとき、1 \leq {ra}_i, {rb}_i \leq H、1 \leq {ca}_i, {cb}_i \leq W
t_i = 1 かつ t_j = 1 (1 \leq i < j \leq Q) のとき、(r_i, c_i) \neq (r_j, c_j)
与えられる入力は全て整数

入力

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

H W 
Q
q_1
\vdots
q_Q

ここで、q_i は i 番目のクエリの情報であり、以下の 2 つの形式のどちらかを満たします。

1 r_i c_i

2 {ra}_i {ca}_i {rb}_i {cb}_i

出力

与えられた Q 個のクエリのうち t_i = 2 のクエリを処理した結果を順に、改行で区切って 1 行ずつ出力してください。

入力例 1

出力例 1

No
No
Yes
Yes
No

与えられた 10 個のクエリを順に処理すると以下のようになります。

マス (2, 2) が赤色で塗られる。
マス (1, 1) が赤色で塗られる。
マス (1, 1) からマス (2, 2) までは赤色マス上を上下左右に移動することで到達できないので No を出力する。
マス (3, 2) が赤色で塗られる。
マス (1, 1) からマス (2, 2) までは赤色マス上を上下左右に移動することで到達できないので No を出力する。
マス (2, 2) からマス (3, 2) までは赤色に塗られていて、上下方向で隣接しているマスなので Yes を出力する。
マス (2, 3) が赤色で塗られる。
マス (2, 1) が赤色で塗られる。
マス (1, 1) からマス (2, 2) まではマス (1, 1) → マス (2, 1) → マス (2, 2) と赤色マス上を上下左右に移動して到達できるので Yes を出力する。
マス (1, 1) からマス (3, 3) までは赤色マス上を上下左右に移動することでたどり着けないので No を出力する。

入力例 2

出力例 2

No
Yes

1 マスも赤色で塗られていない場合に注意してください。

入力例 3

出力例 3

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes

Source Name

「競プロ典型90問」12日目

013 - Passing（★5）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 5 点

問題文

AGC 王国には N 個の街があり、それぞれ 1, 2, \cdots, N の番号がついています。また、街と街を結ぶ M 本の道路があります。i 番目の道路は街 A_i と B_i を双方向に結んでおり、通るのに C_i 分かかります。

k = 1, 2, \cdots, N それぞれについて、街 1 から街 k を経由して街 N まで移動するときにかかる時間の最小値を求めてください。

制約

2 \leq N \leq 100000
1 \leq M \leq \min\left(100000, \frac{N(N-1)}{2}\right)
1 \leq A_i < B_i \leq N
(A_i, B_i) \neq (A_j, B_j) (1 \leq i < j \leq M)
1 \leq C_i \leq 10000
どの街の間もいくつかの道路を通って移動が可能である
入力はすべて整数

入力

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

N M
A_1 B_1 C_1
\vdots
A_M B_M C_M

出力

N 行出力してください。
k (1 \leq k \leq N) 行目には、街 1 から街 k を経由して街 N まで移動するときにかかる時間の最小値を分単位で出力してください。

入力例 1

出力例 1

例えば k = 3 のときは、以下のような経路を通るのが最適です。このときかかる時間は 9 分であるので、3 行目には 9 を出力します。

入力例 2

出力例 2

入力例 3

出力例 3

Source Name

「競プロ典型90問」13日目

014 - We Used to Sing a Song Together（★3）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 3 点

問題文

AGC 街道には N 人の小学生が住んでおり、小学生 i (1 \leq i \leq N) の家は位置 A_i にあります。
また、小学校は N 校建てられており、小学校 j (1 \leq j \leq N) は位置 B_j にあります。
AGC 街道に住む小学生は性格が悪く、どの人同士も険悪な関係になっているため、全員が別の学校に通うようにしたいです。

また、不便さは次のように定義されます。

小学生 i にとっての家から学校までの距離を E_i とするとき、不便さは距離の総和、すなわち E_1 + E_2 + ... + E_N である。
ただし、位置 u から位置 v までの距離は |u-v|

どの生徒も別の学校に通うという条件下における、不便さとして考えられる最小値を求めてください。

制約

1 \leq N \leq 100000
0 \leq A_i \leq 10^9
0 \leq B_j \leq 10^9
A_1, A_2, \dots, A_N は相異なる
B_1, B_2, \dots, B_N は相異なる
入力はすべて整数

入力

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

N
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_N

出力

答えを出力してください。

入力例 1

1
869
120

出力例 1

小学生 1 の家と小学校 1 の距離は |869 - 120| = 749 です。
この入力では小学生 1 が必ず小学校 1 に通うことになるため、この値が不便さとして考えられる唯一の値であり、最小値です。

入力例 2

6
8 6 9 1 2 0
1 5 7 2 3 9

出力例 2

小学生 1,2,3,4,5,6 をそれぞれ小学校 3,2,6,4,5,1 に通わせることにすると、不便さは |8-7|+|6-5|+|9-9|+|1-2|+|2-3|+|0-1|=5 となります。
これ以上不便さを小さくすることはできないため、答えは 5 です。

入力例 3

10
31 41 59 26 53 58 97 93 23 84
17 32 5 8 7 56 88 77 29 35

出力例 3

入力例 4

20
804289382 846930886 681692776 714636914 957747792 424238335 719885386 649760491 596516649 189641420 25202361 350490026 783368690 102520058 44897761 967513925 365180539 540383425 304089172 303455735
35005211 521595368 294702567 726956428 336465782 861021530 278722862 233665123 145174065 468703135 101513928 801979801 315634021 635723058 369133068 125898166 59961392 89018454 628175011 656478041

出力例 4

2736647674

Source Name

「競プロ典型90問」14日目

015 - Don't be too close（★6）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 6 点

問題文

1 から N までの整数が書かれた、N 個のボールがあります。 k = 1, 2, 3, ..., N それぞれについて、以下の質問に答えてください。

これら N 個のボールから 1 個以上のボールを選ぶ方法は 2^N-1 通り存在するが、その中で次の条件を満たす選び方は何通りあるか。
- どの選んだ 2 つのボールについても、書かれている整数の差が k 以上である。
ただし、答えは非常に大きくなることがあるので、10^9+7 で割った余りを出力すること。

制約

1 \leq N \leq 10^5
N は整数

入力

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

出力

出力は N 行からなります。

i\ (1\leq i \leq N) 行目には、k = i のときの答えを 10^9+7 で割った余りを出力してください。

入力例 1

出力例 1

ボール 1 を選ぶ 1 通りのみが存在します。

入力例 2

出力例 2

3
2

k=1 のとき、選んだボールの集合として、\{1\}、\{2\}、\{1,2\} の 3 通りが存在します。

k=2 のとき、\{1\}、\{2\} の 2 通りが存在します。

入力例 3

出力例 3

7
4
3

入力例 4

出力例 4

入力例 5

出力例 5

入力例 6

出力例 6

入力例 7

出力例 7

10^9+7 で割った余りを出力してください。

Source Name

「競プロ典型90問」15日目

016 - Minimum Coins（★3）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 3 点

問題文

A 円硬貨、B 円硬貨、C 円硬貨をそれぞれ 0 枚以上使ってちょうど N 円を支払うとき、使う硬貨の枚数として考えられる最小値を求めてください。

ただし、それぞれの硬貨は無数にあるものとします。

制約

1 \leq A, B, C, N \leq 10^9
A, B, C はすべて異なる
合計 9999 枚以下の硬貨でちょうど N 円を支払うことができる
入力はすべて整数

入力

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

N
A B C

出力

答えを出力してください。

入力例 1

227
21 47 56

出力例 1

21 円硬貨を 1 枚、47 円硬貨を 2 枚、56 円硬貨を 2 枚使って支払うのが最適です。
合計で 5 枚となります。

入力例 2

9999
1 5 10

出力例 2

1 円硬貨を 4 枚、5 円硬貨を 1 枚、10 円硬貨を 999 枚使って支払うのが最適です。
合計で 1004 枚となります。

入力例 3

998244353
314159 265358 97932

出力例 3

入力例 4

100000000
10001 10002 10003

出力例 4

Source Name

「競プロ典型90問」16日目

017 - Crossing Segments（★7）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 7 点

問題文

円周上に N 個の点があり、時計回りに 1, 2, \ldots, N と番号づけられています。また、M 本の線分があり、線分 i は点 L_i と点 R_i を結んでいます。

線分 s,t が端点以外で交わるような、(s,t) (1 \leq s \lt t \leq M) の組の数を求めてください。

制約

3\leq N\leq 300000
2\leq M\leq 300000
1\leq L_i < R_i\leq N
(L_i, R_i) \neq (L_j, R_j) (1 \leq i \lt j \leq M)

小課題

(1 点) N \leq 1000, M \leq 1000
(2 点) N \leq 1000, M \leq 100000
(4 点) 追加の制約はない

入力

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

N M
L_1 R_1
L_2 R_2
\vdots
L_M R_M

出力

線分 s,t が端点以外で交わるような (s,t) (1 \leq s \lt t \leq M) の組の数を出力してください。

入力例 1

出力例 1

入力例 2

出力例 2

入力例 3

出力例 3

入力例 4

出力例 4

入力例 5

出力例 5

Source Name

「競プロ典型90問」17日目

018 - Statue of Chokudai（★3）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点：3 点

問題文

平面 x = 0 上に、高さ L の T 分で一周する観覧車があります。観覧車は円形になっており、次のように一定の速さで動きます。ただし、xy 平面が水平方向、z 軸が垂直方向です。

乗ってから 0 分後には、座標 (0, 0, 0) にある
乗ってから \frac{T}{4} 分後には、座標 (0, -\frac{L}{2}, \frac{L}{2}) にある
乗ってから \frac{T}{2} 分後には、座標 (0, 0, {L}) にある
乗ってから \frac{3T}{4} 分後には、座標 (0, \frac{L}{2}, \frac{L}{2}) にある

観覧車の名物である「高橋直大像」は、座標 (X, Y, 0) に存在します。以下の形式の質問が Q 個与えられるので、順に答えてください。

i 個目の質問では、E869120 君が観覧車に乗ってから E_i 分後における、E869120 君から見た高橋直大像の俯角を求めよ。

制約

2 \leq T \leq 10^9
1 \leq L, X, Y \leq 10^9
1 \leq Q \leq 1000
0 \leq E_i \lt T
入力は全て整数で与えられる

入力

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

T
L X Y
Q
E_1
E_2
:
E_Q

出力

各時刻における高橋直大像の俯角を、合計 Q 行で順に出力してください。ただし、90 度までの度数法で出力してください。

相対誤差または絶対誤差が 10^{-7} 以下のとき、正答とみなされます。

入力例 1

出力例 1

0.000000000000
24.094842552111
54.735610317245
45.000000000000

高橋直大像は、座標 (1, 1, 0) に存在します。

時刻 0 において、E869120 君は座標 (0, 0, 0) に存在し、E869120 君から見た高橋直大像の俯角は 0 度です。

時刻 3 において、E869120 君は座標 (0, 1, 1) に存在し、E869120 君から見た高橋直大像の俯角は 45 度です。

入力例 2

5121
312000000 4123 3314
6
123
12
445
4114
42
1233

出力例 2

4.322765775902
0.421184234768
15.640867693969
35.396039162484
1.475665637902
43.338582976959

Source Name

「競プロ典型90問」18日目

019 - Pick Two（★6）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 6 点

問題文

長さ 2N の正整数列 A=(A_1,A_2,\ldots,A_{2N}) が与えられます。次の操作で列 A から数を取り除くことを考えます。

残っている列を (A^{\prime}_1,A^{\prime}_2,\ldots,A^{\prime}_M) とする。 1\leq i<M を満たす整数 i を一つ選び、A^{\prime}_i と A^{\prime}_{i+1} を列から取り除く。この操作のあと、残る列は (A^{\prime}_1,\ldots,A^{\prime}_{i-1},A^{\prime}_{i+2},\ldots,A^{\prime}_M) である。

この操作には コスト がかかります。 1 回の操作にかかるコストは、取り除く数を A^{\prime}_i,A^{\prime}_{i+1} として |A^{\prime}_i-A^{\prime}_{i+1}| です。

この操作を N 回繰り返して列 A から全ての数を取り除くとき、N 回の操作にかかるコストの総和として考えられる最小の値を求めてください。

制約

1 \leq N \leq 200
1 \leq A_i \leq 10^6\ (1\leq i\leq 2N)
入力は全て整数

入力

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

N
A_1 A_2 \ldots A_{2N}

出力

N 回の操作にかかるコストの総和として考えられる最小の値を出力してください。

入力例 1

3
6 2 3 9 8 6

出力例 1

コストの総和が最小になる操作の例を以下に示します。

i=2 とし、|2 - 3| = 1 のコストをかけて操作を行う。列は (6,9,8,6) となる。
i=2 とし、|9 - 8| = 1 のコストをかけて操作を行う。列は (6,6) となる。
i=1 とし、|6 - 6| = 0 のコストをかけて操作を行う。列は () となる。

3 回の操作にかかるコストの総和は 2 となります。

入力例 2

3
1 3 5 5 3 1

出力例 2

入力例 3

4
1 2 4 8 16 32 64 128

出力例 3

入力例 4

15
73 8 55 26 97 48 37 47 35 55 5 17 62 2 60 23 99 73 34 75 7 46 82 84 29 41 32 31 52 32

出力例 4

Source Name

「競プロ典型90問」19日目

020 - Log Inequality（★3）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 3 点

問題文

\log_2 a < b \log_2 c ですか？

制約

1 \leq a \leq 9 \times 10^{18}
1 \leq b \leq 17
1 \leq c \leq 13
入力は全て整数

入力

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

a b c

出力

\log_2 a < b \log_2 c ならば Yes 、そうでなければ No と出力してください。

入力例 1

4 3 2

出力例 1

Yes

\log_2 4=2, 3 \log_2 2=3 \times 1=3 より、 \log_2 4 < 3 \log_2 2 です。

入力例 2

16 3 2

出力例 2

No

\log_2 16=4, 3 \log_2 2=3 \times 1=3 より、 \log_2 16 < 3 \log_2 2 ではありません。

入力例 3

8 3 2

出力例 3

No

\log_2 8=3, 3 \log_2 2=3 \times 1=3 より、 \log_2 8 = 3 \log_2 2 です。両辺の値が等しいときも No を出力することに注意してください。

Source Name

「競プロ典型90問」20日目

021 - Come Back in One Piece（★5）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 5 点

問題文

N 頂点 M 辺の有向グラフがあります。辺には 1,2,\dots,M と番号が付けられており、辺 i は頂点 A_i から頂点 B_i に向かいます。

次の条件を満たす 2 頂点 (x, y) の組 (1 \leq x \lt y \leq N) はいくつありますか？

頂点 x から頂点 y に向かうパス、頂点 y から頂点 x に向かうパスが、どちらも存在する

制約

2 \leq N \leq 100000
1 \leq M \leq 200000
1 \leq A_i , B_i \leq N (1 \leq i \leq M)
A_i \ne B_i (1 \leq i \leq M)
入力はすべて整数

入力

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

N M
A_1 B_1
A_2 B_2
 \vdots 
A_M B_M

出力

答えを出力してください。

入力例 1

出力例 1

たとえば、(x,y) = (1,2) は、頂点 1 から頂点 2 へは辺 1 からなるパスが、頂点 2 から頂点 1 へは辺 2 からなるパスが得られるため、条件を満たします。このほかにも (x,y)=(1,4),(2,4) が条件を満たしますが、(x,y)=(2,3) は頂点 3 から頂点 2 へのパスが存在しないため、条件を満たしません。

また、辺 3 と辺 7 のように多重辺が含まれるかもしれないことに気を付けてください。

入力例 2

100 1
1 2

出力例 2

Source Name

「競プロ典型90問」21日目

022 - Cubic Cake（★2）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点：2 点

問題文

幅 A、奥行き B、高さ C の直方体の形をしたケーキがあります。

あなたはケーキに対して、次の操作を行うことができます。

ある面に平行な方向に切断する
ただし、ケーキは動かしてはならない（複数のケーキに分割されている場合、これらを変形したり、別々に切ることはできない）

最小何回の操作で、全てのピースを立方体にすることができますか？

制約

1 \leq A, B, C \leq 10^{18}
入力はすべて整数

入力

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

A B C

出力

最小の操作回数を 1 行で出力してください。

入力例 1

2 2 3

出力例 1

4 回ケーキを切断することで、一辺の長さが 1 の立方体が 12 個できます。

入力例 2

2 2 4

出力例 2

1 回ケーキを切断することで、一辺の長さが 2 の立方体が 2 個できます。

入力例 3

1000000000000000000 999999999999999999 999999999999999998

出力例 3

2999999999999999994

オーバーフローに注意してください。

Source Name

「競プロ典型90問」22日目

023 - Avoid War（★7）

Time Limit: 8 sec / Memory Limit: 2048 MB

配点: 7 点

問題文

縦 H マス、横 W マスからなるグリッドがあり、上から i 行目・左から j 列目のマスを (i,j) で表します。各マスには色が塗られており、マス (i,j) の色は C_{i,j} が # のとき黒、C_{i,j} が . のとき白です。

あなたはいくつかの白マスを選び（1 つも選ばなくても良い）、キングの駒を置きます。 キング同士が互いに攻撃し合わない（後述）ような置き方の数を、10^9+7 で割った余りを求めてください。

ただし、ある 2 つの置き方が異なるとは、「ある白マスが存在して、片方ではキングが置かれており、もう片方では置かれていない」ことを言います。

「キング同士が互いに攻撃し合わない」とは

キングが置かれている任意の異なる 2 マス (i,j) および (k,l) において、 |i-k|>1 または |j-l|>1 が成り立つことを言います。

制約

1 \leq H,W \leq 24
H,W は整数
C_{i,j} は # または .
少なくとも 1 つの白マスが存在する

小課題

(1 点) 1 \leq H,W \leq 4
(1 点) 1 \leq H,W \leq 9
(2 点) 1 \leq H,W \leq 17
(3 点) 追加の制約はない。

入力

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

H W
C_{1,1}\cdots C_{1,W}
\vdots
C_{H,1}\cdots C_{H,W}

出力

条件を満たす置き方の数を、10^9+7 で割った余りを出力してください。

入力例 1

1 3
...

出力例 1

以下の 5 通りがあります。( o はキングを置いたマスを表します。)

...     o..     .o.     ..o     o.o

これは小課題 1,2,3,4 の制約を満たします。

入力例 2

3 3
.#.
#..
.##

出力例 2

以下の 13 通りがあります。( o はキングを置いたマスを表します。)

.#.     o#.     .#o     .#.     .#.     .#.     o#o
#..     #..     #..     #o.     #.o     #..     #..
.##     .##     .##     .##     .##     o##     .##

o#.     o#.     .#o     .#.     o#o     o#.
#.o     #..     #..     #.o     #..     #.o
.##     o##     o##     o##     o##     o##

これは小課題 1,2,3,4 の制約を満たします。

入力例 3

8 9
######.##
####..##.
..#...#..
###...###
#....##.#
.##......
#.####..#
#.#######

出力例 3

これは小課題 2,3,4 の制約を満たします。

入力例 4

17 17
.####...#.....#.#
.#....#.#####...#
#...##.##...#..##
..#..####..#...##
.#..#..#.#.##...#
.#.#.#...#.##..#.
#...#..#..##..###
###.#..###..###..
...#.##.##.#....#
..####....#.#...#
.##...##.#.#...#.
..########...###.
#..##....#.......
##.##..###.#.##..
.##....#........#
....#####..##.#..
.###...##..##.#..

出力例 4

314465173

10^9+7 で割った余りを出力してください。

これは小課題 3,4 の制約を満たします。

入力例 5

22 18
.##.##.#.#.#...##.
####.#..###.#.#..#
#####.##...##.###.
...#.#.#.##.##.###
..#.##.#.#....#...
#.###.##....###..#
....#####...#...#.
.#..##..#..###....
....#..##.#.#..#.#
###.#.....#..##.#.
#..#..#.#.##..###.
#...#....##..###..
..#...#..###..##..
.#....#.#.#..###.#
##.#.#..#..###..##
....###.##.##.##..
#...####.#.#..##..
..#.###.###.###.##
#...##.#.#.#...#.#
#..###..########..
#.##.#####.#..#.##
#..#........#...#.

出力例 5

47296634

これは小課題 4 の制約を満たします。

Source Name

「競プロ典型90問」23日目

024 - Select +／- One（★2）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 2 点

問題文

長さ N の正整数列 A = (A_1, A_2, \ldots, A_N) および B = (B_1, B_2, \ldots, B_N) が与えられます。

次の操作をちょうど K 回行うことで A を B に一致させることができるか判定してください。

操作：1 \leq i \leq N を満たす i をひとつ選び A_i を A_i - 1 または A_i + 1 に置き換える

制約

1 \leq N \leq 1000
1 \leq K \leq 10^9
1 \leq A_i, B_i \leq 10^6 \ (1 \leq i \leq N)
入力は全て整数

入力

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

N K
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_N

出力

ちょうど K 回の操作で A を B に一致させることができる場合は Yes を、そうでない場合は No を出力してください。

入力例 1

2 5
1 3
2 1

出力例 1

Yes

たとえば、次のようにちょうど 5 回の操作で A を B に一致させることができます。

i = 1 を選び、A_1 を A_1 - 1 で置き換える。すると、A は (0, 3) になる
i = 2 を選び、A_2 を A_2 - 1 で置き換える。すると、A は (0, 2) になる
i = 2 を選び、A_2 を A_2 - 1 で置き換える。すると、A は (0, 1) になる
i = 1 を選び、A_1 を A_1 + 1 で置き換える。すると、A は (1, 1) になる
i = 1 を選び、A_1 を A_1 + 1 で置き換える。すると、A は (2, 1) になり、B に一致する

入力例 2

3 1
7 8 9
7 8 9

出力例 2

No

ちょうど 1 回操作をすると A は以下のいずれかになります。

(6, 8, 9)
(8, 8, 9)
(7, 7, 9)
(7, 9, 9)
(7, 8, 8)
(7, 8, 10)

これらは全て B に一致しないため No を出力してください。

入力例 3

7 999999999
3 1 4 1 5 9 2
1 2 3 4 5 6 7

出力例 3

Yes

Source Name

「競プロ典型90問」24日目

025 - Digit Product Equation（★7）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 7 点

問題文

関数 f(x) を次のように定義します。

f(x)=(x の各位の数字の積)

例えば f(777)=343、f(8691)=432、f(869120)=0 です。

整数 N と B が与えられるので、 1 以上 N 以下の整数 m の中で m-f(m) = B となるものの個数を求めてください。

制約

1 \leq N \lt 10^{11}
1 \leq B \lt 10^{11}
入力はすべて整数

入力

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

N B

出力

答えを出力してください。

入力例 1

999 434

出力例 1

m=574 と m=777 の 2 つが条件を満たします。

入力例 2

255 15

出力例 2

入力例 3

9999999999 1

出力例 3

Source Name

「競プロ典型90問」25日目

026 - Independent Set on a Tree（★4）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 4 点

問題文

N 頂点の木が与えられます。頂点には 1 から N までの番号が付けられており、i 番目の辺 (1 \leq i \leq N-1) は頂点 A_i と B_i を接続しています。

この木から、どの頂点も隣り合わないように、重複しない \frac{N}{2} 頂点を取り出してください。

制約

2 \leq N \leq 10^5
1 \leq A_i < B_i \leq N
N は偶数
入力は全て整数
与えられるデータは木である

入力

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

N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}

出力

1 行に空白区切りで、頂点番号を重複しないように \frac{N}{2} 個出力してください。

入力例 1

出力例 1

3 4

入力例 2

出力例 2

1 2 6

Source Name

「競プロ典型90問」26日目

027 - Sign Up Requests （★2）

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 2 点

問題文

低橋くんはプログラミングコンテストサイト「LowCoder」を作り、サービスを開始しました。
今日の時点では、LowCoder にはユーザはいません。

今日から数えて i (1 \leq i \leq N) 日後には、ユーザ名 S_i を希望するユーザが登録申請を行います。
申請を行った時点でユーザ名が S_i であるユーザが存在する場合、その登録申請は無視されます。
そのようなユーザが存在しない場合は登録申請が受理され、LowCoder にそのユーザが登録されます。

何日目の登録申請が受理されるかを求めてください。

制約

1 \leq N \leq 10^5
S_i (1 \leq i \leq N) は英小文字および数字からなる 1 文字以上 15 文字以下の文字列である。
- より正確には、S_i は正規表現 [a-z0-9]{1,15} で表せる文字列である。

入力

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

N
S_1
S_2
\vdots
S_N

出力

今日から数えて何日目に送られる登録申請が受理されるか、昇順 (値の小さい順) に出力してください。

入力例 1

5
e869120
atcoder
e869120
square1001
square1001

出力例 1

1
2
4

1 日目にはユーザ名 e869120 が申請され、このユーザ名のユーザはいないため、LowCoder に登録されます。
2 日目にはユーザ名 atcoder が申請され、このユーザ名のユーザはいないため、LowCoder に登録されます。
3 日目にはユーザ名 e869120 が申請されますが、このユーザ名のユーザは既に登録されているため、受理されません。
4 日目にはユーザ名 square1001 が申請され、このユーザ名のユーザはいないため、LowCoder に登録されます。
5 日目にはユーザ名 square1001 が申請されますが、このユーザ名のユーザは既に登録されているため、受理されません。

入力例 2

4
taro
hanako
yuka
takashi

出力例 2

受理されない登録申請が存在しない場合もあります。

入力例 3

10
square869120
square869120
square869120
square869120
square869120
square869120
square869120
square869120
square869120
square869120

出力例 3

S_i がすべて同じである可能性もあります。

Source Name

「競プロ典型90問」27問目

028 - Cluttered Paper（★4）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 4 点

問題文

二次元平面上に N 枚の長方形の紙があります。すべての紙は辺が x 軸または y 軸に平行になるように配置されており、i 枚目の紙の左下角の座標は (lx_i, ly_i) 、右上角の座標は (rx_i, ry_i) です。 k=1,2,3, \dots, N について、次の値を求めてください。

紙がちょうど k 枚重なっている部分の面積

制約

1 \leq N \leq 10^5
0 \leq lx_i \lt rx_i \leq 1000
0 \leq ly_i \lt ry_i \leq 1000
入力は全て整数

入力

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

N
lx_1 ly_1 rx_1 ry_1
lx_2 ly_2 rx_2 ry_2
\vdots
lx_N ly_N rx_N ry_N

出力

紙がちょうど k 枚重なっている部分の面積を A_k として、以下の形式で出力してください。

A_1
A_2
\vdots
A_N

入力例 1

2
1 1 3 2
2 1 4 2

出力例 1

2
1

紙が 1 枚重なっている部分の面積は 2、紙が 2 枚重なっている部分の面積は 1 です。

入力例 2

2
1 1 3 4
3 4 6 5

出力例 2

9
0

紙同士が重ならないことがあります。

入力例 3

20
61 98 76 100
70 99 95 100
10 64 96 91
12 37 99 66
63 93 65 95
16 18 18 67
30 47 88 56
33 6 38 8
37 19 40 68
4 56 12 84
3 16 92 78
39 24 67 96
46 1 69 57
40 34 65 65
20 38 51 92
5 32 100 73
7 33 92 55
4 46 97 85
43 18 57 87
15 29 54 74

出力例 3

Source Name

「競プロ典型90問」28日目

029 - Long Bricks（★5）

Time Limit: 4 sec / Memory Limit: 1024 MB

配点: 5 点

問題文

W 個の正方形のマスが左右に並んだ水平な部分があります。最初、すべての部分について、高さは 0 です。ここに高さ 1 の直方体のレンガを N 個、順番に積みます。高さ h の面に接着したレンガの上面の高さは h+1 になります。

i 番目に積むレンガは、左から L_i 番目から R_i 番目のマスをちょうど覆うように置きます。このとき、レンガが覆う範囲の中で最も高い水平な面で接着します。

各レンガについて、上面の高さを求めてください。

制約

2 \leq W \leq 5 \times 10^5
1 \leq N \leq 2.5 \times 10^5
1 \leq L_i \leq R_i \leq W (1 \leq i \leq N)
入力はすべて整数

小課題・得点

(1 点)： W \leq 9000,\ N \leq 9000
(1 点)： N \leq 9000
(3 点)：追加の制約はない。

入力

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

W N
L_1 R_1
L_2 R_2
\vdots
L_N R_N

出力

i (1 \leq i \leq N) 行目には、 i 番目に積むレンガの上面の高さを整数で出力してください。

入力例 1

出力例 1

i 番目に積むレンガをレンガ i と呼びます。
レンガ 1 は、マスの表面に接着するので、上面の高さは 1 です。
レンガ 2 は、レンガ 1 の上面に接着するので、上面の高さは 2 です。
レンガ 3 は、レンガ 1 の上面に接着するので、上面の高さは 2 です。
レンガ 4 は、レンガ 2 の上面に接着するので、上面の高さは 3 です。

入力例 2

出力例 2

i 番目に積むレンガをレンガ i と呼びます。
レンガ 1 は、マスの表面に接着するので、上面の高さは 1 です。
レンガ 2 は、レンガ 1 の上面に接着するので、上面の高さは 2 です。
レンガ 3 は、レンガ 2 の上面に接着するので、上面の高さは 3 です。
レンガ 4 は、レンガ 3 の上面に接着するので、上面の高さは 4 です。
レンガ 5 は、レンガ 3 の上面に接着するので、上面の高さは 4 です。

入力例 3

出力例 3

入力例 4

500000 7
1 500000
500000 500000
1 500000
1 1
1 500000
500000 500000
1 500000

出力例 4

※この入力例は小課題 2,3 のみの制約を満たします。

Source Name

「競プロ典型90問」29日目

030 - K Factors（★5）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 5 点

問題文

2 以上 N 以下の整数のうち、K 種類以上の素因数を持つものの個数を求めてください。

制約

2 \leq N \leq 10^7
1 \leq K \leq 8
入力は全て整数

入力

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

N K

出力

答えを出力してください。

入力例 1

15 2

出力例 1

例えば、4=2^2 は素因数を 1 種類持つため条件を満たさず、 6=2\times 3 は素因数を 2 種類持つため条件を満たします。

条件を満たすのは、6,10,12,14,15 の 5 個です。

入力例 2

30 2

出力例 2

条件を満たすのは、6,10,12,14,15,18,20,21,22,24,26,28,30 の 13 個です。

入力例 3

200 4

出力例 3

入力例 4

869120 1

出力例 4

入力例 5

10000000 3

出力例 5

Source Name

「競プロ典型90問」30日目

031 - VS AtCoder（★6）

Time Limit: 3 sec / Memory Limit: 1024 MB

配点: 6 点

問題文

あなたは、人気番組「VS AtCoder」に「チーム競技プログラマー」として参加しました。

この番組の最終ゲーム「リムービングストーン」のルールは、次の通りです。

ルール1　N 個の山が横一列に並んでいる。左から i 番目の山には、白石が W_i 個、青石が B_i 個ある。

ルール2　先攻から交互に、以下の操作を行わなければならない。

白石が 1 個以上または青石が 2 個以上ある石の山を 1 つ選び、次の操作のうちいずれか一方のみを行う。ただし、選んだ山にある白石と青石の個数をそれぞれ w, b とする。

[w \geq 1 のとき選択可能]　選んだ山に青石を w 個加え、白石を 1 個取り除く。

[b \geq 2 のとき選択可能]　1 以上 \lfloor \frac{b}{2} \rfloor 以下の整数 k を選び、選んだ山から青石を k 個取り除く。

ルール3　初めて操作を行えなくなった人が負けである。つまり、初めて「すべての山について、白石が 0 個かつ青石が 1 個以下」という状況で自分の番を迎えた人が負けである。

あなたはこの番組のレギュラーである E869120 と直接対決をします。ゲストの特権により、あなたは先攻か後攻かを選ぶことができます。そして、このゲームの勝敗が全体の勝敗に直結するため、あなたは絶対にこのゲームで勝つ必要があります。

両者が最善を尽くすとき、あなたが勝つためには先攻・後攻のどちらを選ぶべきでしょうか？

\lfloor x \rfloor について

\lfloor x \rfloor とは、x を超えない最大の整数を表します。
例えば、\lfloor 2.5 \rfloor = 2、\lfloor 3 \rfloor = 3、\lfloor 9.999999 \rfloor = 9 となります。

制約

1 \leq N \leq 10^5
0 \leq W_i, B_i \leq 50
(W_i, B_i) \neq (0,0)
入力される値は全て整数である

入力

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

N
W_1 W_2 \dots W_N
B_1 B_2 \dots B_N

出力

あなたが先攻を選ぶべきであるならば First 、後攻を選ぶべきであるならば Second と出力してください。

入力例 1

1
0
2

出力例 1

First

あなたが先攻を選んだ場合、最初の操作で唯一の山から青石を 1 個だけ取り除くことができます。この操作をすると、山の状態が「青石 1 個だけ」になり、E869120 が負け、あなたは勝ちます。よって、先攻を選ぶべきです。

入力例 2

2
10 10
10 10

出力例 2

Second

あなたが後攻を選んだ場合、毎回の自分の操作において、E869120 が直前に行った操作をもう一方の山に対して行うことによって、あなたは勝つことができます。よって、後攻を選ぶべきです。

入力例 3

1
1
1

出力例 3

Second

あなたは後攻を選ぶべきです。なぜなら、以下のようにしかゲームが進行し得ないからです。

E869120 が最初青石を 1 個加え、白石を 1 個取り除く
山の状態が「青石 2 個だけ」になる。そのとき、あなたは青石を 1 個取り除く操作しかできない。
すると、山の状態が「青石 1 個だけ」になり、E869120 は操作を行えなくなる。

入力例 4

6
3 1 4 1 5 9
2 7 1 8 2 8

出力例 4

Second

入力例 5

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

出力例 5

First

Source Name

「競プロ典型90問」31日目

032 - AtCoder Ekiden（★3）

Time Limit: 5 sec / Memory Limit: 1024 MB

配点: 3 点

問題文

ABC 陸上部には N 人の駅伝選手がいます。駅伝では 1 人の選手が 1 つの区を担当して走ります。複数の選手が 1 つの区を担当することや 1 人の選手が複数の区を担当することはできません。駅伝コースは第 1 区から第 N 区まであり、選手 i が第 j 区を走るのにかかる時間は A_{i, j} です。

駅伝は第 1 区、第 2 区、……、第 N 区の順にその区間を担当する選手が走ります。第 j 区 (1 \leq j \leq N - 1) を走り終わった選手は第 j + 1 区を走る選手にタスキを渡さなければいけません。このとき、タスキの受け渡しにかかる時間は十分短いため無視できます。最後にタスキを受けとった選手が第 N 区を走りゴールとなります。

さて、ABC 陸上部には M 個の噂があります。i 番目の噂は「選手 X_i と選手 Y_i は仲が悪い」というものです。噂をされている選手同士ではタスキの受け渡しができません。つまり、選手 X_i の直後に選手 Y_i が走ることも選手 Y_i の直後に選手 X_i が走ることもできません。

ABC 陸上部が駅伝でゴールするまでにかかる時間の最小値を求めてください。ただし、各選手が走る区間をどのように決めてもゴールできない場合、代わりに -1 を出力してください。

制約

1 \leq N \leq 10
1 \leq A_{i, j} \leq 1000 \ (1 \leq i \leq N, 1 \leq j \leq N)
0 \leq M \leq N(N - 1)/2
1 \leq X_i < Y_i \leq N \ (1 \leq i \leq M)
(X_i, Y_i) \neq (X_j, Y_j) \ (i \neq j)
入力は全て整数

入力

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

N
A_{1, 1} A_{1, 2} \cdots A_{1, N}
A_{2, 1} A_{2, 2} \cdots A_{2, N}
\vdots
A_{N, 1} A_{N, 2} \cdots A_{N, N}
M
X_1 Y_1
X_2 Y_2
\vdots
X_M Y_M

出力

ゴールするまでにかかる時間の最小値を出力してください。ただし、各選手が走る区間をどのように決めてもゴールできない場合 -1 を出力してください。

入力例 1

出力例 1

選手 1 が第 1 区を走り、選手 2 が第 3 区を走り、選手 3 が第 2 区を走ることで最小値 111 を達成できます。

入力例 2

4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
3
1 2
1 3
2 3

出力例 2

-1

入力例 3

出力例 3

Source Name

「競プロ典型90問」32日目

033 - Not Too Bright（★2）

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 2 点

問題文

E869120 くんは、冬に公開するイルミネーションを作成することを計画しています。
E869120 くんが計画しているイルミネーションは、縦 H \times 横 W の HW 個のLEDで構成されます。
イルミネーションの各 LED は、点灯・消灯の状態を任意に切り替えることができます。

このイルミネーションは、以下の条件を満たすとき 不適切である といいます。

イルミネーション全体に完全に含まれる縦 2 \times 横 2 の、4 つの LED を含む領域であって、点灯している LED が領域内に 2 つ以上あるものが存在する。

適切な（不適切な状態ではない）イルミネーションの点灯パターンのうち、点灯している LED の個数としてありうる最大値を求めてください。

制約

1 \leq H, W \leq 100
入力はすべて整数

入力

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

H W

出力

答えを出力してください。

入力例 1

2 3

出力例 1

点灯している LED を '#'、消灯している LED を '.' とすると、たとえば以下の状態が、適切である中で点灯している LED の個数が最大となります。

#.#
...

一方、以下の状態は不適切であるため、条件を満たしません。
上から 1 ～ 2 つ目、左から 1 ～ 2 つ目の LED からなる領域内に点灯している LED が 2 つ存在します。

#.#
.#.

入力例 2

3 4

出力例 2

たとえば以下の状態が、適切である中で点灯している LED の個数が最大となります。

#..#
....
#..#

入力例 3

3 6

出力例 3

Source Name

「競プロ典型 90 問」33 日目

034 - There are few types of elements（★4）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 4 点

問題文

長さ N の数列 a = (a_1, a_2, \ldots, a_N) と整数 K が与えられます。以下の条件を満たす 連続する 部分列のうち、最も長いものの長さを求めてください。

その部分列に含まれている要素は K 種類以下の値からなる。

制約

1 \leq K \leq N \leq 100{,}000
1 \leq a_i \leq 10^{9} (1 \leq i \leq N)
入力は全て整数

入力

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

N K
a_1 a_2 \ldots a_N

出力

答えを出力してください。

入力例 1

5 1
1 2 3 4 5

出力例 1

K = 1 であって、数列内の要素の値が全て異なるので、答えは 1 です。

入力例 2

5 4
1 1 2 4 2

出力例 2

K = 4 であって、数列内の要素の値は 3 種類であるので、全ての要素を含んだ区間が条件を満たします。

入力例 3

10 2
1 2 3 4 4 3 2 1 2 3

出力例 3

条件を満たす区間のなかで長さが最大のものは、区間 [3, 6] です。

Source Name

「競プロ典型90問」34日目

035 - Preserve Connectivity（★7）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点：7 点

問題文

N 頂点の木があり、頂点には 1, 2, \cdots, N と番号づけられています。i 番目 (1 \leq i \leq N-1) の辺は、頂点 A_i と B_i を結んでいます。

以下の形式の質問が Q 個与えられるので、j = 1, 2, \cdots, Q の順に答えてください。

N-1 本の辺のうち何本かを、残す辺として選ぶ。
選ばれなかった辺を削除したとき、頂点 V_{j,1},V_{j,2}, \cdots ,V_{j,K_j} すべてが互いに連結となるようにしたい。
最小で何本の辺を選ぶ必要があるか？

制約

2 \leq N \leq 100000
1 \leq A_i \lt B_i \leq N
1 \leq Q \leq 100000
2 \leq K_j \leq N
1 \leq V_{j,1} \lt V_{j,2} \lt \cdots \lt V_{j,K_j} \leq N
K_1 + K_2 + \cdots + K_Q \leq 200000
与えられるグラフは木である
入力はすべて整数

小課題・得点

(2 点)：N,Q \leq 5000
(1 点)：K_j = 2
(1 点)：K_j = 3
(3 点)：追加の制約はない。

入力

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

N
A_1 B_1
A_2 B_2
 \vdots 
A_{N-1} B_{N-1}
Q
K_1 V_{1,1} V_{1,2} ... V_{1,K_1}
K_2 V_{2,1} V_{2,2} ... V_{2,K_2}
 \vdots 
K_Q V_{Q,1} V_{Q,2} ... V_{Q,K_Q}

出力

j=1,2,...,Q に対し、j 行目に j 番目の質問に対する答えを出力してください。

入力例 1

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

出力例 1

1 番目の質問においては、頂点 1 と頂点 2 は 1 番目の辺によって隣接しているため、この辺のみを選べばよいです。
残りの質問についても同様に答えが導けます。

なお、この入力は小課題 1, 4 の制約を満たします。

入力例 2

出力例 2

この入力は小課題 1, 2, 4 の制約を満たします。

入力例 3

出力例 3

この入力は小課題 1, 3, 4 の制約を満たします。

Source Name

「競プロ典型90問」35日目

036 - Max Manhattan Distance（★5）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 5 点

問題文

二次元座標平面上に相異なる N 個の点 P_1, P_2, \ldots, P_N があり、点 P_i の座標は (x_i, y_i) です。

以下の Q 個のクエリを順に処理してください。

i (1 \leq i \leq Q) 番目のクエリでは、整数 q_i が与えられるので、点 P_{q_i} と N 個の点の間のマンハッタン距離の最大値を出力する。
つまり、点 P_s と点 P_t のマンハッタン距離を \rm{dist}(P_s, P_t) とするとき、\rm{max}(\rm{dist}(P_{q_i}, P_1), \cdots, \rm{dist}(P_{q_i}, P_N)) の値を出力する。

マンハッタン距離について

座標 (x_1, y_1) と座標 (x_2, y_2) の間のマンハッタン距離は、|x_1 - x_2| + |y_1 - y_2| で定義されます。

制約

2 \leq N \leq 100000
1 \leq Q \leq N
-10^9 \leq x_i, y_i \leq 10^9
(x_i, y_i) \neq (x_j, y_j) (1 \leq i < j \leq N)
1 \leq q_i \leq N (1 \leq i \leq Q)
q_i \neq q_j (1 \leq i < j \leq Q)
与えられる入力は全て整数

入力

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

N Q 
x_1 y_1
\vdots
x_N y_N
q_1
\vdots
q_Q

出力

与えられた Q 個のクエリに対する答えを改行で区切って 1 行ずつ出力してください。

入力例 1

出力例 1

6
7
7

1 番目のクエリでは点 1 に注目します。

点 1 と点 1 のマンハッタン距離は |-1 - (-1)| + |2 - 2| = 0
点 1 と点 2 のマンハッタン距離は |-1 - 1| + |2 - 1| = 3
点 1 と点 3 のマンハッタン距離は |-1 - (-2)| + |2 - (-3)| = 6

したがって、1 番目のクエリではこれらのマンハッタン距離の最大値である 6 を出力します。

入力例 2

出力例 2

8
4
8

入力例 3

2 1
-1000000000 -1000000000
1000000000 1000000000
1

出力例 3

4000000000

オーバーフローに注意してください。

Source Name

「競プロ典型90問」36日目

037 - Don't Leave the Spice（★5）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 5 点

問題文

香辛料を使う料理が N 種類あり、1 から N までの番号が付いています。

料理 i (1 \le i \le N) の価値は V_i で、作るときに香辛料を消費します。消費する香辛料の量は L_i [\mathrm{mg}] 以上 R_i [\mathrm{mg}] 以下の範囲で調節できます。

以下のことが実現可能かどうか判定し、可能な場合は作る料理の価値の合計としてあり得る最大の値を出力してください。

N 種類の料理から何種類かを選んで 1 つずつ 作ることで、香辛料を ちょうど W [\mathrm{mg}] 消費する。
ただし、上で述べたもの以外の手段で香辛料を消費することはできない。

制約

1 \leq W \leq 10^4
1 \leq N \leq 500
1 \leq L_i \leq R_i \leq W (1 \leq i \leq N)
1 \leq V_i \leq 10^9 (1 \leq i \leq N)
入力はすべて整数

入力

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

W N
L_1 R_1 V_1
L_2 R_2 V_2
\vdots
L_N R_N V_N

出力

作る料理の価値の合計としてあり得る最大値を出力してください。

香辛料をちょうど W [\mathrm{mg}] 消費することが不可能な場合は、 -1 を出力してください。

入力例 1

出力例 1

料理 1 、料理 3 、料理 4 を、それぞれ香辛料を \frac{100}{3} [\mathrm{mg}] ずつ消費して作ると、価値の合計は 120+1500+40=1660 になります。

入力例 2

100 4
13 15 31415
12 13 92653
29 33 58979
95 98 32384

出力例 2

-1

香辛料をちょうど 100 [\mathrm{mg}] 消費することは不可能です。

入力例 3

5000 5
1000 1000 1000000000
1000 1000 1000000000
1000 1000 1000000000
1000 1000 1000000000
1000 1000 1000000000

出力例 3

5000000000

入力例 4

10000 20
4539 6002 485976
1819 5162 457795
1854 2246 487643
1023 4733 393530
1052 6274 289577
1874 2436 167747
1457 4248 452660
2103 4189 174955
3057 5061 319316
4898 4953 394627
1313 2880 154687
1274 1364 259598
3866 5844 233027
1163 5036 386223
1234 4630 155972
2845 4978 442858
3168 5368 171601
3708 4407 394899
3924 4122 428313
2112 4169 441976

出力例 4

Source Name

「競プロ典型90問」37日目

038 - Large LCM（★3）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 3 点

問題文

正整数 A, B が与えられます。A と B の最小公倍数を求めてください。ただし、答えが 10^{18} を超える場合は Large と出力してください。

制約

1 \leq A, B \leq 10^{18}
入力は全て整数

入力

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

A B

出力

A と B の最小公倍数を出力してください。答えが 10^{18} を超える場合は代わりに Large と出力してください。

入力例 1

4 6

出力例 1

4 と 6 の最小公倍数は 12 です。
答えが 10^{18} を超えないので、12 を出力してください。

入力例 2

1000000000000000000 3

出力例 2

Large

10^{18} と 3 の最小公倍数は 3 \times 10^{18} です。
答えが 10^{18} を超えるので、Large と出力してください。

入力例 3

1000000000000000000 1

出力例 3

1000000000000000000

答えがちょうど 10^{18} の場合、そのまま出力することに注意してください。

Source Name

「競プロ典型90問」38日目

039 - Tree Distance（★5）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点：5 点

問題文

N 頂点の木が与えられます。木の頂点にはそれぞれ 1 から N までの番号が振られています。
i 番目の辺は、頂点 a_i と頂点 b_i を双方向に結んでおり、長さは全て 1 です。

{\displaystyle\sum_{u = 1}^{N - 1} \sum_{v = u + 1}^{N} \operatorname{dist}(u, v)}

の値を求めてください。

ただし、\operatorname{dist}(u,v) は、頂点 u から頂点 v までの最短距離とします。

制約

2 \leq N \leq 100000
1 \leq a_i, b_i \leq N
与えられるグラフは木である
入力は全て整数で与えられる

入力

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

N
a_1 b_1
a_2 b_2
:
a_{N - 1} b_{N - 1}

出力

答えを 1 行に出力してください。

入力例 1

2
1 2

出力例 1

\operatorname{dist}(1, 2) = 1 であるので、答えは 1 です。

入力例 2

出力例 2

\operatorname{dist}(1, 2) = 1
\operatorname{dist}(1, 3) = 1
\operatorname{dist}(1, 4) = 1
\operatorname{dist}(2, 3) = 2
\operatorname{dist}(2, 4) = 2
\operatorname{dist}(3, 4) = 2

であるので、これらを足し合わせた 9 が答えになります。　

入力例 3

出力例 3

Source Name

「競プロ典型90問」39日目

040 - Get More Money（★7）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 7 点

問題文

AtCoder 共和国には N 軒の家があり、1 から N までの番号が付けられています。

はじめ、家 i の中には、現金 A_i 円と、k_i 本の鍵（それぞれ家 c_{i,1}, c_{i,2}, \dots, c_{i,k_i} の鍵）が置いてあり、家に入ることでこれらを回収できます。ただし、任意の j (1 \leq j \leq k_i) に対して c_{i,j} \gt i が保証されます。

また、家 i に入るためには、以下の 2 つのことをする必要があります。

AtCoder 共和国の中に家 i の鍵があれば、それらをすべて回収した状態にする
料金 W 円を支払う

あなたは AtCoder 共和国の家にある現金を集めることで、できるだけ多くの金額を得ようと考えています。家に入る手順をうまく決めたときに、最大で何円得するかを求めてください。すなわち、家に入って回収した金額を I 円、家に入るために支払った料金を O 円として、I-O の最大値を求めてください。ただし、家に入るための費用は必要ならいつでも支払えるものとします。

制約

2 \leq N \leq 100
0 \leq W \leq 10^7
0 \leq A_i \leq 10^7
0 \leq k_i \leq N-i
i \lt c_{i,j} \leq N
c_{i,j} \neq c_{i,k} (j \neq k)
入力は全て整数

入力

入力は、以下の形式で与えられます。

N W
A_1 A_2 \cdots A_N
k_1 c_{1,1} c_{1,2} \cdots c_{1,k_1}
k_2 c_{2,1} c_{2,2} \cdots c_{2,k_2}
\vdots
k_N c_{N,1} c_{N,2} \cdots c_{N,k_N}

出力

最終的に得る金額の最大値を、一行に出力してください。

入力例 1

出力例 1

家 1,2,3 にこの順で入るのが最適で、5+2+10-3\times 5=2 円得られます。

入力例 2

6 10
8 6 9 1 2 0
1 3
2 3 4
1 5
1 5
1 6
0

出力例 2

どの家にも入らないのが最適な場合もあります。

Source Name

「競プロ典型90問」40日目

041 - Piles in AtCoder Farm（★7）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 7 点

問題文

AtCoder 農園には N 本の杭があり、 i 本目の杭は座標 (X_i,Y_i) のところに打たれています。

あなたはすべての杭を囲む塀を作り、塀の周上および内側にある全ての格子点に杭を打ちたいと思っています。

長い塀を作るのは疲れるので、すべての杭を囲むような塀のうち最も周の長さが短いものを作ります。

あなたが新しく打つ必要がある杭の本数を求めてください。

ただし、杭の太さや塀の厚さは無視できるものとします。

制約

3 \leq N \leq 10^5
0 \leq X_i,Y_i \leq 10^9\ (1\leq i\leq N)
i\neq j ならば (X_i,Y_i)\neq(X_j,Y_j)
入力は全て整数

小課題・得点

(2 点): N=3,X_i,Y_i\leq1000
(2 点): X_i,Y_i\leq1000
(3 点): 追加の制約はない。

入力

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

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

出力

あなたが打つことになる杭の本数を出力してください。

入力例 1

出力例 1

あなたが作ることになる塀は下の図のような形になります。
このとき塀の周の長さは 9\sqrt{2}+\sqrt{34}=18.5588\ldots で、これより短い塀ですべての杭を囲むことはできません。

新しく点 (2,4),(2,5),(3,3),(3,4),(3,5),(3,6),(4,3),(4,4),(4,5),(4,6),(4,7),(5,2),(5,3),(5,4),(5,5),(5,6),(5,7) に対応する 17 本の杭を打つことになるため、答えは 17 です。

入力例 2

出力例 2

1 本も新しい杭を打たなくてもいい場合もあります。

入力例 3

出力例 3

下の図のように、新たに 599 本の杭が必要になります。

入力例 4

出力例 4

この入力例は小課題 1 の制約を満たしませんが、小課題 2,3 の制約を満たします。
下の図のように、新たに 4828 本の杭が必要になります。

入力例 5

30
878317816 654163251
686185971 65193664
421988001 893301255
337790787 848308131
116633641 453711858
147679897 275450390
871549713 368160131
945135251 515070794
113677189 553747963
648722370 798825746
334960984 163211483
477414168 849868430
46724716 593116536
424597820 84043071
456749260 981436379
167906984 546584517
187306934 201207913
535850448 43428774
602081737 111568378
607467836 80430906
965538187 537789555
69199019 485172741
267885487 934316143
883812229 276272851
507976072 19708905
951100460 639017801
43859603 556279043
300658736 79240016
231304846 220059094
854667690 399502355

出力例 5

607281204170558988

この入力例は小課題 1,2 の制約を満たしませんが、小課題 3 の制約を満たします。
出力すべき値が 32 bit 整数に収まらない場合もあります。

Source Name

「競プロ典型90問」41日目

042 - Multiple of 9（★4）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点：4 点

問題文

0 以外の数字のみを使って書ける正の整数 X のうち、以下の条件をともに満たすものが何通りあるかを求め、 10^9 + 7 で割った余りを出力してください。

X は 9 の倍数
X を 10 進法で表したときの各桁の数字の和は K

制約

1 \leq K \leq 100000
K は整数

入力

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

出力

答えを 1 行に出力してください。

入力例 1

出力例 1

0 以外の数字のみを使って書ける正の整数のうち、各桁の数字の和が 1 になるのは 1 のみです。ここで、1 は 9 の倍数ではないため、条件を満たす整数 X はありません。よって、答えは 0 通りになります。

入力例 2

出力例 2

757186539

10^9 + 7 で割った余りを出力することに注意してください。

Source Name

「競プロ典型90問」42日目

043 - Maze Challenge with Lack of Sleep（★4）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 4 点

問題文

縦 H マス、横 W マスのグリッド状の迷路があり、上から i 行目・左から j 列目のマスを (i,j) とします。マス (i,j) は S_{i,j} = # のとき壁で、S_{i,j} = . のとき壁ではありません。

あなたは上下左右に隣接する壁でないマスへの移動を繰り返してマス (r_s,c_s) からマス (r_t,c_t) に移動したいです。ただし、移動する方向が変わる回数が多いと脳が疲れてしまうため好ましくありません。また、迷路の外へ出るような移動は許されません。

移動する方向が変わる回数の最小値を求めてください。

制約

2 \leq H,W \leq 1000
1 \leq r_s,r_t \leq H
1 \leq c_s,c_t \leq W
(r_s,c_s) \ne (r_t,c_t)
H,W,r_s,c_s,r_t,c_t は整数
S_{i,j} は # または .
S_{r_s,c_s},S_{r_t,c_t} は .
マス (r_s,c_s) からマス (r_t,c_t) への移動が可能

入力

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

H W
r_s c_s
r_t c_t
S_{1,1} S_{1,2} ... S_{1,W}
 \vdots 
S_{H,1} S_{H,2} ... S_{H,W}

出力

答えを出力してください。

入力例 1

3 3
1 1
3 3
..#
#.#
#..

出力例 1

最短路に沿って進むと、マス (1,2) とマス (3,2) で移動の方向が変わります。

入力例 2

3 3
2 1
2 3
#.#
...
#.#

出力例 2

入力例 3

4 6
2 1
1 5
...#..
.#.##.
.#....
...##.

出力例 3

Source Name

「競プロ典型90問」43日目

044 - Shift and Swapping（★3）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 3 点

問題文

長さ N の整数列 \{A_n\} が与えられます。以下の Q 個のクエリを順に処理してください。

T_i=1 のとき: 数列の第 x 項 (=A_x) の値と第 y 項 (=A_y) の値を入れ替える。
T_i=2 のとき: 数列を右方向にシフトする。すなわち、\{A_n\} = A_N, A_1, A_2, \cdots, A_{N-1} とする。
T_i=3 のとき: 数列の第 x 項 (=A_x) の値を求める。

制約

2 \leq N \leq 2 \times 10^5
1 \leq Q \leq 2 \times 10^5
1 \leq A_n \leq 10^9 (1 \leq n \leq N)
1 \leq T_i \leq 3 (1 \leq i \leq Q)
T_i = 1 ならば 1 \leq x_i, y_i \leq N かつ x_i \neq y_i
T_i = 2 ならば x_i=y_i=0
T_i = 3 ならば 1 \leq x_i \leq N かつ y_i=0
入力中の値はすべて整数である

入力

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

N Q
A_1 A_2 \cdots A_N
T_1 x_1 y_1
\vdots
T_Q x_Q y_Q

出力

T_i=3 であるクエリに対する答えを、与えられた順に改行区切りで出力してください。

入力例 1

8 5
6 17 2 4 17 19 1 7
2 0 0
1 7 2
1 2 6
1 4 5
3 4 0

出力例 1

最初、数列は 6, 17, 2, 4, 17, 19, 1, 7 です。
1 番目のクエリでは、数列を右方向にシフトします。この操作のあと、数列は 7, 6, 17, 2, 4, 17, 19, 1 となります。
2 番目のクエリでは、数列の第 7 項と第 2 項を入れ替えます。この操作のあと、数列は 7, 19, 17, 2, 4, 17, 6, 1 となります。
3 番目のクエリでは、数列の第 2 項と第 6 項を入れ替えます。この操作のあと、数列は 7, 17, 17, 2, 4, 19, 6, 1 となります。
4 番目のクエリでは、数列の第 4 項と第 5 項を入れ替えます。この操作のあと、数列は 7, 17, 17, 4, 2, 19, 6, 1 となります。
5 番目のクエリでは、数列の第 4 項の値 A_4=4 を出力します。

入力例 2

9 6
16 7 10 2 9 18 15 20 5
2 0 0
1 1 4
2 0 0
1 8 5
2 0 0
3 6 0

出力例 2

最初、数列は 16, 7, 10, 2, 9, 18, 15, 20, 5 です。
1 番目のクエリのあと、数列は 5, 16, 7, 10, 2, 9, 18, 15, 20 となります。
2 番目のクエリのあと、数列は 10, 16, 7, 5, 2, 9, 18, 15, 20 となります。
3 番目のクエリのあと、数列は 20, 10, 16, 7, 5, 2, 9, 18, 15 となります。
4 番目のクエリのあと、数列は 20, 10, 16, 7, 18, 2, 9, 5, 15 となります。
5 番目のクエリのあと、数列は 15, 20, 10, 16, 7, 18, 2, 9, 5 となります。
6 番目のクエリでは、数列の第 6 項の値 A_6=18 を出力します。

入力例 3

11 18
23 92 85 34 21 63 12 9 81 44 96
3 10 0
3 5 0
1 3 4
2 0 0
1 4 11
3 11 0
1 3 5
2 0 0
2 0 0
3 9 0
2 0 0
3 6 0
3 10 0
1 6 11
2 0 0
3 10 0
3 4 0
3 5 0

出力例 3

Source Name

「競プロ典型90問」44日目

045 - Simple Grouping（★6）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 6 点

問題文

ユークリッド平面上に、N 個の点 (X_1,Y_1), (X_2,Y_2), \cdots, (X_N,Y_N) があります。これらを、次の条件を満たすように K 個のグループに分けることを考えます。

複数のグループに入る点があってはならない。
どのグループにも属さない点があってはならない。
ひとつも点が属さないグループがあってはならない。

このとき、同一グループ内での 2 点間距離の最大値を最小化してください。ただし、ジャッジにはこのときの同一グループ内での 2 点間距離の最大値の 2 乗を 出力してください。

なお、このときの最大値を 2 乗した値は必ず整数になることが証明できます。

制約

2\leq K< N\leq 15
0\leq X_i,Y_i\leq 10^9
(X_i,Y_i)\neq (X_j,Y_j) (i\neq j)
入力は全て整数

入力

入力は、以下の形式で与えられます。

N K
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

出力

ありうるすべてのグループ分けの方法に対して、同一グループ内での 2 点間距離の最大値を計算したとき、その最小値 の 2 乗を 整数で 1 行に出力してください。

入力例 1

出力例 1

\{(0,1),(1,2)\}, \{(2,0)\} となるように分けると、同一グループ内での 2 点間距離の最大値は \sqrt 2 になってこれが最小なので、これを 2 乗した 2 を出力します。

入力例 2

出力例 2

\{(0,0),(0,2)\}, \{(1,1),(3,1)\}, \{(2,3)\} と分けると、距離の最大値が 2 の組が二つできて、その最大値は 2 です。

\{(0,0)\}, \{(0,2),(1,1)\}, \{(2,3),(3,1)\} などと分けることもできますが、この場合同一グループ内の 2 点間距離は \sqrt2 と \sqrt5 となります。

入力例 3

出力例 3

入力例 4

3 2
0 0
500000000 500000000
1000000000 1000000000

出力例 4

500000000000000000

Source Name

「競プロ典型90問」45日目

046 - I Love 46（★3）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 3 点

問題文

3 つの長さ N の数列 A = (A_1, A_2, \cdots, A_N), B = (B_1, B_2, \cdots, B_N), C = (C_1, C_2, \cdots, C_N) が与えられます。

A_i + B_j + C_k が 46 の倍数となるような (i, j, k) (1 \leq i,j,k \leq N) の選び方の総数を出力してください。

制約

1 \leq N \leq 10^5
0 \leq A_i, B_j, C_k \leq 10^9
入力は全て整数

入力

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

N
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_N
C_1 C_2 \cdots C_N

出力

答えを 1 行に出力してください。

入力例 1

出力例 1

A_i + B_j + C_k が 46 の倍数となる (i, j, k) の選び方は (1, 2, 1) (2, 1, 2) (2, 2, 3) の 3 つです。

入力例 2

出力例 2

どのような選び方をしても 3 つの整数の和が 46 の倍数になります。

入力例 3

20
238 395 46 238 264 114 354 52 324 14 472 64 307 280 209 24 165 194 179 248
270 83 377 332 173 21 362 75 66 342 229 117 124 481 48 235 376 13 420 74
175 427 76 278 486 169 311 47 348 225 41 482 355 356 263 95 170 156 340 289

出力例 3

Source Name

「競プロ典型90問」46日目

047 - Monochromatic Diagonal（★7）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 7 点

問題文

文字 'R','G','B' のみからなる、長さ N の文字列 S,T が与えられます。 S の i 文字目を s_i 、T の j 文字目を t_j とします。

N\times N のマス目があり、次の規則でマス目に色を塗ります。ここで、文字 'R','G','B' をそれぞれ赤色、緑色、青色に対応させます。

s_i=t_j のとき、上から i 行目、左から j 列目のマスを色 s_i で塗る。
s_i\neq t_j のとき、上から i 行目、左から j 列目のマスを赤、緑、青のうち s_i とも t_j とも異なる色で塗る。

このマス目には左上から右下に向かうような斜めの列は 2N-1 本あります。マス目が一色のみで塗られている列は何本あるか、求めてください。

より厳密に書くと、次のようになります。次の条件を満たす整数 k\ (-N<k<N) がいくつあるか求めてください。

ある色 c が存在して、1\leq i\leq N かつ 1\leq i+k\leq N が成り立つ任意の i について、マス (i,i+k) が色 c で塗られている。

制約

1 \leq N \leq 10^6
S,T は文字 'R','G','B' のみからなる

小課題・得点

(2 点): N\leq2000
(5 点): 追加の制約はない。

入力

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

N
S
T

出力

全てのマスが同じ色で塗られているような斜めの列の個数を一行に出力してください。

入力例 1

5
RGBGB
GRGRB

出力例 1

k=-4,-3,-1,2,3,4 の 6 つが条件を満たします。
例えば、k=-3 が条件を満たすことは、マス (4,1),(5,2) がどちらも緑色で塗られていることから確かめられます。

入力例 2

3
RRR
BBB

出力例 2

入力例 3

10
BGGGRBBGRG
RGBBRGRGGG

出力例 3

Source Name

「競プロ典型90問」47日目

048 - I will not drop out（★3）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 3 点

問題文

N 問からなる試験があります。i 番目の問題は満点が A_i 点、部分点が B_i 点です。ここで、部分点は満点より小さく満点の半分より大きいです。つまり \frac{A_i}{2} < B_i < A_i を満たします。

E869120 君はどの問題についても 1 分かけると部分点を取ることができ、さらに 1 分かけると満点を取ることができます。

試験時間 K 分間で E869120 君が得られる合計得点の最大値を求めてください。

制約

1 \leq N \leq 2 \times 10^5
1 \leq K \leq 2N
3 \leq A_i \leq 10^9 \ (1 \leq i \leq N)
\frac{A_i}{2} < B_i < A_i \ (1 \leq i \leq N)
入力は全て整数

入力

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

N K
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

E869120 君が K 分間で得られる合計得点の最大値を出力してください。

入力例 1

出力例 1

E869120 君は 3 問目に 2 分かけて満点 15 点を取り、4 問目に 1 分かけて部分点 6 点を取ることで、合計 21 点を得ることができます。

21 点より多く得点することはできないため、答えは 21 となります。

入力例 2

2 2
7 6
3 2

出力例 2

入力例 3

10 12
987753612 748826789
36950727 36005047
961239509 808587458
905633062 623962559
940964276 685396947
959540552 928301562
60467784 37828572
953685176 482123245
87983282 66762644
912605260 709048491

出力例 3

6437530406

Source Name

「競プロ典型90問」48日目

049 - Flip Digits 2（★6）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 6 点

問題文

E869120 君は、長さ N のビット列 S を持っています。最初、S の全ての文字は 0 です。

ABC 商店には M 個のアイテムが売られており、それぞれ 1 から M までの番号が振られています。アイテム i の価格は C_i 円であり、これを使うと S の L_i 〜 R_i 文字目が反転します。すなわち、S の L_i 〜 R_i 文字目のうち、0 であったものは 1 に、 1 であったものは 0 に変化します。

E869120 君は、M 個のアイテムのうちいくつかを選んで買うことで、次の条件が満たされるようにしたいです。

条件　どのような長さ N のビット列 T （全部で 2^N 通りあります）についても、「買ったアイテムから一つを選んで使う」操作を好きな回数（0 回でもよい）行うことで、S を T に一致させることができる

条件を満たすために、彼が買う必要のあるアイテムの合計価格の最小値を求めてください。

ただし、全てのアイテムを買っても条件を満たせない場合は、その旨を報告してください。

制約

1 \leq N \leq 10^5
1 \leq M \leq 10^5
1 \leq C_i \leq 10^9
1 \leq L_i \leq R_i \leq N
入力は全て整数

入力

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

N M
C_1 L_1 R_1
C_2 L_2 R_2
\vdots
C_M L_M R_M

出力

全てのアイテムを買っても条件を満たせない場合は、-1 を出力してください。

そうでない場合は、条件を満たすために E869120 君が買う必要のあるアイテムの合計価格の最小値を出力してください。

入力例 1

出力例 1

アイテム 1, 2 を買った場合を考えましょう。

各 T に対して、例えば次のように操作を行うと S を T に一致させることができます。

T= 00 のとき：何も操作を行わない
T= 01 のとき：アイテム 2 を使う
T= 10 のとき：アイテム 1 を使う
T= 11 のとき：アイテム 1 を使い、その後アイテム 2 を使う

そのとき、合計価格は 1 + 1 = 2 円であり、これが最小となります。

入力例 2

出力例 2

アイテム 1, 3 を買った場合を考えましょう。

各 T に対して、例えば次のように操作を行うと S を T に一致させることができます。

T= 00 のとき：何も操作を行わない
T= 01 のとき：アイテム 3 を使い、その後アイテム 1 を使う
T= 10 のとき：アイテム 1 を使う
T= 11 のとき：アイテム 3 を使う

そのとき、合計価格は 1 + 1 = 2 円であり、これが最小となります。

入力例 3

出力例 3

-1

(L_i,R_i) が同じアイテムが複数個含まれていることもあります。

入力例 4

出力例 4

Source Name

「競プロ典型90問」49日目

050 - Stair Jump（★3）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点：3 点

問題文

E869120 君は、N 段の階段を上ろうとしています。彼は一歩で 1 段か L 段上ることができます。

0 段目から出発し、N 段目にたどり着くまでの移動方法が何通りあるかを求め、10^9 + 7 で割った余りを出力してください。

制約

2 \leq N \leq 100000
2 \leq L \leq 100000
入力は全て整数

入力

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

N L

出力

答えを 1 行に出力してください。

入力例 1

3 2

出力例 1

移動方法は、以下のような 3 通りの方法があります。

1 段上る → 1 段上る → 1 段上る
1 段上る → 2 段上る
2 段上る → 1 段上る

入力例 2

4 4

出力例 2

1 段ずつ上る方法と、一気に 4 段を上る方法があります。

入力例 3

5 2

出力例 3

入力例 4

6783 125

出力例 4

674508908

10^9 + 7 で割った余りを出力することに注意してください。

Source Name

「競プロ典型90問」50日目

051 - Typical Shop（★5）

Time Limit: 3 sec / Memory Limit: 1024 MB

配点: 5 点

問題文

典型商店には N 個の区別できる品物があります。品物には 1, 2, \cdots, N と番号が付けられており、品物 i の値段は A_i 円です。

あなたは商店に売られている品物からちょうど K 個を選んで、値段の合計が P 円以下となるように買い物をしたいです。あり得る品物の選び方は何通りあるでしょうか？

なお、2 通りの品物の選び方は、ある品物 i があって、品物 i が一方では選ばれており他方では選ばれていないときに区別されます。

制約

1 \leq K \leq N \leq 40
1 \leq P \leq 10^{18}
1 \leq A_i \leq 10^{16} (1 \leq i \leq N)
入力は全て整数

入力

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

N K P
A_1 A_2 \ldots A_N

出力

答えを出力してください。

入力例 1

5 2 10
3 8 7 5 11

出力例 1

ちょうど 2 個を選び、値段の合計が 10 円以下となるような品物の選び方は、以下の 2 通りです。

品物 1 と品物 3 を選ぶ
品物 1 と品物 4 を選ぶ

入力例 2

5 1 10
7 7 7 7 7

出力例 2

品物は、同じ値段であったとしても区別されることに注意してください。

入力例 3

40 20 100
1 3 1 3 4 1 3 5 5 3 3 4 1 5 4 4 3 1 3 4 1 3 2 4 4 1 5 2 5 3 1 3 3 3 5 5 5 2 3 5

出力例 3

137846528820

答えが 32 bit 整数に収まらないことがあることに注意してください。

Source Name

「競プロ典型90問」51日目

052 - Dice Product（★3）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 3 点

問題文

N 個の 6 面体サイコロがあり、1, 2, 3, \cdots, N と番号付けられています。サイコロ i の j (1 \leq j \leq 6) 番目の面には整数 A_{i,j} が書かれています。ここで、それぞれのサイコロについて、書かれている整数は相異なります。

さて、サイコロの出目に対して、次のように得点を定義します。

得点は N 個のサイコロの出目の総積である。つまり、サイコロ i の出目を R_i としたとき、得点は R_1 \times R_2 \times \dots \times R_N と計算される。

N 個のサイコロの出目の結果としては 6^N 通り考えられますが、これら全てにおける得点の総和 S を 10^9 + 7 で割った余りを求めてください。ただし、それぞれのサイコロは互いに区別できるものとします。

制約

1 \leq N \leq 100
1 \leq A_{i,1} < A_{i,2} < A_{i,3} < A_{i,4} < A_{i,5} < A_{i,6} \leq 100
入力はすべて整数である

入力

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

N
A_{1,1} A_{1,2} A_{1,3} A_{1,4} A_{1,5} A_{1,6}
\vdots
A_{N,1} A_{N,2} A_{N,3} A_{N,4} A_{N,5} A_{N,6}

出力

S を 10^9+7 で割った余りを出力してください。

入力例 1

2
1 2 3 5 7 11
4 6 8 9 10 12

出力例 1

例えば、出目が 3, 10 だった場合の得点は 3 \times 10=30 より、 30 です。サイコロの出目の結果は 6^2=36 通り考えられ、全ての得点の総和は 1421 です。

入力例 2

1
11 13 17 19 23 29

出力例 2

サイコロが 1 つだけの場合の答えは、唯一のサイコロの各面に書かれている整数の総和になります。

入力例 3

7
19 23 51 59 91 99
15 45 56 65 69 94
7 11 16 34 59 95
27 30 40 43 83 85
19 23 25 27 45 99
27 48 52 53 60 81
21 36 49 72 82 84

出力例 3

670838273

S=211411531150718976 ですが、出力すべき答えは S を 10^9+7 で割った余りである 670838273 であることに注意してください。

Source Name

「競プロ典型90問」52日目

053 - Discrete Dowsing（★7）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 7 点

問題文

これはインタラクティブな問題です。

T 個のテストケースに対して、以下の問題を解いてください。

長さ N の非負整数列 A = (A_1, A_2, \cdots, A_N) と整数 k (1 \le k \le N) が隠されている。数列 A は以下の条件を満たすことが分かっている。

1 \le i \le k-1 のとき A_i \lt A_{i+1}

k \le i \le N-1 のとき A_i \gt A_{i+1}

整数 N が与えられた後、あなたはクエリを何回か送ることができる。 1 回のクエリでは、 1 \le i \le N なる i を 1 つ指定して A_i の値を得ることができる。できるだけ少ない回数のクエリで数列 A の最大値を求めよ。（詳しくは小課題・得点の項を参照）

制約

1 \leq T \leq 50
1 \leq N \leq 1500
0 \leq A_i \leq 10^9 (1 \leq i \leq N)
入力はすべて整数

小課題・得点

この問題に正解した場合の得点は、以下のように計算されます。

各テストケースに対するクエリの数の最大値を Q_{\mathrm{max}} とします。

1500 \lt Q_{\mathrm{max}} のとき 0 点
40 \lt Q_{\mathrm{max}} \leq 1500 のとき 1 点
22 \lt Q_{\mathrm{max}} \leq 40 のとき 3 点
15 \lt Q_{\mathrm{max}} \leq 22 のとき 4 点
Q_{\mathrm{max}} \leq 15 のとき 7 点

入出力

最初に、テストケースの数 T が与えられます。

以降、 T 個のテストケースが続きます。

テストケースの最初では、次の形式で入力が与えられます。

クエリを送るには、以下の形式で出力してください。

? i

このクエリに対して、次の形式で返答が与えられます。

A_i

数列 A の最大値を答えるときは、その値を A_{\mathrm{max}} として次の形式で出力してください。

! A_{\mathrm{max}}

その後、次のテストケースがあれば続けて処理し、なければすぐにプログラムを終了してください。

プログラムが正しくないクエリを出力した場合は、 -1 が入力に与えられます。この場合はすぐにプログラムを終了してください。

注意

この問題のジャッジはアダプティブです。つまり、これまでのクエリの内容に矛盾しない限り、数列の内容が変更される場合があります。
すべてのテストケースで答えを出力した後、または -1 が与えられた後、プログラムをすぐに終了しなかった場合、採点結果は定義されません。
出力のたびに標準出力を flush してください。そうしない場合、TLE の可能性があります。
AtCoder の仕様上、1 点以上を取れば AC と表示されることにご注意ください。（AC でも満点ではない場合があります）

入出力例1

入力	出力	説明
`1`		`T=1`
`8`		`1` つ目のテストケースについて、 `N=8`
	`? 6`
`6`		`A_6=6`
	`? 7`
`9`		`A_7=9`
	`? 8`
`1`		`A_8=1`
	`! 9`

数列 A は (1, 2, 3, 4, 5, 6, 9, 1) で、 k = 7 です。数列 A の最大値は 9 です。

例えば、 1 回目のクエリ終了時点では (7, 8, 9, 8, 7, 6, 5, 4) を数列 A としてもクエリの内容に矛盾しないので、この数列に変更される可能性があります。

入出力例2

入力	出力	説明
`2`		`T=2`
`1`		`1` つ目のテストケースについて、 `N=1`
	`? 1`
`0`		`A_1=0`
	`! 0`
`1`		`2` つ目のテストケースについて、 `N=1`
	`? 1`
`1000000000`		`A_1=1000000000`
	`! 1000000000`

Source Name

「競プロ典型90問」53日目

054 - Takahashi Number（★6）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 6 点

問題文

研究者の高橋氏は多くの共著論文を執筆したということから、関係者によって敬意とユーモアの意味を込めて高橋数という概念が作り出されました。高橋数は以下のように、各研究者に対して定められます。

高橋氏の高橋数は 0 である。
高橋数が n の研究者との共著経験があり、高橋数が n 未満の研究者との共著経験がない研究者の高橋数は n+1 とする。
上記の事項によって高橋数が決まらなかった研究者については、高橋数は定義されない。

現在、この世界には高橋氏を含める N 人の研究者について、 M 個の共著論文があり、 i 番目の共著論文は K_i 人の研究者 R_{i,1}, \dots, R_{i,K_i} による共著です。ここで、高橋氏は研究者 1 であるとします。このとき、 N 人の研究者それぞれについて高橋数は定義されているでしょうか？もし定義されているならば、その値はいくつでしょうか？

制約

2 \leq N \leq 10^5
1 \leq M \leq 10^5
2 \leq K_i \leq N
K_1+K_2+\dots+K_M \leq 2 \times 10^5
1 \leq R_{i,1} < \dots < R_{i,K_i} \leq N
入力される値は全て整数である

入力

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

N M
K_1
R_{1,1} \cdots R_{1,K_1}
\vdots
K_M
R_{M,1} \cdots R_{M,K_M}

出力

出力は N 行からなる。j 行目 (1 \leq j \leq N) には研究者 j の高橋数が存在するならば、その高橋数を、存在しないならば、 -1 を出力せよ。

入力例 1

出力例 1

6 人の高橋数はそれぞれ以下のようにして求められます。

研究者 1 (高橋氏) の高橋数は定義より 0 です。
研究者 2,3 は高橋数が 0 である研究者 1 との共著経験があり、高橋数 0 未満の研究者との共著経験がないので、高橋数は 1 になります。
研究者 4 は高橋数が 1 である研究者 3 との共著経験があり、高橋数 1 未満の研究者との共著経験がないので、高橋数は 2 になります。
研究者 5,6 はそれぞれ共著経験がありますが、高橋数が定義されている研究者との共著経験がないので、高橋数は定義されません。

以上から、研究者 1 から順に高橋数は 0,1,1,2,\times,\times (\times は高橋数が存在しないことを表します) になります。

入力例 2

出力例 2

入力例 3

4 1
3
2 3 4

出力例 3

0
-1
-1
-1

入力例 4

出力例 4

Source Name

「競プロ典型90問」54日目

055 - Select 5（★2）

Time Limit: 5 sec / Memory Limit: 1024 MB

配点: 2 点

問題文

N 個の整数 A_1, A_2, \cdots, A_N があります。この中から 5 個を選ぶ方法のうち、これら 5 個の整数の積を P で割ると Q 余るようなものが何通りあるか求めてください。

制約

5\leq N\leq 100
0\leq A_i\leq 10^9
0\leq Q < P\leq 10^9
入力はすべて整数

入力

入力は、以下の形式で与えられます。

N P Q
A_1 A_2 A_3 \cdots A_N

出力

この問題の答えを 1 行に出力してください。

入力例 1

6 7 1
1 2 3 4 5 6

出力例 1

A_1,A_2,A_3,A_4,A_5 を選んだときのみ、積を 7 で割った余りが 1 になります。

入力例 2

10 1 0
0 0 0 0 0 0 0 0 0 0

出力例 2

Source Name

「競プロ典型90問」55日目

056 - Lucky Bag（★5）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 5 点

問題文

デパートの高橋屋では、N 日にわたって初売りが行われます。
i (1 \leq i \leq N) 日目には、A_i 円の福袋 A と B_i 円の福袋 B が売られます。

低橋くんは N 日間、毎日高橋屋に通って福袋 A または福袋 B のいずれかを購入します。（なにも購入しないことはできません。）
N 日間で購入した N 個の福袋の総額がちょうど S 円になるように購入したいです。

低橋くんは計算が苦手なので、あなたが代わりに条件を満たす福袋の購入の計画を立ててください。
そのような購入の計画が存在しない場合は、それを報告してください。

制約

1 \leq N \leq 100
1 \leq S \leq 10^5
1 \leq A_i, B_i \leq 10^5 (1 \leq i \leq N)
入力中の値はすべて整数

入力

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

N S
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

問題文の条件を満たす購入の計画を、以下のような N 文字の文字列 T で表して出力してください。

i (1 \leq i \leq N) 日目に福袋 A を購入する場合は T_i= 'A'、福袋 B を購入する場合は T_i= 'B'

条件を満たす購入の計画が存在しない場合は 'Impossible' と出力してください。

入力例 1

出力例 1

BAB

以下のように購入すると、総額が 14+15+5=34 円となります。

1 日目に福袋 B (14 円)
2 日目に福袋 A (15 円)
3 日目に福袋 B (5 円)

入力例 2

出力例 2

BABBA

このような買い方をすると、総額が 16+3+9+26+23=77 円となります。
このほかに、BAAAB でも総額が 16+3+43+4+11=77 円となるため正解となります。

入力例 3

出力例 3

Impossible

条件を満たすような買い方が存在しない場合もあります。

Source Name

「競プロ典型 90 問」56 日目

057 - Flip Flap（★6）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 6 点

問題文

1, 2, \dots, M と番号付けられた M 枚のパネルがあり、全てのパネルは最初裏向きです。また、あなたの前には 1, 2, \dots, N と番号付けられた N 個のスイッチがあります。スイッチ i を押すことにより、以下のことが起こります。

T_i 枚のパネル A_{i,1} ,\dots, A_{i,T_i} が裏返り、表裏が変わる。

ここで、一度押したスイッチは二度と押すことができません。

あなたの仕事はこの M 枚のパネルの表裏を希望通りにすることです。なお、希望は長さが M の 0, 1 からなる列 S で与えられ、S_j=0 は、パネル j を裏に、S_j=1 はパネル j を表にすることを意味します。

ボタンの押し方は押す順番を考慮しないと 2^N 通りありますが、このうち希望を満たすボタンの押し方は何通りでしょうか。ただし、解答は非常に大きくなる可能性があるので、 998244353 で割った余りを出力してください。

制約

1 \leq N,M \leq 300
1 \leq T_i \leq M
1 \leq A_{i,1} < \dots < A_{i,T_i} \leq M
S_i=0 または S_i=1
入力は全て整数である

入力

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

N M
T_1
A_{1,1} \cdots A_{1,T_1}
\vdots
T_N
A_{N,1} \cdots A_{N,T_N}
S_1 \cdots S_M

出力

希望を満たすようなボタンの押し方の場合の数を 998244353 で割った余りを出力せよ。

入力例 1

出力例 1

スイッチ 1 とスイッチ 2 のボタンを押すことによって、 3 枚のパネルの表裏を希望通りにすることができます。また、これ以外に 3 枚のパネルを希望通りにすることはできないので、答えは 1 通りです。

入力例 2

出力例 2

パネル 3 の表裏を変えるスイッチが存在しないので、パネル 3 を表にすることはできません。よって、答えは 0 通りです。

入力例 3

出力例 3

2 枚のパネルを希望通りにするためのスイッチのボタンの押し方は以下の 2 通りあります。

スイッチ 1 のボタンのみを押す。
スイッチ 1, 2, 3 の全てのボタンを押す。

入力例 4

13 6
3
1 3 5
3
1 4 5
4
3 4 5 6
2
2 5
4
1 2 3 5
3
3 4 6
3
4 5 6
6
1 2 3 4 5 6
4
1 3 5 6
3
1 2 4
3
1 5 6
4
1 2 3 4
1
5
1 0 0 1 0 0

出力例 4

Source Name

「競プロ典型90問」57日目

058 - Original Calculator（★4）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 4 点

問題文

あなたは奇妙な電卓を持っています。この電卓は 0 以上 10^5-1 以下の整数を 1 つ表示できます。この電卓には ボタンA と呼ばれるボタンがあります。整数 x が表示されているときにボタンA を 1 回押すと、次の処理が順番に行われます。

x を十進法で表したときの各桁の和を計算し、 y とする。
x+y を 10^5 で割ったあまりを計算し、 z とする。
表示されている整数を z に変更する。

例えば、 99999 が表示されているときにボタンA を 1 回押すと、 99999+(9+9+9+9+9)=100044 なので、表示される整数は 44 に変更されます。

今、この電卓に N が表示されています。ボタンA を K 回押した後に表示されている整数を求めて下さい。

制約

0 \leq N \leq 10^5-1
1 \leq K \leq 10^{18}
入力はすべて整数

入力

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

N K

出力

ボタンA を K 回押した後に表示されている整数を出力してください。

入力例 1

5 3

出力例 1

1 回目にボタンA を押した後に表示される整数は 5+(5)=10 です。
2 回目にボタンA を押した後に表示される整数は 10+(1+0)=11 です。
3 回目にボタンA を押した後に表示される整数は 11+(1+1)=13 です。

入力例 2

0 100

出力例 2

0 が表示されているときにボタンA を押しても、表示される整数は 0 のままです。

入力例 3

99999 1000000000000000000

出力例 3

Source Name

「競プロ典型90問」58日目

059 - Many Graph Queries（★7）

Time Limit: 3 sec / Memory Limit: 1024 MB

配点: 7 点

問題文

N 頂点 M 辺の有向グラフが与えられます。このグラフにおいて、辺 i は頂点 X_i から Y_i に向かいます。

Q 個の、次の形式のクエリに答えてください。

クエリ j: 頂点 A_j から B_j まで、辺を向きのとおりに通って移動することは可能か？

制約

2\leq N\leq 10^5
1\leq M\leq 10^5
1\leq Q\leq 10^5
1\leq X_i < Y_i\leq N
1\leq A_j < B_j\leq N
入力はすべて整数

小課題

(2 点): N,M,Q\leq 2000
(5 点): 追加の制約はない。

入力

入力は、以下の形式で与えられます。

N M Q
X_1 Y_1
X_2 Y_2
\vdots
X_M Y_M
A_1 B_1
A_2 B_2
\vdots
A_Q B_Q

出力

j 行目には、頂点 A_j から B_j まで移動可能なら Yes を、そうでなければ No を出力してください。

入力例 1

出力例 1

Yes
Yes
No

1,2 番目のクエリでは、2\rightarrow4\rightarrow6, 1\rightarrow5 と移動できます。 3 番目のクエリでは、移動不可能です。

入力例 2

出力例 2

Yes
No

グラフは単純とは限りません。

入力例 3

2 1 1
1 2
1 2

出力例 3

Yes

Source Name

「競プロ典型90問」59日目

060 - Chimera（★5）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 5 点

問題文

長さ N の数列 A = (A_1,A_2, \cdots , A_N) が与えられます。
A の（連続とは限らない）部分列 B=(B_1,B_2, \cdots , B_M) であって、次の条件を満たすものを考えます。

条件　ある整数 K(1 \leq K \leq M) が存在して、以下の条件をともに満たす

1 \leq j \lt K を満たす全ての j に対し、B_j \lt B_{j+1} が成立する

K \leq j \lt M を満たす全ての j に対し、B_j \gt B_{j+1} が成立する

B の要素数 M として考えられる最大値を求めてください。

制約

1 \leq N \leq 300000
1 \leq A_i \leq N
入力は全て整数

入力

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

N
A_1 A_2  \cdots  A_N

出力

答えを出力してください。

入力例 1

6
1 2 3 3 2 1

出力例 1

A_1,A_2,A_3,A_5,A_6 から B を得ると B = (1,2,3,2,1) となります。
これは K=3 とすると条件を満たす部分列であり、要素数は 5 です。
これよりも要素数の多い部分列であって条件を満たすものは存在しないため、答えは 5 になります。

入力例 2

4
1 2 3 4

出力例 2

入力例 3

5
3 3 3 3 3

出力例 3

Source Name

「競プロ典型90問」60日目

061 - Deck（★2）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 2 点

問題文

あなたはカードを整理するために 1 つの山札を作ります。最初、山札にカードは 1 枚もありません。

これから Q 個の操作を行います。i 番目 (1 \leq i \leq Q) の操作では以下を行います：

t_i = 1 のとき、整数 x_i が書かれたカードを山札の一番上にいれる
t_i = 2 のとき、整数 x_i が書かれたカードを山札の一番下にいれる
t_i = 3 のとき、山札の上から x_i 番目のカードに書かれた数を紙に書き出す

t_i = 3 の操作で書き出された整数を操作順に出力するプログラムを書いてください。

制約

2 \leq Q \leq 10^5
1 \leq t_i \leq 3
t_i = 1, 2 のとき 1 \leq x_i \leq 10^9
t_i = 3 のとき 1 \leq x_i \leq k_i（k_i は 1 \leq j \leq i かつ t_j = 1, 2 を満たす j の個数）
t_i = 1, 2 を満たす i が少なくとも 1 つ存在する
t_i = 3 を満たす i が少なくとも 1 つ存在する
与えられる入力は全て整数

入力

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

Q
t_1 x_1
t_2 x_2
:
t_Q x_Q

出力

与えられた Q 個の操作のうち t_i = 3 の操作で書き出した整数を順に、改行で区切って 1 行ずつ出力してください。

入力例 1

出力例 1

1
2
3

山札は各操作の後に次の状態になります。

1 番目の操作の直後：カードに書かれた整数は上から順に (2) である
2 番目の操作の直後：カードに書かれた整数は上から順に (1, 2) である
3 番目の操作以降：カードに書かれた整数は上から順に (1, 2, 3) である

したがって、書き出された数は順番に 1、2、3 となります。

入力例 2

出力例 2

1
1
1

カードを山札の一番下にいれる操作のみを行います。
最初、1 が書かれたカードを山札にいれるので、t_i = 3 で書き出す数は常に 1 となります。　

入力例 3

6
1 1000000000
2 200000000
1 30000000
2 4000000
1 500000
3 3

出力例 3

1000000000

Source Name

「競プロ典型90問」61日目

062 - Paint All（★6）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 6 点

問題文

N 個の白いボールと N 個のアイテムがあります。ボールとアイテムにはそれぞれ 1 から N までの番号がついています。
ここで、アイテム i について以下のことがわかっています。

ボール A_i, B_i の少なくとも一方が白である時、またその時に限り使える。
これを使うと、ボール i を黒く塗ることができる。

N 個のアイテムを適切な順序で使うことで、全てのボールを黒く塗ることが可能かどうかを判定してください。
可能な場合は使う順序の一例を求めてください。

制約

1 \leq N \leq 10^5
1 \leq A_i, B_i \leq N
入力は全て整数

入力

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

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

全てのボールを黒く塗ることが不可能ならば、-1 を出力してください。
可能ならば、次の形式で出力してください。

X_1
X_2
\vdots
X_N

X_i は i 番目に使うアイテムの番号を表します。
ここで、1 \le X_i \le N, X_i \neq X_j\ (i \neq j) かつ X_i は全て整数である必要があります。

アイテムを使う順序が複数考えられる場合、そのうちのどれを出力しても構いません。

入力例 1

出力例 1

この出力例が正しい出力であることを示します：

ボール 2\ (=A_4) およびボール 1\ (=B_4) は白であるため、アイテム 4 によってボール 4 を黒く塗ることができる。
ボール 1\ (=A_2) およびボール 3\ (=B_2) は白であるため、アイテム 2 によってボール 2 を黒く塗ることができる。
ボール 4\ (=B_1) は黒ですが、ボール 3\ (=A_1) が白であるため、アイテム 1 によってボール 1 を黒く塗ることができる。
ボール 2\ (=A_3) は黒ですが、ボール 3\ (=B_3) が白であるため、アイテム 3 によってボール 3 を黒く塗ることができる。

このようにして、全てのボールを黒く塗ることができました。操作によって A_i,B_i がどちらも黒くなったとしても、操作前にどちらかが白であれば良いことに注意してください。

他には、4,1,2,3 の順でアイテムを使用しても良いです。

入力例 2

出力例 2

3
2
1

どのような順序でアイテムを使用しても良いです。

なお、この問題では A_i = B_i となり得ることに注意してください。

入力例 3

出力例 3

-1

どのようにしても、全てのボールを黒く塗ることはできません。

入力例 4

出力例 4

この出力例が唯一の正答です。

入力例 5

出力例 5

-1

Source Name

「競プロ典型90問」62日目

063 - Monochromatic Subgrid（★4）

Time Limit: 4 sec / Memory Limit: 1024 MB

配点: 4 点

問題文

縦 H 行、横 W 列のグリッドがあり、上から i 行目、左から j 列目のマスを (i, j) で表します。マス (i, j) には整数 P_{i, j} が書かれています。

さて、このグリッドから（連続するとは限らない）1 つ以上の行と 1 つ以上の列を選ぶことでできる「部分グリッド」であって、次の条件を満たすものを良い部分グリッドと呼びます。

条件　選んだ行を i_1, i_2, \dots, i_A \ (1 \leq i_1 < i_2 < \dots < i_A \leq H) とし、選んだ列を j_1, j_2, \dots, j_B \ (1 \leq j_1 < j_2 < \dots < j_B \leq W) とすると、マス (i_a, j_b) \ (1 \leq a \leq A, 1 \leq b \leq B) に書かれている整数はすべて同じである。

良い部分グリッドの大きさとしてあり得る最大値を求めてください。
ただし A 個の行・B 個の列からなる部分グリッドの大きさは A \times B であるとします。

制約

1 \leq H \leq 8
1 \leq W \leq 10000
1 \leq P_{i, j} \leq HW
入力は全て整数

入力

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

H W
P_{1, 1} P_{1, 2} \cdots P_{1, W}
P_{2, 1} P_{2, 2} \cdots P_{2, W}
\vdots
P_{H, 1} P_{H, 2} \cdots P_{H, W}

出力

良い部分グリッドの大きさとしてあり得る最大値を出力してください。

入力例 1

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

出力例 1

\{2, 3\} 行目と \{2, 3, 5\} 列目を選ぶことでできる大きさ 6 の部分グリッドは、次のように全てのマスに 2 が書かれています。

. . . . . .
. 2 2 . 2 .
. 2 2 . 2 .
. . . . . .

したがって、この部分グリッドは良い部分グリッドであり、これより大きな良い部分グリッドは存在しないため 6 を出力します。

入力例 2

出力例 2

入力例 3

出力例 3

Source Name

「競プロ典型90問」63日目

064 - Uplift（★3）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 3 点

問題文

日本は N 個の区画に分けられており、西から i 番目の区画（以下、区画 i とする）の標高は A_i です。

これから Q 回の地殻変動が起こります。i 回目の地殻変動では、区画 L_i, L_i+1, \cdots, R_i の標高が V_i だけ変化します。（V_i \geq 0 のとき標高が |V_i| 上がり、V_i < 0 のとき標高が |V_i| 下がることを意味します）

さて、区画 1 から N へ行く際の不便さは次のように定義されます。

区画 i の標高を E_i とするとき、不便さは |E_1 - E_2| + |E_2 - E_3| + \cdots + |E_{N-1} - E_N|

各地殻変動後の不便さをそれぞれ求めてください。

制約

1 \leq N, Q \leq 10^{5}
-10^{9} \leq A_i, V_i \leq 10^{9}
1 \leq L_i \leq R_i \leq N
入力は全て整数

入力

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

N Q
A_1 A_2 \cdots A_N
L_1 R_1 V_1
L_2 R_2 V_2
\vdots
L_Q R_Q V_Q

出力

Q 行出力してください。
i 行目には、i 番目の地殻変動が終わった後の不便さを出力してください。

入力例 1

出力例 1

3
4
4

1 回目の地殻変動後の各区画の標高は、西から順に 1, 3, 4 であり、不便さは |1 - 3| + |3 - 4| = 3 です。
2 回目の地殻変動後の各区画の標高は、西から順に 0, 2, 4 であり、不便さは |0 - 2| + |2 - 4| = 4 です。
3 回目の地殻変動後の各区画の標高は、西から順に 2, 4, 6 であり、不便さは |2 - 4| + |4 - 6| = 4 です。

入力例 2

20 10
61 51 92 -100 -89 -65 -89 -64 -74 7 87 -2 51 -39 -50 63 -23 36 74 37
2 2 -45
6 19 82
2 9 36
7 13 71
16 20 90
18 20 -24
14 17 -78
10 11 -55
7 19 -26
20 20 -7

出力例 2

Source Name

「競プロ典型90問」64日目

065 - RGB Balls 2（★7）

Time Limit: 3 sec / Memory Limit: 1024 MB

配点: 7 点

問題文

赤色のボールが R 個、緑色のボールが G 個、青色のボールが B 個あります。それぞれのボールは、たとえ色が同じであっても互いに区別できます。

これらの R+G+B 個のボールから、以下の条件を全て満たしながら K 個のボールを選ぶことを考えます。

赤色・緑色のボールを合計 X 個以下選んでいる
緑色・青色のボールを合計 Y 個以下選んでいる
青色・赤色のボールを合計 Z 個以下選んでいる

このような K 個のボールの選び方は何通りあるでしょうか？答えは非常に大きくなる可能性があるため、答えを 998244353 で割った余りを求めてください。

制約

1 \leq R, G, B \leq 200000
1 \leq K \leq \min(200000, R+G+B)
0 \leq X \leq \min(K, R+G)
0 \leq Y \leq \min(K, G+B)
0 \leq Z \leq \min(K, B+R)
入力は全て整数

小課題・得点

この問題はいくつかの小課題に分けられ、その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます。

小課題 1 (3 点)
- 1 \leq R, G, B \leq 5
- 1 \leq K \leq \min(5, R+G+B)
小課題 2 (2 点)
- 1 \leq R, G, B \leq 3000
- 1 \leq K \leq \min(3000, R+G+B)
小課題 3 (2 点)
- 追加の制約はない

入力

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

R G B K
X Y Z

出力

答えを 998244353 で割った余りを出力してください。

入力例 1

3 1 2 5
4 2 4

出力例 1

この入出力例は小課題 1, 2, 3 の制約を満たします。

2 つある青色のボールのうちいずれか 1 つのみを選ばず、残りを全て選ぶことで目的を達成できます。これ以外に目的を達成する方法は存在しないため、答えは 2 通りです。

入力例 2

65 6 12 35
30 18 35

出力例 2

257190020

この入出力例は小課題 2, 3 の制約を満たします。

答えを 998244353 で割った余りを出力してください。

入力例 3

23502 65936 72385 95835
72759 85735 72385

出力例 3

229429276

この入出力例は小課題 3 の制約を満たします。

Source Name

「競プロ典型90問」65日目

066 - Various Arrays（★5）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 5 点

問題文

数列屋の高橋くんは長さ N の数列 a を作っています。数列 a の i 番目の要素 a_i の値は、L_i 以上 R_i 以下の整数から一様ランダムに選ぶことで決定されます。

このようにしてできた数列 a の転倒数の期待値を求めてください。

なお、長さ m の数列 x の「転倒数」とは、i < j かつ x_i > x_j であるような (i, j) (1 \leq i, j \leq m) の個数のことです。

制約

1 \leq N \leq 100
1 \leq L_i \leq R_i \leq 100 (1 \leq i \leq N)
入力は全て整数で与えられる

入力

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

N
L_1 R_1
\vdots
L_N R_N

出力

答えを出力してください。ただし、相対誤差または絶対誤差が 10^{-7} 以下であれば正解として扱われます。

入力例 1

2
1 2
1 2

出力例 1

0.250000000000

数列 a としてあり得るものは以下の 4 通りです。

a = (1, 1), 転倒数 0
a = (1, 2), 転倒数 0
a = (2, 1), 転倒数 1
a = (2, 2), 転倒数 0

よって、期待値は \frac{1}{4} = 0.25 となります。

入力例 2

出力例 2

1.000000000000

数列 a としてあり得るものは a = (3, 1, 4) のみであり、この数列の転倒数は 1 です。

入力例 3

出力例 3

13.696758921226

Source Name

「競プロ典型90問」66日目

067 - Base 8 to 9（★2）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 2 点

問題文

黒板に 8 進法の整数 N が書かれています。あなたは以下の操作を K 回行います。

黒板の整数を 9 進法に直し、ここに現れる数字「 8 」を「 5 」に書き直す（書き直した後の数は 8 進数とみなされる）

操作を K 回行った後にできる数を 8 進法で出力してください。

制約

0 \leq N \lt 8^{20}
1 \leq K \leq 100
N は 8 進法で表される整数
N の先頭に余分な 0 を含まない
K は整数

入力

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

N K

出力

操作を K 回行った後にできる数を 8 進法で出力してください。このとき、答えとなる整数の先頭に余分な 0 を付けないでください。

入力例 1

21 1

出力例 1

8 進法で 21 と表される整数を 9 進法で表すと 18 となります。 8 の部分を 5 に書き直すので答えは 15 となります。

入力例 2

1330 1

出力例 2

8 進法で 1330 と表される整数を 9 進法で表すと 888 となります。 8 の部分を 5 に書き直すので答えは 555 となります。

入力例 3

2311640221315 15

出力例 3

Source Name

「競プロ典型90問」67問目

068 - Paired Information（★5）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 5 点

問題文

長さ N の整数列 A = (A_1, A_2, \ldots, A_N) があります。はじめ、あなたはこの整数列について何も知りません。

整数列 A に関する情報と質問（まとめてイベントと呼ぶ）が Q 個与えられます。最初から i 番目 (1 \leq i \leq Q) のイベントは 4 つの整数の組 (T_i, X_i, Y_i, V_i) で表され、これは次のようなものです。

T_i = 0 のとき、これは A_{X_i} + A_{Y_i} = V_i という情報が与えられることを意味します。ここでは、必ず X_i+1=Y_i です。
T_i = 1 のとき、これは A_{X_i} = V_i と仮定したとき A_{Y_i} の値は何か？という質問を意味します。
- より厳密には、 A_{X_i}=V_i と A_{X_j} + A_{Y_j} = V_j \ (1 \leq j \lt i, T_j = 0) がすべて成り立つような長さ N の整数列 A において、 A_{Y_i} の値は何か？という質問を表します。

イベントを順に処理し、それぞれの質問に答えてください。ただし、質問の時点で答え A_{Y_i} が一通りに定まらないとき、代わりに Ambiguous と出力してください。

制約

1\leq N\leq10^5
1\leq Q\leq10^5
T_i=0 または T_i=1\ (1\leq i\leq Q)
1\leq X_i,Y_i\leq N\ (1\leq i\leq Q)
T_i=0 ならば X_i+1=Y_i\ (1\leq i\leq Q)
0\leq V_i\leq 2\times10^9\ (1\leq i\leq Q)
矛盾するような入力は与えられない。
- つまり、i=1,2,\ldots,Q に対して、 T_i=0 ならば T_j=0\ (1\leq j\leq i) を満たす j に対する A_{X_j}+A_{Y_j}=V_j がすべて成り立ち、 T_i=1 ならば A_{X_i}=V_i と T_j=0\ (1\leq j \lt i) を満たす j に対する A_{X_j}+A_{Y_j}=V_j がすべて成り立つような、長さ N の整数列 A が存在する。
入力は全て整数

入力

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

N
Q
T_1 X_1 Y_1 V_1
T_2 X_2 Y_2 V_2
\vdots
T_Q X_Q Y_Q V_Q

出力

それぞれの質問の答えを順番に出力してください。ただし、質問の時点で答えが一通りに定まらないとき、代わりに Ambiguous と出力してください。

入力例 1

出力例 1

2
Ambiguous
1
2

それぞれの質問について、答えは次のようになります。

1 回目の質問(i=2)では、A_1=1 および A_1+A_2=3 を満たすような数列 A はすべて A_2=2 を満たすので、出力すべきものは 2 です。
2 回目の質問(i=3)では、A_3=5 および A_1+A_2=3 を満たすような数列 A には (A_1,A_2,A_3,A_4)=(1,2,5,10) や (A_1,A_2,A_3,A_4)=(3,0,5,0) などがあり、 A_4 の値はただ一つに定まらないため、出力すべきものは Ambiguous です。
3 回目の質問(i=5)では、A_3=5 および A_1+A_2=3,A_3+A_4=6 を満たすような数列 A はすべて A_4=1 を満たすので、出力すべきものは 1 です。
4 回目の質問(i=7)では、A_3=5 および A_1+A_2=3,A_3+A_4=6,A_2+A_3=6 を満たすような数列 A はすべて A_1=2 を満たすので、出力すべきものは 2 です。

入力例 2

15
25
0 11 12 41
0 1 2 159
0 14 15 121
0 4 5 245
0 12 13 157
0 9 10 176
0 6 7 170
0 2 3 123
0 7 8 167
0 3 4 159
1 12 11 33
0 10 11 116
0 8 9 161
1 9 12 68
1 12 12 33
1 7 12 74
0 5 6 290
1 8 9 93
0 13 14 127
1 10 12 108
1 14 1 3
1 13 8 124
1 12 11 33
1 12 10 33
1 5 15 194

出力例 2

Source Name

「競プロ典型90問」68日目

069 - Colorful Blocks 2（★3）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 3 点

問題文

N 個のブロックが横一列に並んでおり、左から順に 1 から N までの番号が付けられています。

これらのブロックそれぞれを、K 種類の色のうちいずれか一色で塗ることを考えます。ここで、次の条件を満たすように塗らなければなりません。

1 \leq |i-j| \leq 2 ならば、ブロック i とブロック j に塗られている色は異なる。
ただし、使わない色があってもよい。

このようなブロックの塗り方が何通りあるかを、10^9 + 7 で割った余りを出力してください。ただし、2 つのブロックの列の塗り方が異なるとは、ある 1 以上 N 以下の整数 i が存在して、ブロック i について異なる色で塗られていることとします。

制約

1 \leq N \leq 10^{18}
1 \leq K \leq 10^9
入力は全て整数である

入力

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

N K

出力

条件を満たすような塗り方の数を 10^9+7 で割った余りを出力せよ。

入力例 1

2 3

出力例 1

条件を満たすためには、2 つのブロックは互いに異なる色で塗らなくてはなりません。K=3 であることから、条件を満たす塗り方は 6 通りです。

入力例 2

10 2

出力例 2

2 色のみで 10 個のブロックを条件を満たすように塗ることはできません。

入力例 3

2021 617

出力例 3

53731843

答えを 10^9+7 で割った余りを出力することに注意してください。

Source Name

「競プロ典型90問」69日目

070 - Plant Planning（★4）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 4 点

問題文

二次元平面上に N 棟の工場があり、i 番目の工場は座標 (X_i, Y_i) にあります。

これからあなたは二次元平面上の好きな場所を 1 つ選び、発電所を建設します。

発電所の不便さを、発電所から各工場までのマンハッタン距離の総和と定義するとき、不便さとしてありうる最小の値を求めてください。なお、この問題の制約下で答えは整数となることが証明できます。

マンハッタン距離について

座標 (x_1, y_1) と座標 (x_2, y_2) の間のマンハッタン距離は、|x_1 − x_2| + |y_1 − y_2| で定義されます。

制約

1 \leq N \leq 10^5
-10^9 \leq X_i, Y_i \leq 10^9
入力は全て整数

入力

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

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

出力

不便さの最小値を整数で出力してください。

入力例 1

2
-1 2
1 1

出力例 1

発電所を (0, 1) に建設することで、発電所から各工場までのマンハッタン距離は次のようになります。

工場 1 ： |-1 - 0| + |2 - 1| = 2
工場 2 ： |1 - 0| + |1 - 1| = 1

このときの不便さは 2 + 1 = 3 であり、不便さを 3 より小さくすることはできないため 3 を出力します。

入力例 2

2
1 0
0 1

出力例 2

発電所を (1, 0) に建設することで不便さの最小値 2 を達成できます。

また、発電所を (0.5, 0.5) や (0, 1) に建設した場合も同様に不便さは 2 となります。

入力例 3

出力例 3

同じ座標に複数の工場が存在することもあります。

入力例 4

4
1000000000 1000000000
-1000000000 1000000000
-1000000000 -1000000000
1000000000 -1000000000

出力例 4

8000000000

Source Name

「競プロ典型90問」70日目

071 - Fuzzy Priority（★7）

Time Limit: 3 sec / Memory Limit: 1024 MB

配点: 7 点

問題文

(1,2,3, \cdots ,N) の順列 P = (P_1,P_2,P_3, \cdots ,P_N) であって、以下の条件を満たすものを K 個求めてください。 K 個存在しない場合は、そのことを報告してください。

i=1,2,3, \cdots ,M について、順列 P の中で A_i は B_i よりも前にある。

制約

1 \leq N \leq 10^5
0 \leq M \leq 10^5
1 \leq K \leq 10
1 \leq A_i \leq N
1 \leq B_i \leq N
A_i \neq B_i
i \neq j ならば (A_i,B_i) \neq (A_j,B_j)
入力はすべて整数

小課題・得点

(2 点)： N \leq 10^3
(3 点)： K = 1
(2 点)：追加の制約はない。

入力

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

N M K
A_1 B_1
A_2 B_2
\vdots
A_M B_M

出力

条件を満たす順列 P が K 個存在しない場合は -1 を出力してください。

存在する場合の出力は K 行からなります。各行には、条件を満たす順列 P を以下の形式で出力してください。

P_1 P_2 P_3 \cdots P_N

K 個の順列は相異なる必要があります。

入力例 1

5 2 3
1 2
3 4

出力例 1

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

この入力例は小課題 1,3 のみの制約を満たします。

順列 P の条件は

1 が 2 よりも前にある
3 が 4 よりも前にある

の 2 つを両方満たすことです。

この条件を満たす相異なる K 個の順列であれば、出力例と異なる順列を出力しても正解となります。また、 K 個の順列を出力する順番が異なっていても正解となります。

入力例 2

5 2 1
1 3
3 1

出力例 2

-1

この入力例はすべての小課題の制約を満たします。

条件を満たす順列は 1 つも存在しません。

入力例 3

出力例 3

5 10 6 2 8 1 3 7 9 4
5 10 6 2 8 1 3 9 7 4
5 10 6 8 2 1 3 7 9 4
5 10 6 8 2 1 3 9 7 4
5 10 6 8 1 2 3 7 9 4
5 10 6 8 1 2 3 9 7 4
10 5 6 2 8 1 3 7 9 4
10 5 6 2 8 1 3 9 7 4
10 5 6 8 2 1 3 7 9 4
10 5 6 8 2 1 3 9 7 4

この入力例は小課題 1,3 のみの制約を満たします。

Source Name

「競プロ典型90問」71日目

072 - Loop Railway Plan（★4）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 4 点

問題文

ABC 王国は H 行 W 列のマス目であらわされます。各マスは山のマスと平野のマスのどちらかです。上から i 行目、左から j 列目にあるマスが山のマスなら c_{i,j} は # 、平野のマスなら c_{i,j} は . です。

あなたは鉄道路線を作りたいです。鉄道路線の経路は、以下の条件をすべて満たす必要があります。

条件1　あるマスを始点とし、辺を共有して隣接するマスに移動することを k 回 (3 \le k) 繰り返し、始点で終わる経路である。
条件2　k 回の移動について、移動先は相異なる。（始点と終点は一致してよい）
条件3　山のマスを通らない。

例えば左から 1 番目の鉄道路線は条件を満たしますが、左から 2, 3, 4, 5 番目の鉄道路線は条件を満たしません。

鉄道路線が通るマスの数としてあり得る最大値を求めてください。ただし、条件を満たす鉄道路線がない場合は、代わりにそれを報告してください。

制約

H, W は正整数
H \times W \leq 16
c_{i,j} は # または .
c_{i,j} が . である i,j (1 \leq i \leq H,1 \leq j \leq W) が 1 つ以上存在する

入力

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

H W
c_{1,1} c_{1,2} \cdots c_{1,W}
c_{2,1} c_{2,2} \cdots c_{2,W}
\vdots
c_{H,1} c_{H,2} \cdots c_{H,W}

出力

鉄道路線が通るマスの数の最大値を出力してください。

条件を満たす鉄道路線がない場合は、代わりに -1 を出力してください。

入力例 1

3 3
...
.#.
...

出力例 1

例えば、以下の鉄道路線は 8 個のマスを通ります。

入力例 2

1 6
......

出力例 2

-1

条件を満たす鉄道路線は存在しないため、-1 と出力すればよいです。

入力例 3

4 4
....
#...
....
...#

出力例 3

例えば、以下の鉄道路線は 12 個のマスを通ります。

Source Name

「競プロ典型90問」72日目

073 - We Need Both a and b（★5）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点：5 点

問題文

N 頂点の木が与えられます。木の頂点は 1, 2, \cdots, N と番号付けられており、i 番目の辺は頂点 a_i と頂点 b_i を双方向に結んでいます。

各頂点には a, b いずれかの文字が書かれており、頂点 i に書かれている文字は c_i です。

0 本以上の辺を削除する方法は 2^{N-1} 通りありますが、その中で「辺を削除した後、すべての連結成分が a, b 両方の文字を含む」ものは何通りかを求め、10^9+7 で割った余りを出力してください。

制約

2 \leq N \leq 100000
c_i は a, b のいずれか
1 \leq a_i, b_i \leq N
与えられるグラフは木である

入力

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

N
c_1 c_2 \ldots c_N
a_1 b_1
\vdots
a_{N - 1} b_{N - 1}

出力

答えを 10^9+7 で割った余りを一行に出力してください。　

入力例 1

7
b a b a b b a
2 1
3 7
3 2
3 4
5 4
4 6

出力例 1

条件を満たす辺の削除方法は、以下の 4 つです。

辺を一つも削除しない
辺 (3, 2) を削除する
辺 (3, 4) を削除する
辺 (3, 2) と辺 (3, 4) を削除する

入力例 2

2
a b
1 2

出力例 2

辺を削除することはできません。

入力例 3

22
b a b b a b b b a b a a a a b b a b b a a a
1 7
4 14
12 22
2 4
21 17
3 20
7 8
20 14
15 11
8 14
9 12
17 8
6 20
11 20
18 19
10 8
22 20
13 21
5 14
19 20
16 14

出力例 3

Source Name

「競プロ典型90問」73日目

074 - ABC String 2（★6）

Time Limit: 1 sec / Memory Limit: 1024 MB

問題文

いま、電光掲示板に a・b・c からなる長さ N の文字列 S が表示されています。

あなたは以下の 2 種類の操作を好きな順番で何回でも行うことができます。ただし「変化させる」とは、元々 a だったものを b に、b だったものを c に、c だったものを a に変えることを指します。

S_i = b である i (1 \leq i \leq N) を 1 つ選び、S_i を a に変更した後、S_1, S_2, \cdots, S_{i-1} を変化させる。
S_i = c である i (1 \leq i \leq N) を 1 つ選び、S_i を b に変更した後、S_1, S_2, \cdots, S_{i-1} を変化させる。

最大で何回の操作が行えるか、求めてください。

制約

1 \leq N \leq 60
S は a・b・c からなる長さ N の文字列である

入力

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

N
S

出力

答えを出力してください。

入力例 1

3
aba

出力例 1

例えば以下のような手順をとることで、2 回の操作を行うことができます。

まず i = 2 を選んで操作を行う。そのとき、文字列 S は aba → baa に変化する。
次に i = 1 を選んで操作を行う。そのとき、文字列 S は baa → aaa に変化する。

入力例 2

10
aaaaaaaaaa

出力例 2

すべての文字が a であるため、残念ながら操作を行うことができません。

入力例 3

5
baaca

出力例 3

Source Name

「競プロ典型90問」74日目

075 - Magic For Balls（★3）

Time Limit: 2 sec / Memory Limit: 1024 MB

得点: 3 点

問題文

整数 x が書かれたボールに対し、そのボールを叩くことによって以下の操作が行われます。

x が素数でない場合：叩かれたボールを消滅させ、整数 a が書かれたボールと整数 b が書かれたボールを追加する。a, b は ab=x かつ a \geq 2, b \geq 2 を満たす整数から自由に選ぶことができる。
x が素数である場合：なにも起こらない。

また、魔法を 1 回使うと、現在あるすべてのボールを同時に叩くことができます。一方、魔法を使う以外の手段でボールを叩くことはできません。

さて、整数 N が書かれたボールが 1 個だけあります。あなたは何回か魔法を使うことで、すべてのボールに書かれている数を素数にしたいです。最小で何回の操作を行う必要がありますか？

制約

2 \leq N \leq 10^{12}
N は整数

入力

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

出力

答えを出力してください。

入力例 1

出力例 1

はじめに、42 が書かれたボールがあります。魔法を使ってこのボールを叩くと、例えば以下の操作が行われます。

42 が書かれたボールを消滅させ、7 が書かれたボールと 6 が書かれたボールを追加する。

いま、それぞれ 6, 7 が書かれた 2 個のボールがあります。魔法を使ってこれらのボールを叩くと、以下の操作が行われます。

7 が書かれたボールを叩いても何も起こらない。
6 が書かれたボールを消滅させ、2 が書かれたボールと 3 が書かれたボールを追加する。

いま、それぞれ 2, 3, 7 が書かれた 3 個のボールがあります。これらはすべて素数であるため、2 回の魔法で条件を達成することができます。2 回より少ない回数で条件を達成することはできません。

入力例 2

出力例 2

例えば、下図の手順で操作を行うと、3 回の魔法ですべてのボールに書かれている数を素数にできます。

入力例 3

出力例 3

入力例 4

出力例 4

はじめから素数の場合は、魔法を使わずとも条件を満たしているため、0 を出力してください。

Source Name

「競プロ典型90問」75日目

076 - Cake Cut（★3）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 3 点

問題文

N 個のピースに分かれている円形のホールケーキがあり、時計回りで i 番目にあるピース（以下、ピース i とする）の大きさは A_i です。1 \leq i \leq N-1 に対し、ピース i とピース i+1 は隣接しており、ピース N とピース 1 も隣接しています。

ケーキのある連続するピースを選ぶ方法であって、選んだ部分が全体の大きさのちょうど 10 分の 1 になるものは存在するか、判定してください。

制約

1 \leq N \leq 10^5
1 \leq A_i \leq 10^9
入力は全て整数

入力

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

N
A_1 A_2 \cdots A_N

出力

選んだ部分が全体の大きさの 10 分の 1 になるような取り出し方が存在する場合は Yes を、そうでない場合は No を出力してください。

入力例 1

10
1 1 1 1 1 1 1 1 1 1

出力例 1

Yes

全体の大きさは 10 なので、選んだ部分の大きさの合計が 1 になるように連続するピースを選ぶ必要があります。
例えばピース 1 のみを選ぶなどの方法があります。

入力例 2

3
1 1 1

出力例 2

No

選んだ部分が全体の 10 分の 1 になるような選び方はありません。

入力例 3

3
1 18 1

出力例 3

Yes

ピース 1 とピース 3 を選ぶことで、選んだ部分の大きさの合計が全体の 10 分の 1 になります。
ピース 1 とピース N が隣接していることに注意してください。

入力例 4

4
1 9 1 9

出力例 4

No

ピース 1 とピース 3 を選ぶと大きさの合計は全体の 10 分の 1 になりますが、ピースが連続しないように選ぶことは出来ません。

Source Name

「競プロ典型90問」76日目

077 - Planes on a 2D Plane（★7）

Time Limit: 1.5 sec / Memory Limit: 1024 MB

配点: 7 点

問題文

2 次元座標平面とみなせる大空に、N 機の飛行機が航行しています。
i=1,2, \cdots ,N に対し、 i 番目の飛行機は時刻 0 において座標 (AX_i,AY_i) に存在しました。

飛行機はいずれも向き 1,2,3,4,5,6,7,8 のいずれかを向いて航行しています。
時刻 t において座標 (x,y) に存在する向き d の飛行機は、時刻 t+1 において

d=1 ならば座標 (x+1,y) に
d=2 ならば座標 (x+1,y+1) に
d=3 ならば座標 (x,y+1) に
d=4 ならば座標 (x-1,y+1) に
d=5 ならば座標 (x-1,y) に
d=6 ならば座標 (x-1,y-1) に
d=7 ならば座標 (x,y-1) に
d=8 ならば座標 (x+1,y-1) に

存在します。
また、航行の途中で飛行機が向きを変えることはありません。

あなたは管制官の高橋くんから次のような報告を受けました。

時刻 T において、座標 (BX_1,BY_1),(BX_2,BY_2), \cdots ,(BX_N,BY_N) に飛行機が存在した

彼の報告に矛盾しないような N 機の飛行機の向きの組み合わせが存在するかを判定し、存在する場合は一例を出力してください。

制約

1 \leq N \leq 20000
1 \leq T \leq 10^9
0 \leq AX_i,AY_i,BX_i,BY_i \leq 10^9
i \ne j ならば (AX_i,AY_i) \ne (AX_j,AY_j)
i \ne j ならば (BX_i,BY_i) \ne (BX_j,BY_j)
入力はすべて整数

小課題・得点

(1 点)：N \leq 6
(1 点)：AY_i=0, BY_i=0
(2 点)：N \leq 1000
(3 点)：追加の制約はない。

入力

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

N T
AX_1 AY_1
AX_2 AY_2
 \vdots 
AX_N AY_N
BX_1 BY_1
BX_2 BY_2
 \vdots 
BX_N BY_N

出力

高橋くんの報告に矛盾しない向きの組み合わせが存在しない場合、No と出力してください。
存在する場合、以下の形式で 1, 2, \cdots, N 番目の飛行機の向きを空白区切りで出力してください。ただし、D_i は飛行機 i の向きとします。

Yes
D_1 D_2 D_3 \cdots D_N

入力例 1

出力例 1

Yes
2 6 1

時刻 T において、1 番目の飛行機は座標 (BX_2,BY_2) に、2 番目の飛行機は座標 (BX_3,BY_3) に、3 番目の飛行機は座標 (BX_1,BY_1) に存在します。

入力例 2

3 2
3 3
5 5
9 2
11 1000000000
5 5
3 3

出力例 2

No

高橋くんの報告に矛盾しない向きの組み合わせは存在しません。

入力例 3

20 774
540130346 269080121
139837096 165633078
731188937 784167460
18996195 52176517
153153670 738204723
179733158 825294112
698198250 713974773
449248931 563096572
249863070 242694893
428066819 476630383
554127636 460973490
389988495 32320086
889782910 956212985
43905938 212030305
638141790 667879166
985957895 358743012
971007109 827787244
804625543 141347414
905270323 167192824
614855582 963943648
179733932 825294886
731188163 784166686
153154444 738205497
554128410 460973490
804626317 141348188
449249705 563096572
540129572 269079347
638142564 667878392
614855582 963944422
18996969 52177291
971007109 827788018
889782910 956213759
43906712 212031079
389987721 32319312
139836322 165633078
428067593 476631157
905271097 167192824
249862296 242694893
985958669 358742238
698199024 713975547

出力例 3

Yes
6 5 6 2 2 2 2 1 5 2 1 6 3 2 8 8 3 2 1 3

Source Name

「競プロ典型90問」77日目

078 - Easy Graph Problem（★2）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点：2 点

問題文

N 頂点 M 辺の連結な単純無向グラフが与えられます。グラフの頂点には、それぞれ 1 から N までの番号が振られています。 i 番目の辺は、頂点 a_i と b_i を双方向に結んでいます。

以下の条件を満たす頂点の個数はいくつあるか出力してください。

自分自身より頂点番号が小さい隣接頂点がちょうど 1 つ存在する

制約

2 \leq N \leq 100000
N - 1 \leq M \leq \mathrm{min}(\frac{N(N - 1)}{2}, 100000)
1 \leq a_i, b_i \leq N
与えられるグラフは単純グラフである
与えられるグラフは連結である
入力はすべて整数で与えられる

入力

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

N M
a_1 b_1
\vdots
a_{M} b_{M}

出力

条件を満たす頂点の個数を一行に出力してください。

入力例 1

出力例 1

条件を満たす頂点は、2, 4, 5 の 3 つです。

頂点 2 は、自分自身より頂点番号が小さい隣接頂点として、頂点 1 のみをもつ
頂点 4 は、自分自身より頂点番号が小さい隣接頂点として、頂点 2 のみをもつ
頂点 5 は、自分自身より頂点番号が小さい隣接頂点として、頂点 2 のみをもつ

入力例 2

2 1
1 2

出力例 2

条件を満たす頂点は 2 のみです。

入力例 3

出力例 3

Source Name

「競プロ典型90問」78日目

079 - Two by Two（★3）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 3 点

問題文

H \times W の 2 次元配列 A が与えられます。あなたは以下の 2 種類の操作を好きな順番で何度でも行うことが出来ます。

整数 x, y (1 \leq x \lt H, 1 \leq y \lt W) を選び、A_{x, y}, A_{x+1, y}, A_{x, y+1}, A_{x+1, y+1} の値をそれぞれ 1 ずつ増やす。
整数 x, y (1 \leq x \lt H, 1 \leq y \lt W) を選び、A_{x, y}, A_{x+1, y}, A_{x, y+1}, A_{x+1, y+1} の値をそれぞれ 1 ずつ減らす。

操作を 0 回以上行うことで A を B に一致させることは可能でしょうか。もし可能ならば、最小の操作回数も答えてください。

制約

2 \leq H, W \leq 100
0 \leq A_{i, j}, B_{i, j} \leq 10^5
入力は全て整数

入力

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

H W
A_{1, 1} A_{1, 2} \cdots A_{1, W}
A_{2, 1} A_{2, 2} \cdots A_{2, W}
\vdots
A_{H, 1} A_{H, 2} \cdots A_{H, W}
B_{1, 1} B_{1, 2} \cdots B_{1, W}
B_{2, 1} B_{2, 2} \cdots B_{2, W}
\vdots
B_{H, 1} B_{H, 2} \cdots B_{H, W}

出力

操作を行うことで A を B に一致させることが可能である場合は 1 行目に Yes、2 行目に最小の操作回数を出力してください。 A を B に一致させることが不可能である場合は No と出力してください。

入力例 1

出力例 1

Yes
1

(x, y)=(1, 1) を選んで 1 増やす操作を行うことで A が B に一致します。

入力例 2

出力例 2

No

どのように操作を行っても A を B に一致させることは出来ません。

入力例 3

5 5
6 17 18 29 22
39 50 25 39 25
34 34 8 25 17
28 48 25 47 42
27 47 24 32 28
4 6 3 29 28
48 50 21 48 29
44 44 19 47 28
4 49 46 29 28
4 49 45 1 1

出力例 3

Yes
140

Source Name

「競プロ典型90問」79日目

080 - Let's Share Bit（★6）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 6 点

問題文

N 個の非負整数 A_1,A_2,\ldots,A_N があります。

0 以上 2^D 未満の整数 x のうち、i=1,2,\ldots,N すべてについて次の条件を満たすようなものはいくつあるか、求めてください。

A_i と x のビットごとの論理積（ビット単位\operatorname{AND}）が 0 でない。

ビットごとの論理積（ビット単位\operatorname{AND}）について

非負整数 A,B のビットごとの論理積（ビット単位\operatorname{AND}）、A\ \operatorname{AND}\ B は以下のように定義されます。

A\ \operatorname{AND}\ B を二進表記した際の 2^k\ (k\geq0) の位の数は、A,B を二進表記した際の 2^k の位の数のうち両方が 1 であれば 1、そうでなければ 0 である。

例えば、3\ \operatorname{AND}\ 5=1 となります (二進表記すると: 011\ \operatorname{AND}\ 101=001)。

制約

1\leq N\leq20
0\leq D\leq60
0\leq A_i<2^D\ (1\leq i\leq N)
入力は全て整数

入力

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

N D
A_1 A_2 \cdots A_N

出力

N 個の条件をすべて満たす整数 x の個数を出力してください。

入力例 1

4 3
1 3 4 5

出力例 1

0 以上 2^3 未満の整数 x はそれぞれ次の条件を満たします。

0 はどの条件も満たさない。
1 は 1,2,4 つ目の条件を満たすが、3 つ目の条件を満たさない。
2 は 2 つ目の条件を満たすが、1,3,4 つ目の条件を満たさない。
3 は 1,2,4 つ目の条件を満たすが、3 つ目の条件を満たさない。
4 は 3,4 つ目の条件を満たすが、1,2 つ目の条件を満たさない。
5 は全ての条件を満たす。
6 は 2,3,4 つ目の条件を満たすが、1 つ目の条件を満たさない。
7 は全ての条件を満たす。

よって、答えは 2 です。

入力例 2

5 21
1050624 32772 493952 144 869120

出力例 2

入力例 3

20 60
216181578206878016 81348488767472704 26388280246272 281543729742896 72127981178847488 2199108462600 585610888171487234 22027813536776 567459673280576 146648462866649600 144484898860704776 576471786208755714 4398621196432 144141576657960976 81069330992726040 360851057582278674 17859112 11570646360064 144115206396936193 1702052723957760

出力例 3

977902973481140224

入力や出力すべき値が 32 ビット整数に収まらない場合があります。

Source Name

「競プロ典型90問」80日目

081 - Friendly Group（★5）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 5 点

問題文

典型高校には N 人の生徒がおり、各生徒には 1 から N までの番号が付けられています。生徒 i の身長は A_i、体重は B_i です。

N 人の生徒から 1 人以上を選び、次の条件をすべて満たすようにチームを作ります。

チーム内のどの 2 人も、身長の差の絶対値が K 以下である
チーム内のどの 2 人も、体重の差の絶対値が K 以下である

チームの人数としてありうる最大の値を求めてください。

制約

1 \leq N \leq 2 \times 10^5
1 \leq K \leq 5000
1 \leq A_i, B_i \leq 5000 \ (1 \leq i \leq N)
入力は全て整数

入力

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

N K
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

答えを出力してください。

入力例 1

出力例 1

|A_1 - A_2| = |1 - 2| = 1 \leq K, |B_1 - B_2| = |1 - 5| = 4 \leq K より、生徒 1 と生徒 2 を選び 2 人チームを作ることができます。

2 人より多い人数のチームを作ることはできないため 2 を出力します。

入力例 2

2 123
4 5
678 901

出力例 2

1 人チームしか作れない場合もあります。

入力例 3

出力例 3

5 人の生徒 1, 2, 3, 5, 6 を選んでチームを作ることができます。

Source Name

「競プロ典型90問」81日目

082 - Counting Numbers（★3）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 3 点

問題文

何も書かれていない黒板があります。 x=L,\ L+1,\ \dots,\ R の順に、以下の操作を行います。

黒板に、整数 x を x 回書く。

全ての操作が終了した後、黒板に書かれている文字の個数を 10^9+7 で割った余りを求めてください。

ただし、数えるのは整数ではなく文字である事に注意してください。例えば、整数 15 は 2 個の文字として数えます。

制約

1 \leq L \leq R \leq 10^{18}
入力は全て整数

入力

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

L R

出力

全ての操作が終了した後、黒板に書かれている文字の個数を 10^9+7 で割った余りを出力してください。

入力例 1

3 5

出力例 1

全ての操作が終了した後、黒板には以下の整数が書かれています。

3,\ 3,\ 3,\ 4,\ 4,\ 4,\ 4,\ 5,\ 5,\ 5,\ 5,\ 5

よって、書かれている文字の個数は 12 です。

入力例 2

98 100

出力例 2

全ての操作が終了した後、黒板には 98 が 98 個、99 が 99 個、100 が 100 個書かれています。

よって、書かれている文字の個数は 2\times 98+2\times 99+3\times 100=694 です。

入力例 3

1001 869120

出力例 3

59367733

10^9+7 で割った余りを出力してください。

入力例 4

381453331666495446 746254773042091083

出力例 4

584127830

入力は 32 bit 整数型に収まらない可能性があります。

Source Name

「競プロ典型90問」82日目

083 - Colorful Graph（★6）

Time Limit: 3 sec / Memory Limit: 1024 MB

配点：6 点

問題文

10^9 種類の色があり、各色には 1 から 10^9 までの番号が振られています。最初、すべての頂点は色 1 で塗られています。

以下の形式のクエリが Q 個与えられるので、順に処理してください。

整数 x, y が与えられる。現在の頂点 x の色の番号を出力し、頂点 x とそれに隣接するすべての頂点を色 y で塗り替える。

制約

1 \leq N \leq 200000
N - 1 \leq M \leq \mathrm{min}(\frac{N(N - 1)}{2}, 200000)
1 \leq a_i, b_i \leq N
1 \leq Q \leq 200000
1 \leq x_i \leq N
1 \leq y_i \leq 10^9
与えられるグラフは単純グラフである
与えられるグラフは連結である
入力はすべて整数で与えられる

小課題・得点

(2 点)： N, Q \leq 2000
(4 点)：追加の制約はない。

入力

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

N M
a_1 b_1
\vdots
a_M b_M
Q
x_1 y_1
\vdots
x_Q y_Q

出力

各クエリに対する答えを、合計 Q 行で順に出力してください。

入力例 1

出力例 1

各クエリでは以下の処理が行われます。

1 番目のクエリでは、頂点 4 の色の番号 1 を出力した後、頂点 1, 4 を色 2 に変更する
2 番目のクエリでは、頂点 3 の色の番号 1 を出力した後、頂点 1, 2, 3 を色 3 に変更する
3 番目のクエリでは、頂点 2 の色の番号 3 を出力した後、頂点 1, 2, 3 を色 4 に変更する
4 番目のクエリでは、頂点 4 の色の番号 2 を出力した後、頂点 1, 4 を色 5 に変更する
5 番目のクエリでは、頂点 1 の色の番号 5 を出力した後、頂点 1, 2, 3, 4 を色 6 に変更する

入力例 2

出力例 2

Source Name

「競プロ典型90問」83日目

084 - There are two types of characters（★3）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 3 点

問題文

o と x からなる長さ N の文字列 S が与えられます。

以下の条件をすべて満たす整数の組 (l, r) の個数を求めてください。

1 \leq l \leq r \leq N
S の l 文字目から r 文字目までの区間に、o と x 両方が含まれる

制約

1 \leq N \leq 10^6
S は o, x からなる長さ N の文字列である

入力

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

N
S

出力

答えを出力してください。

入力例 1

4
ooxo

出力例 1

(l, r) = (1, 3), (1, 4), (2, 3), (2, 4), (3, 4) の 5 個が条件を満たします。

入力例 2

5
oxoxo

出力例 2

入力例 3

5
ooooo

出力例 3

どのような (l, r) を選んでも条件を満たしません。

入力例 4

7
xxoooxx

出力例 4

Source Name

「競プロ典型90問」84日目

085 - Multiplication 085（★4）

Time Limit: 2 sec / Memory Limit: 1024 MB

得点: 4 点

問題文

正の整数 K が与えられます。abc=K を満たす正の整数 (a, b, c) \ (a \le b \le c) の組がいくつあるかを求めてください。

制約

1 \leq K \leq 10^{12}

入力

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

出力

答えを出力してください。

入力例 1

出力例 1

以下の 5 通りの方法で、3 つの正整数の積として表すことができます。

(a, b, c) = (1, 1, 42) にする [1 \times 1 \times 42 = 42]
(a, b, c) = (1, 2, 21) にする [1 \times 2 \times 21 = 42]
(a, b, c) = (1, 3, 14) にする [1 \times 3 \times 14 = 42]
(a, b, c) = (1, 6, 7) にする [1 \times 6 \times 7 = 42]
(a, b, c) = (2, 3, 7) にする [2 \times 3 \times 7 = 42]

入力例 2

出力例 2

以下の 1 通りの方法で、3 つの正整数の積として表すことができます。

(a, b, c) = (1, 1, 7) にする [1 \times 1 \times 7 = 7]

入力例 3

出力例 3

Source Name

「競プロ典型90問」85日目

086 - Snuke's Favorite Arrays（★5）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 5 点

問題文

すぬけ君は、以下の 2 つの条件両方を満たす、長さ N の数列 A = (A_1, A_2, \ldots, A_N) が好きです。

条件1　すべての i (1 \leq i \leq Q) について A_{x_i} \ \mathrm{OR} \ A_{y_i} \ \mathrm{OR} \ A_{z_i} = w_i を満たす（ここで \mathrm{OR} はビットごとの論理和である）
条件2　すべての j (1 \leq j \leq N) について 0 \leq A_j < 2^{60} を満たす

すぬけ君が好きな数列 A の個数を 1000000007 で割った余りを出力してください。

制約

3 \leq N \leq 12
1 \leq Q \leq 50
1 \leq x_i < y_i < z_i \leq N (1 \leq i \leq Q)
0 \leq w_i < 2^{60} (1 \leq i \leq Q)
入力はすべて整数で与えられる

入力

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

N Q
x_1 y_1 z_1 w_1
\vdots
x_Q y_Q z_Q w_Q

出力

すぬけ君が好きな数列 A の個数を 1000000007 で割った余りを出力してください。

入力例 1

4 2
1 2 3 50
2 3 4 45

出力例 1

例えば A = (50, 32, 0, 13) は、すぬけ君が好きな数列の一つです。以下の通り、与えられたすべての条件を満たすことが確認できます。

(A_1 \ \mathrm{OR} \ A_2 \ \mathrm{OR} \ A_3) = (50 \ \mathrm{OR} \ 32 \ \mathrm{OR} \ 0) = 50
(A_2 \ \mathrm{OR} \ A_3 \ \mathrm{OR} \ A_4) = (32 \ \mathrm{OR} \ 0 \ \mathrm{OR} \ 13) = 45
数列 A のそれぞれの要素の値は 0 以上 2^{60} 未満である

入力例 2

8 2
2 3 6 1152886174205865983
1 2 8 1116611213275394047

出力例 2

395781543

1000000007 で割った余りを出力してください。

Source Name

「競プロ典型90問」86日目

087 - Chokudai's Demand（★5）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 5 点

問題文

AtCoder 国には N 個の街があり、それぞれ 1, 2, \cdots, N と番号付けられています。任意の 2 つの街の間には道路があり、交通費（単位：スヌーク）を支払うことで一方の街から他方の街へ移動することができます。

AtCoder 国の大臣は、最初に正の整数 X を決めた後、それぞれの (i, j) (i \neq j) の組について交通費を以下のように設定することにしました。

A_{i,j} \neq -1 のとき：街 i と街 j の間を結ぶ道路の交通費は A_{i,j} スヌーク
A_{i,j} =-1 のとき：街 i と街 j の間を結ぶ道路の交通費は X スヌーク

また、チョクダイ国王の意向により、以下の要件を満たさなければなりません。

経路を適切に選ぶことで街 i から街 j まで合計 P スヌーク以下で到達可能であるような組 (i, j) [1 \leq i < j \leq N] がちょうど K 個存在する。

チョクダイ国王の意向を満たすような X の選び方はいくつ存在しますか。ただし、無限個の場合はそのことを報告してください。

制約

2 \leq N \leq 40
1 \leq P \leq 10^9
0 \leq K \leq \frac{N(N-1)}{2}
i \neq j ならば 1 \leq A_{i,j} \leq 10^8 または A_{i,j}=-1
i=j ならば A_{i,j}=0
A_{i,j}=A_{j,i}
入力は全て整数

入力

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

N P K
A_{1,1} \cdots A_{1,N}
\vdots
A_{N,1} \cdots A_{N,N}

出力

チョクダイ国王の意向を満たすような正整数 X の個数が有限個ならばその個数を、無限個ならば Infinity と出力してください。

入力例 1

出力例 1

例えば、X=3 とすると、以下の通り 4 スヌーク以下で到達可能な街の組の数はちょうど 2 なので、チョクダイ国王の意向を満たします。

街 1 から街 2 へは 4 スヌーク以下で到達可能
街 1 から街 3 へは 4 スヌーク以下で到達可能
街 2 から街 3 へは 4 スヌーク以下で到達不可能

また、X = 2, 3, 4 のときチョクダイ国王の意向を満たし、これ以外のときは満たさないので、答えは 3 です。

入力例 2

出力例 2

Infinity

X \geq 11 である全ての正の整数 X においてチョクダイ国王の意向を満たします。よって、無限個存在するので Infinity と出力しなければなりません。

入力例 3

13 777 77
0 425 886 764 736 -1 692 660 -1 316 424 490 423
425 0 -1 473 -1 311 -1 -1 903 941 386 521 486
886 -1 0 605 519 473 775 467 677 769 690 483 501
764 473 605 0 424 454 474 408 421 530 756 568 685
736 -1 519 424 0 -1 804 598 911 731 837 459 610
-1 311 473 454 -1 0 479 613 880 -1 393 875 334
692 -1 775 474 804 479 0 579 -1 -1 575 985 603
660 -1 467 408 598 613 579 0 456 378 887 -1 372
-1 903 677 421 911 880 -1 456 0 859 701 476 370
316 941 769 530 731 -1 -1 378 859 0 800 870 740
424 386 690 756 837 393 575 887 701 800 0 -1 304
490 521 483 568 459 875 985 -1 476 870 -1 0 716
423 486 501 685 610 334 603 372 370 740 304 716 0

出力例 3

Source Name

「競プロ典型90問」87日目

088 - Similar but Different Ways（★6）

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 6 点

問題文

N 枚のカードがあり、各カードには 1 から N までの番号が振られています。カード i には正整数 A_i が書かれています。
E869120 と square1001 は、これらのカードからそれぞれ 1 枚以上のカードを選びました。
両者のカードの選び方について、次の条件をすべて満たすことが分かっています。

条件1　E869120 が選んだカードに書かれた整数の総和と、square1001 が選んだカードに書かれた整数の総和は等しかった
条件2　i = 1, 2, \cdots, Q に対し、カード X_i とカード Y_i の両方を選んだ人はいなかった
条件3　両者が選んだカードの集合は等しくなかった

両者のカードの選び方としてあり得るものを一つ出力してください。ただし、E869120・square1001 両方が選んだカードが存在するかもしれないことに注意してください。

制約

2 \leq N \leq 88
0 \leq Q \leq \frac{N(N-1)}{2}
1 \leq A_i
A_1 + A_2 + ... + A_N \leq 8888
1 \leq X_i \lt Y_i \leq N
i \ne j ならば (X_i,Y_i) \ne (X_j,Y_j)
入力はすべて整数
条件を満たすカードの選び方が存在する

入力

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

N Q
A_1 A_2 \cdots A_N
X_1 Y_1
X_2 Y_2
 \vdots 
X_Q Y_Q

出力

E869120 がカード (B_1, B_2, \cdots, B_x) [B_1 < B_2 < \cdots < B_x] を、square1001 がカード (C_1, C_2, \cdots, C_y) [C_1 < C_2 < \cdots < C_y] を選んだとするとき、以下の形式で 4 行にわたって出力してください。

x
B_1 B_2 \cdots B_x
y
C_1 C_2 \cdots C_y

入力例 1

出力例 1

A_2 + A_3 + A_4 + A_5 = 9, A_1 + A_3 + A_5 = 9 であり、両者が選んだカードに書かれた整数の総和は等しいです。
その他の条件もすべて満たすため、この出力は正しいです。
他にも、例えば以下のような出力も正答として扱われます。

入力例 2

10 10
2 5 7 8 11 10 1 88 86 50
1 2
1 3
1 4
1 5
1 6
5 10
6 10
2 3
9 10
7 8

出力例 2

Source Name

「競プロ典型90問」88日目

089 - Partitions and Inversions（★7）

Time Limit: 3 sec / Memory Limit: 1024 MB

配点: 7 点

問題文

長さ N の正整数列 A = (A_1,A_2,A_3,\cdots, A_N) が与えられます。

この数列を 1 つ以上の空でない連続した区間に分割する方法は 2^{N-1} 通りありますが、これらのうち次の条件を満たすものの個数を数えてください。

すべての区間について、その区間内での バブルソートの交換回数 が K 以下である。

ただし、答えは非常に大きくなる可能性があるため、10^9+7 で割った余りを出力してください。

バブルソートの交換回数とは

「"A_i > A_{i+1} であればその 2 数を交換する" という操作を i = 1, 2, \cdots, N-1 の順に行う」ことを 1 回の走査とします。そこで、走査を N-1 回繰り返すことで、数列を昇順にソートできることが知られています。
ここでは、このアルゴリズムを適用した時に整数の交換が行われる回数をバブルソートの交換回数と定義します。
例えば A = (2, 4, 3, 1) の場合、バブルソートの交換回数は 4 です。

制約

1\leq N\leq 2 \times 10^5
0\leq K\leq \frac{N(N-1)}2
1\leq A_i\leq 10^9
入力はすべて整数

小課題

(1 点): K=0
(1 点): N\leq 15
(1 点): N\leq 800
(2 点): N\leq 10000
(2 点): 追加の制約はない。

入力

入力は、以下の形式で与えられます。

N K
A_1 A_2 A_3 \cdots A_N

出力

問題文中の条件を満たす分割方法の数を 10^9+7 で割った余りを 1 行に出力してください。

入力例 1

4 0
3 1 4 2

出力例 1

\{3\}, \{1,4\}, \{2\} という分割と、\{3\}, \{1\}, \{4\}, \{2\} という分割の 2 通りが条件を満たします。

入力例 2

7 2
5 3 7 2 1 2 3

出力例 2

入力例 3

7 0
7 6 5 4 3 2 1

出力例 3

Source Name

「競プロ典型90問」89日目

090 - Tenkei90's Last Problem（★7）

Time Limit: 7 sec / Memory Limit: 1024 MB

配点: 10 点

問題文

以下の条件を満たす長さ N の非負整数列 A=(A_1,A_2, \cdots ,A_N) の個数を 998244353 で割ったあまりを求めてください。

1 \leq l \leq r \leq N を満たす任意の整数の組 (l,r) について、 \mathrm{min} \lbrace A_l,A_{l+1}, \cdots , A_r \rbrace \times (r-l+1) \leq K が成り立つ。

制約

1 \leq N \leq 10^{11}
1 \leq K \leq 10^5
入力はすべて整数

小課題・得点

(1 点)： N \leq 10^5, K = 1
(1 点)： K = 1
(1 点)： N \leq 6, K \leq 6
(2 点)： N \leq 100, K \leq 100
(2 点)： N \leq 10000, K \leq 10000
(2 点)： N \leq 10^5
(1 点)：追加の制約はない。

入力

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

N K

出力

答えを 1 行に出力してください。

入力例 1

2 2

出力例 1

A=(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1) は条件を満たします。

A=(2,2) は、 l=1,r=2 の場合に \mathrm{min} \lbrace A_l,A_{l+1}, \cdots , A_r \rbrace \times (r-l+1) = \mathrm{min} \lbrace 2,2 \rbrace \times (2-1+1) = 4 \gt K となり、条件を満たしません。

入力例 2

17 29

出力例 2

263173793

この入力は小課題 4,5,6,7 の制約を満たします。

入力例 3

2718 2818

出力例 3

393799986

この入力は小課題 5,6,7 の制約を満たします。

入力例 4

28593 1

出力例 4

365728740

この入力は小課題 1,2,6,7 の制約を満たします。

入力例 5

869120 1001

出力例 5

967393022

この入力は小課題 7 の制約を満たします。

Source Name

「競プロ典型90問」90日目