Time Limit: 2 sec / Memory Limit: 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
Time Limit: 6 sec / Memory Limit: 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
5 6 0 1 5 1 2 1 2 3 2 3 4 1 4 1 -1 3 1 -4 2 5 7
出力例 1
8
頂点を 1 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 5 と移動すれば、所持金は 8 円となります。
入力例 2
5 6 10 1 4 1 2 1 1 3 3 2 4 6 5 4 0 3 5 2 2 5 1
出力例 2
-1
どのように操作を行っても 4 回の操作を完了することはできません。したがって -1 を出力します。
入力例 3
2 2 0 2 1000000000 1 2 100000 2 1 100000
出力例 3
100000000000000
Time Limit: 3 sec / Memory Limit: 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
1 2 6 6 6 6
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
Time Limit: 3 sec / Memory Limit: 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
5 1 2 2 2 3 2 3 1 3 3 4 1 4 5 5
出力例 1
9 11 10 5 4
- 辺 1 のみを取り除いたパセリにおいて、最短距離は (1, 5) 間の 9 が最大です。
- 辺 2 のみを取り除いたパセリにおいて、最短距離は (2, 5) 間の 11 が最大です。
- 辺 3 のみを取り除いたパセリにおいて、最短距離は (1, 5) 間の 10 が最大です。
- 辺 4 のみを取り除いたパセリにおいて、最短距離は (4, 5) 間の 5 が最大です。
- 辺 5 のみを取り除いたパセリにおいて、最短距離は (1, 4) 間の 4 が最大です。
入力例 2
6 1 2 1 2 3 1 3 1 1 1 4 10 2 5 1 3 6 1
出力例 2
13 12 13 3 12 12
入力例 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
6749598432 6749598432 6749598432 6749598432 6749598432 6749598432 7303505702 5015716191 6749598432 6749598432 6749598432 7303505702 6749598432 6749598432 5971361289 6749598432 6548910966 4857711627 6749598432 6749598432 6749598432 4261075407 6749598432 7303505702 6055910024 5971361289 5971361289 6749598432 6749598432 5221319615