問題一覧 > 通常問題

No.1613 Rush and Remove

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 63
作問者 : 👑 ygussany / テスター : tatyam chocorusk
8 ProblemId : 6520 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-07-22 01:44:26

問題文

R.R. 君はゲームが好きで，次のようなゲームを考えました．

  • 2 人プレイヤーのゲームであり，手番は交互に訪れる． 自分の手番での操作が不可能となったプレイヤーの負け，他方のプレイヤーの勝ちとする．
  • H×W のマス目が盤面であり，上から i (1≤i≤H) 番目，左から j (1≤j≤W) 番目のマスを (i,j) で表す．
  • 各マスの状態は，駒がちょうど 1 個置かれているか，駒が置かれていないかのいずれかである．
  • 手番のプレイヤーは，以下の一連の操作をちょうど 1 回行う．
    • 駒が置かれているマス (i,j) (1≤i≤H, 1≤j≤W) を 1 つ選ぶ．
    • i 以下の正整数 i∗ であって，マス (i∗,j),(i∗+1,j),…,(i−1,j) に駒が 1 個も置かれていないようなものを 1 つ選ぶ．
    • マス (i,j) から駒を取り除き，マス (i∗,j),(i∗+1,j),…,(i−1,j) に駒を 1 個ずつ置く．

ゲームの初期盤面が与えられるので，2 人のプレイヤーが勝ちを目指して最善を尽くした場合に，先手と後手のどちらが勝つのかを判定してください．

入力

H W
B1
B2
 ⋮
BH

  • 1≤H,W≤300
  • Bi (1≤i≤H) は o と . からなる長さ W の文字列である．
  • Bi の左から 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もしくは右上の雲マークをクリックしてアカウントを作成してください。