DISCO presents ディスカバリーチャンネルコードコンテスト2020 本戦

A - Div/de

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点: 300 点

問題文

双子の姉妹である Yes と No は、東京で行われるプログラミングコンテストに参加します。姉妹はウォーミングアップのため、会場へ向かう新幹線でゲームをすることにしました。

姉妹は紙に N 個の正の整数を書きます。i\ (1 \leq i \leq N) 番目の値は A_i です。

ゲームでは、Yes が先攻、No が後攻となって、交互に以下の操作をします。

紙に書いてある 2 以上の整数を 1 つ選び、より小さい正の約数に書き換える。

先に操作ができなくなった方が負けとなります。

2 人が最善を尽くしたとき、勝つのは Yes と No のどちらでしょうか？

制約

入力はすべて整数
1 \leq N \leq 100
1 \leq A_i \leq 100\ (1 \leq i \leq N)

入力

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

N
A_1 A_2 \dots A_N

出力

2 人が最善を尽くしたとき、Yes が勝つならば Yes を、No が勝つならば No を出力せよ。

入力例 1

5
1 2 3 4 5

出力例 1

Yes

ゲームの進行は、一例として次のようになります。

Yes が A_4 を 4 から 2 に書き換える。
No が A_3 を 3 から 1 に書き換える。
Yes が A_2 を 2 から 1 に書き換える。
No が A_4 を 2 から 1 に書き換える。
Yes が A_5 を 5 から 1 に書き換える。
No は操作できなくなり、Yes が勝つ。

No がどう動かしても、Yes が適切に操作すれば No が先に操作できなくなります。

入力例 2

6
1 1 1 1 1 1

出力例 2

No

はじめから操作できないので、No が勝ちます。

入力例 3

3
19 12 15

出力例 3

No

入力例 4

10
91 92 93 94 95 96 97 98 99 100

出力例 4

No

B - Hawker on Graph

実行時間制限: 6 sec / メモリ制限: 1024 MB

配点 : 600 点

問題文

N 頂点 M 辺の重み付き有向グラフ G があります。 G の頂点には 1, 2, \ldots, N、辺には 1, 2, \ldots, M と番号が振られています。辺 i は頂点 u_i から頂点 v_i へ張られており、辺の重みは w_i です。あなたは、G 上で次のようなゲームをします。

初めに、所持金 W 円を持って頂点 S 上に立つ。その後、以下の操作を K 回行う:

自分の今いる頂点から出ている辺を 1 つ選んで、その辺が接続する頂点に移動する。
このとき、選んだ辺の重みを w とすると、w が正ならば w 円得る。逆に w が負ならば |w| 円失う。また、所持金が負となることはない。すなわち、元の所持金を t 円とすると、移動後の所持金は \mathrm{max}(t+w, 0) 円である。

同じ辺を何度通ってもよく、通るたびに所持金が変化します。 K 回の操作を完了する前に、移動が不可能になる頂点に訪れては行けません。また、ゲーム終了時はどの頂点に立っていても構いません。

このとき、ゲーム終了時の所持金は最大でいくらにできるかを求め、出力してください。ただし、どのように操作を行っても K 回の操作を完了できない場合は、-1 を出力してください。

制約

2 \leq N \leq 200
0 \leq M \leq N (N-1)
0 \leq W \leq 10^{16}
1 \leq S \leq N
1 \leq K \leq 10^9
1 \leq u_i, v_i \leq N (1 \leq i \leq M)
-10^7 \leq w_i \leq 10^7 (1 \leq i \leq M)
u_i \neq v_i (1 \leq i \leq M)
i \neq j ならば (u_i, v_i) \neq (u_j, v_j)

入力

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

N M W S K
u_1 v_1 w_1
:
u_M v_M w_M

出力

K 回の操作を完了できる場合には、ゲーム終了時の所持金の最大値を出力せよ。どのように操作を行っても完了できない場合は、-1 を出力せよ。

入力例 1

出力例 1

頂点を 1 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 5 と移動すれば、所持金は 8 円となります。

入力例 2

出力例 2

-1

どのように操作を行っても 4 回の操作を完了することはできません。したがって -1 を出力します。

入力例 3

2 2 0 2 1000000000
1 2 100000
2 1 100000

出力例 3

100000000000000

C - Smaller-Suffix-Free Sequences

実行時間制限: 3 sec / メモリ制限: 1024 MB

配点 : 800 点

問題文

数列 T = (T_1, \ldots, T_L) が smaller-suffix-free であるとは、 i = 2, 3, \ldots, L 全てについて、数列 (T_i, T_{i+1}, \ldots, T_L) が辞書順で T よりも大きいことを指します。たとえば (5) や (1, 1, 2, 3) はsmaller-suffix-freeであり、(3, 2, 1) や (2, 2) は smaller-suffix-free ではありません。

長さ N の数列 A = (A_1, \ldots, A_N) が与えられます。各 i = 1, \ldots, N について、(A_i, A_{i+1}, \ldots, A_j) が smaller-suffix-free であるような最大の j を求めてください。

制約

1 \leq N \leq 2 \times 10^5
1 \leq A_i \leq 2 \times 10^5 (1 \leq i \leq N)

入力

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

N
A_1 A_2 \ldots A_N

出力

出力は N 行からなる。

i 行目には (A_i, A_{i+1}, \ldots, A_j) が smaller-suffix-free であるような最大の j を出力せよ。

入力例 1

6
3 2 1 1 2 3

出力例 1

A_1 から始まる smaller-suffix-free である最長の連続する部分列は (A_1) = (3) です。したがって 1 行目には 1 を出力します。

同様に、(A_2), (A_3, A_4, A_5, A_6), (A_4, A_5, A_6), (A_5, A_6), (A_6) がそれぞれ A_i (2 \leq i \leq 6) から始まる smaller-suffix-free である最長の連続する部分列です。

入力例 2

3
10 10 10

出力例 2

1
2
3

D - Pars/ey

実行時間制限: 3 sec / メモリ制限: 1024 MB

配点: 1100 点

問題文

AtCoder 社の料理長を務めるあなたはよく高橋社長に自慢のハンバーグをふるまっていますが、せっかく仕入れたパセリを高橋社長が食べてくれず困っています。そこであなたは、パセリを一箇所でカットして食べやすくすることにしました。

パセリは N 頂点 N 辺の単純かつ連結な無向グラフで表され、頂点にも辺にも 1 から N までの番号がついています。辺 i は 2 頂点 A_i, B_i をつないでおり、長さは C_i です。

連結な頂点対 (u, v) 全てに対して u, v 間の最短距離を求めたとき、その最大値をパセリの硬さと定義します。

全ての i\ (1 \leq i \leq N) に対して、辺 i のみを取り除いたパセリの硬さを求めてください。

制約

入力はすべて整数
3 \leq N \leq 2 \times 10^5
1 \leq A_i, B_i \leq N
1 \leq C_i \leq 10^9
与えられる無向グラフは単純かつ連結

入力

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

N
A_1 B_1 C_1
:
A_{N} B_{N} C_{N}

出力

N 行出力せよ。i 行目には、辺 i のみを取り除いたパセリの硬さを出力すること。

入力例 1

出力例 1

辺 1 のみを取り除いたパセリにおいて、最短距離は (1, 5) 間の 9 が最大です。
辺 2 のみを取り除いたパセリにおいて、最短距離は (2, 5) 間の 11 が最大です。
辺 3 のみを取り除いたパセリにおいて、最短距離は (1, 5) 間の 10 が最大です。
辺 4 のみを取り除いたパセリにおいて、最短距離は (4, 5) 間の 5 が最大です。
辺 5 のみを取り除いたパセリにおいて、最短距離は (1, 4) 間の 4 が最大です。

入力例 2

出力例 2

入力例 3

30
14 4 848722274
18 12 171265658
8 4 511894372
25 11 330929651
23 19 418973258
22 4 817877182
13 23 222674219
22 16 413782819
29 5 544392908
7 17 144238161
13 27 923626020
24 22 304070169
24 28 791071873
4 27 156167139
21 15 120681393
27 25 59605316
1 2 200687466
5 20 908000896
4 17 52288616
16 30 835920548
30 6 290694093
5 13 650921045
18 13 427412075
24 23 817018683
26 10 693688408
21 16 636579751
15 2 946903174
11 3 261890778
5 9 131214588
20 10 834590409

出力例 3