Time Limit: 2 sec / Memory Limit: 256 MB
問題文
N 枚のカードがあり、i (1 ≦ i ≦ N) 枚目のカードには整数 A_i が書かれています。ゲーム好きの兄妹はこれらのカードを使ってゲームをしようとしています。
- 最初に全てのカードを、カードに書かれた整数が見えるようにテーブルの上に並べる。
- プレイヤーは自分のターンに、テーブルの上にあるカードからちょうど 1 枚のカードを選んで取る。
- テーブルの上にカードがなくなるまで、交互にターンを繰り返す。
- 最終的に、自分が取ったカードに書かれた整数の和がプレイヤーの スコア となる。
2 人ともが自分のスコアを出来るだけ大きくしようとしたとき、先手のスコアはいくつになるでしょうか？
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 ... A_N
- 1 行目には、カードの枚数を表す整数 N (1 ≦ N ≦ 1000) が与えられる。
- 2 行目には、各カードに書かれた整数を表す N 個の整数が空白区切りで与えられる。このうち i (1 ≦ i ≦ N) 番目の整数 A_i (1 ≦ A_i ≦ 1000) は、i 枚目のカードに書かれた整数を表す。
出力
先手のスコアを 1 行に出力せよ。出力の末尾に改行を入れること。
入力例1
2 400 628
出力例1
628
この例では、ゲームは以下のように進行します。
- 先手が 2 枚目のカードを取る。
- 後手が 1 枚目のカードを取る。
このとき、先手のスコアは 628 となり、後手のスコアは 400 となります。
入力例2
5 2 5 9 6 5
出力例2
16
この例では、ゲームは以下のように進行します。
- 先手が 3 枚目のカードを取る。
- 後手が 4 枚目のカードを取る。
- 先手が 2 枚目のカードを取る。
- 後手が 5 枚目のカードを取る。
- 先手が 1 枚目のカードを取る。
このとき、先手のスコアは 16 となり、後手のスコアは 11 となります。
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
H 行 W 列のマス目とチェスの駒が 1 つあります。i (1 ≦ i ≦ H) 行目 j (1 ≦ j ≦ W) 列目のマスを、マス (i,j) と呼ぶことにします。このとき、左上のマスがマス (1,1) で右下のマスがマス (H,W) となっています。また、マス (1,1) 以外のいくつかのマスには障害物が置いてあります。ゲーム好きな兄妹がこのマス目と駒を使って以下のようなゲームをしようとしています。
- 最初、駒をマス (1,1) に置く。
- プレイヤーは自分のターンに、駒を 1 つ下か 1 つ右下か 1 つ右のマスのうち障害物のないいずれかのマスに動かさなければならない。つまり、駒がマス (i,j) にあるときは、マス (i+1,j) かマス (i+1,j+1) かマス (i,j+1) のうち障害物のないいずれかのマスに動かさなければならない。ただしこのとき、マス目の外に動かすことはできない。すなわち、i = H のときは下や右下には動かせず、j = W のときは右下や右には動かせない。
- 交互にターンを繰り返し、自分のターンに駒を動かせなくなったプレイヤーの負けとなる（もう一方のプレイヤーが勝ちとなる）。
2 人ともが勝ちを目指して最適な戦略をとったとき、先手と後手のどちらが勝つでしょうか？
入力
入力は以下の形式で標準入力から与えられる。
H W
S_{1,1}S_{1,2}..S_{1,W}
S_{2,1}S_{2,2}..S_{2,W}
:
S_{H,1}S_{H,2}..S_{H,W}
- 1 行目には、2 つの整数 H (1 ≦ H ≦ 100), W (1 ≦ W ≦ 100) が空白区切りで与えられる。これは、マス目の行数が H、マス目の列数が W であることを表す。
- 2 行目からの H 行には、マスの情報が与えられる。このうち i (1 ≦ i ≦ H) 行目には、W 個の文字が与えられる。このうちの j (1 ≦ j ≦ W) 個目の文字 S_{i,j} は、マス (i,j) の情報を表す
#または.の文字である。#である場合はマス (i,j) に障害物があることを表し、.である場合はマス (i,j) に障害物がないことを表す。ただし、S_{1,1} は.であることが保証される。
部分点
この問題には部分点が設定されている。
- H ≦ 4 かつ W ≦ 4 を満たすデータセット 1 に正解した場合は、30 点が与えられる。
- 全てのテストケースに正解した場合は、上記とは別に 70 点が与えられる。
出力
先手が勝つ場合は First を、後手が勝つ場合は Second を 1 行に出力せよ。出力の末尾に改行を入れること。
入力例1
2 3 .#. ...
出力例1
First
ゲームは、例えば以下のように進行します。o は駒の位置を表しています。
o#. ...
- 1 ターン目：駒はマス (1,1) にあります。駒を下か右下に動かすことができます。先手は、駒を下に動かしました。
.#. o..
- 2 ターン目：駒はマス (2,1) にあります。駒は右にしか動かせません。後手は、駒を右に動かしました。
.#. .o.
- 3 ターン目：駒はマス (2,2) にあります。駒は右にしか動かせません。先手は、駒を右に動かしました。
.#. ..o
- 4 ターン目：駒はマス (2,3) にあります。後手は、駒を動かすことができないため負けとなります。
後手がどのように駒を動かしても、先手は適切な動かし方をすることによって勝つことができるため First を出力します。
入力例2
4 4 .... ...# .... .#..
出力例2
Second
先手がどのように駒を動かしても、後手は適切な動かし方をすることによって勝つことができるため Second を出力します。
入力例3
11 44 ............................................ ............................................ ............................................ .....#.....#####....####.....####....####... ....#.#....#....#..#....#...#....#..#....#.. ....#.#....#....#..#.............#..#....#.. ...#####...#####...#..........###....####... ...#...#...#....#..#.............#..#....#.. ..#.....#..#....#..#....#...#....#..#....#.. ..#.....#..#....#...####.....####....####... ............................................
出力例3
Second
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
N 個の大きな茶碗が横 1 列に並んでいます。左から i (0 ≦ i ≦ N-1) 番目の茶碗を茶碗 i と呼ぶことにします。茶碗 i (1 ≦ i ≦ N-1) には整数 C_i が書かれており、中には A_i 個の豆が入っています。茶碗 0 には整数は書かれておらず、豆も入っていません。ゲーム好きな兄妹がこれらの茶碗と豆を使って以下のようなゲームをしようとしています。
- プレイヤーは自分のターンに、茶碗 0 以外の茶碗に入っている豆 1 つ選んで取り出す。
- 茶碗 i から豆を取り出したときは、茶碗 i - C_i, 茶碗 i - C_i + 1, ..., 茶碗 i-1 のいずれかの茶碗に豆を入れなければならない。
- 交互にターンを繰り返し、自分のターンに選べる豆がなくなったプレイヤーの負けとなる（もう一方のプレイヤーが勝ちとなる）。
2 人ともが勝ちを目指して最適な戦略をとったとき、先手と後手のどちらが勝つでしょうか？
入力
入力は以下の形式で標準入力から与えられる。
N
C_1 A_1
C_2 A_2
:
C_{N-1} A_{N-1}
- 1 行目には、茶碗の個数を表す整数 N (2 ≦ N ≦ 10^5) が与えられる。
- 2 行目からの N-1 行には、茶碗の情報が与えられる。このうち i (1 ≦ i ≦ N-1) 行目には、2 つの整数 C_i (1 ≦ C_i ≦ i), A_i (0 ≦ A_i ≦ 10^9) が与えられる。これは、茶碗 i に書かれた整数が C_i であり、中に A_i 個の豆が入っていることを表す。ただし、いずれかの茶碗には豆が入っていること、すなわち A_i の合計が 0 でないことが保証される。
部分点
この問題には部分点が設定されている。
- N ≦ 100 かつ A_i ≦ 10 を満たすデータセット 1 に正解した場合は、80 点が与えられる。
- N ≦ 100 を満たすデータセット 2 に正解した場合は、上記とは別に 20 点が与えられる。
- 全てのテストケースに正解した場合は、上記とは別に 4 点が与えられる。
出力
先手が勝つ場合は First を、後手が勝つ場合は Second を 1 行に出力せよ。出力の末尾に改行を入れること。
入力例1
3 1 0 1 1
出力例1
Second
ゲームは、例えば以下のように進行します。
- 1 ターン目：先手が茶碗 2 の豆を選んで取り出し、茶碗 1 に豆を入れる
- 2 ターン目：後手が茶碗 1 の豆を選んで取り出し、茶碗 0 に豆を入れる
- 3 ターン目：豆を選ぶことができないため、先手の負けとなる
この例の場合、各プレイヤーの行動の選択肢はどのターンにも 1 つしかないため必ずこのような結果となります。
入力例2
7 1 1 2 0 1 0 2 0 4 1 3 0
出力例2
First
ゲームは、例えば以下のように進行します。
- 1 ターン目：先手が茶碗 5 の豆を選んで取り出し、茶碗 4 に豆を入れる
- 2 ターン目：後手が茶碗 4 の豆を選んで取り出し、茶碗 2 に豆を入れる
- 3 ターン目：先手が茶碗 2 の豆を選んで取り出し、茶碗 1 に豆を入れる
- 4 ターン目：後手が茶碗 1 の豆を 1 つ選んで取り出し、茶碗 0 に豆を入れる
- 5 ターン目：先手が茶碗 1 の豆を選んで取り出し、茶碗 0 に豆を入れる
- 6 ターン目：豆を選ぶことができないため、後手の負けとなる
その他の進行でも、後手がどのような行動をとっても先手が適切な行動をとることによって勝つことができます。
入力例3
7 1 1 2 0 1 9 2 10 4 3 3 5
出力例3
Second
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
N 頂点 M 辺の有向グラフがあります。このグラフの頂点 i には、整数 X_i が書かれています。ゲーム好きな兄妹がこのグラフと 1 つのチェスの駒を使ってゲームをしようとしています。
- 最初、駒を頂点 1 に置く。
-
プレイヤーは自分のターンに、以下のいずれかちょうど 1 つの操作をしなければならない。
- 移動 : 駒を別の頂点にちょうど 1 回移動させる。駒が頂点 i にある場合は、頂点 i から頂点 j に向かう辺があるような頂点 j にのみ移動させることができる。
- 終了宣言 : ゲームを終了させる。
- 交互にターンを繰り返し、どちらかのプレイヤーが終了宣言をするか、後手が 10^9 回移動をさせた直後の時点でゲームは終了となり、その時点で駒がある頂点に書かれた整数がこのゲームの スコア となる。
先手のプレイヤーがスコアを出来るだけ大きくするような行動を取り、後手のプレイヤーがスコアを出来るだけ小さくするような行動を取るとき、ゲームのスコアはいくつになるでしょうか？
入力
入力は以下の形式で標準入力から与えられる。
N M X_1 X_2 ... X_N A_1 B_1 A_2 B_2 : A_M B_M
- 1 行目には、グラフの頂点の個数を表す整数 N (1 ≦ N ≦ 100,000) と辺の個数を表す M (1 ≦ M ≦ 200,000) が空白区切りで与えられる。
- 2 行目には、各頂点に書かれた整数を表す N 個の整数が空白区切りで与えられる。このうち i (1 ≦ i ≦ N) 番目の整数 X_i (0 ≦ X_i ≦ 10^9) は、頂点 i に書かれた整数を表す。
- 3 行目からの M 行には、辺の情報が与えられる。このうち i (1 ≦ i ≦ M) 行目には、2 つの整数 A_i,B_i (1 ≦ A_i ≦ N, 1 ≦ B_i ≦ N, A_i \neq B_i) が空白区切りで与えられる。これは、グラフに頂点 A_i から頂点 B_i に向かう有向辺があることを表す。ただし、同じ辺が 2 回与えられることはないこと、すなわち p \neq q のとき A_p \neq A_q または B_p \neq B_q が成り立つことが保証される。
部分点
この問題には部分点が設定されている。
- N ≦ 1000 かつ M ≦ 2000 を満たすデータセット 1 に正解した場合は、30 点が与えられる。
- 全てのテストケースに正解した場合は、上記とは別に 70 点が与えられる。
出力
ゲームのスコアを 1 行に出力せよ。出力の末尾に改行を入れること。
入力例1
3 3 1 3 2 1 2 2 3 3 1
出力例1
2
この例では、ゲームは以下のように進行します。
- 先手が移動を選択し、駒を頂点 1 から頂点 2 に移動させる。
- 後手が移動を選択し、駒を頂点 2 から頂点 3 に移動させる。
- 先手が終了宣言を選択し、ゲームを終了させる。このときスコアは 2 となる。
先手がどのような行動を取っても、後手が適切な行動を取ることによってスコアを 2 より大きくすることは出来ません。
また、後手がどのような行動を取っても、先手が適切な行動を取ることによってスコアを 2 より小さくすることは出来ません。
入力例2
4 5 1 3 2 1 1 2 2 3 3 1 2 4 4 3
出力例2
1
この例では、ゲームは以下のように進行します。
- 先手が移動を選択し、駒を頂点 1 から頂点 2 に移動させる。
- 後手が移動を選択し、駒を頂点 2 から頂点 4 に移動させる。
- 先手が移動を選択し、駒を頂点 4 から頂点 3 に移動させる。
- 後手が移動を選択し、駒を頂点 3 から頂点 1 に移動させる。
- 先手が移動を選択し、駒を頂点 1 から頂点 2 に移動させる。
- 後手が移動を選択し、駒を頂点 2 から頂点 4 に移動させる。
- （上の流れをしばらく繰り返す）
- 後手が 10^9 回目の移動を選択し、駒を頂点 3 から頂点 1 に移動させる。
- この時点でゲームが終了し、スコアは 1 となる。
先手がどのような行動を取っても、後手が適切な行動を取ることによってスコアを 1 より大きくすることは出来ません。
また、後手がどのような行動を取っても、先手が適切な行動を取ることによってスコアを 1 より小さくすることは出来ません。