問題一覧 > 通常問題

No.1613 Rush and Remove

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

問題文

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もしくは右上の雲マークをクリックしてアカウントを作成してください。