No.1613 Rush and Remove
タグ : / 解いたユーザー数 63
作問者 : 👑 ygussany / テスター : tatyam chocorusk
問題文
R.R. 君はゲームが好きで,次のようなゲームを考えました.
- $2$ 人プレイヤーのゲームであり,手番は交互に訪れる. 自分の手番での操作が不可能となったプレイヤーの負け,他方のプレイヤーの勝ちとする.
- $H \times W$ のマス目が盤面であり,上から $i$ $(1 \le i \le H)$ 番目,左から $j$ $(1 \le j \le W)$ 番目のマスを $(i, j)$ で表す.
- 各マスの状態は,駒がちょうど $1$ 個置かれているか,駒が置かれていないかのいずれかである.
- 手番のプレイヤーは,以下の一連の操作をちょうど $1$ 回行う.
- 駒が置かれているマス $(i, j)$ $(1 \le i \le H,~1 \le j \le W)$ を $1$ つ選ぶ.
- $i$ 以下の正整数 $i^*$ であって,マス $(i^*, j), (i^* + 1, j), \dots, (i - 1, j)$ に駒が $1$ 個も置かれていないようなものを $1$ つ選ぶ.
- マス $(i, j)$ から駒を取り除き,マス $(i^*, j), (i^* + 1, j), \dots, (i - 1, j)$ に駒を $1$ 個ずつ置く.
ゲームの初期盤面が与えられるので,$2$ 人のプレイヤーが勝ちを目指して最善を尽くした場合に,先手と後手のどちらが勝つのかを判定してください.
入力
$H$ $W$ $B_{1}$ $B_{2}$ $\vdots$ $B_{H}$
- $1 \le H, W \le 300$
- $B_{i} \ (1 \le i \le H)$ は
o
と.
からなる長さ $W$ の文字列である. - $B_{i}$ の左から $j$ 文字目が
o
であれば初期盤面でマス $(i, j)$ に駒が置かれており,そうでなければ駒が置かれていない.
出力
両者が最善を尽くしたときに先手が勝つ場合は First
を,後手が勝つ場合は Second
を出力してください.
サンプル
サンプル 1
入力
4 1 . . o .
出力
First
先手プレイヤーが可能な操作は $(i, i^*) = (3, 1), (3, 2), (3, 3)$ のいずれかです. いずれの場合でもマス $(3, 1)$ から駒が取り除かれ,
- $(i, i^*) = (3, 1)$ の場合にはマス $(1, 1)$ と $(2, 1)$ に駒が置かれ,
- $(i, i^*) = (3, 2)$ の場合にはマス $(2, 1)$ のみに駒が置かれ,
- $(i, i^*) = (3, 3)$ の場合には新たに駒は置かれません.
サンプル 2
入力
3 1 . o o
出力
Second
先手プレイヤーが可能な操作は $(i, i^*) = (2, 1), (2, 2), (3, 3)$ のいずれかです.
先手が $(2, 2), (3, 3)$ を選ぶと,後手は残った方の駒を取り除いて勝てます.
先手が $(2, 1)$ を選ぶと,マス $(1, 1)$ と $(3, 1)$ に駒が置かれた状態になります. 後手は $(i, i^*) = (3, 2)$ として操作を行い,マス $(1, 1)$ と $(2, 1)$ に駒が置かれた状態にします. すると,先手はいずれかの駒を取り除くことしかできず,後手は残った方の駒を取り除いて勝てます.
したがって,先手の選択に依らず後手が必ず勝てます.
サンプル 3
入力
4 4 o.oo .oo. oo.o oo..
出力
First
サンプル 4
入力
4 4 ..oo .oo. oo.o oo..
出力
Second
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。