問題一覧 > 通常問題

No.3140 Weird Parentheses Game

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 131
作問者 : Nauclhlt🪷 / テスター : 👑 p-adic
ProblemId : 12089 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-05-15 08:29:51

問題文

対応が取れた括弧列の定義

文字列 $X$ が対応が取れた括弧列であるとは、次を満たすことをいいます。

  • $X$ に連続部分文字列として含まれる()を削除する操作を $0$ 回以上繰り返して $X$ を空文字列とすることができる

例えば()(())や()()()()は対応が取れた括弧列ですが、))((や)()()(などは対応が取れた括弧列ではありません。


長さ $N$ の対応が取れた括弧列 $S$ があります。

First君とSecond君はこれから $S$ を使ってゲームを行います。ゲームはFirst君を先手として以下のように進行します。

  • 手番のプレイヤーは、$S$ の(空でない)連続部分文字列であって対応が取れた括弧列であるものをひとつ選び、削除する
  • もしも操作ができなければ、最後に操作を行った方の勝ちとしてゲームを終了する

2人ともが自身の勝利を目指して最適に行動するとしたとき、どちらが勝つかを求めてください。

入力

$N$
$S$
  • $1\leq N\leq 1000$
  • $S$ は長さ $N$ の対応が取れた括弧列

出力

First君が勝つならFirst、Second君が勝つならSecondを1行に出力してください。

ジャッジは完全な一致になっています。例えばfirstやSECONDは正しい解だとしてもACとして受理されません。

最後に改行してください。

サンプル

サンプル1
入力
6
()(())
出力
First

例えば、以下のような進行が考えられます。

  • First君が $S$ の $4$ 文字目から $5$ 文字目までを選ぶ。$S$ は()()となる
  • Second君が $S$ の $1$ 文字目から $2$ 文字目までを選ぶ。$S$ は()となる
  • First君が $S$ の $1$ 文字目から $2$ 文字目までを選ぶ。$S$ は空文字列となる
  • Second君は操作ができないため、最後に操作を行ったFirst君の勝ちとしてゲームが終了する

この例では両者が最適な行動を行っているとは限りませんが、最適な行動を行ったとしてもFirst君の勝ちとなります。よってFirstを出力します。

サンプル2
入力
2
()
出力
First

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。