問題一覧 > 教育的問題

No.2168 双頭ヒドラゲーム

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 8
作問者 : 👑 p-adicp-adic / テスター : testestesttestestest
1 ProblemId : 8893 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-04-10 22:35:18

注

コンテスト終了後に、タイトルとタグを編集しました。問題の内容自体に変更はございません。

問題文

$3$ 種類の文字(と|と)のみからなる文字列が双頭ヒドラであるということを以下のように再帰的に定義します：

  • 空文字列は双頭ヒドラである。
  • 任意の双頭ヒドラ $t_0$ と $t_1$ と $t_2$ に対し、(と $t_0$ と|と $t_1$ と)と $t_2$ をこの順に結合した文字列は双頭ヒドラである。
以下、集合などの再帰的定義について詳しくない人向けの説明を書きます。（クリックで開く）

　

$X$ を集合とします。例えば $X$ は特定の文字のみからなる文字列の集合などです。今回説明するのは、$X$ の部分集合などを再帰的に定義する際の数学特有の言い回しです。

例えば $X$ の要素 $c$ と非負整数 $n,m$ と写像 $F \colon X^n \times X^m \to X$ を用いて次のような書き方をすることがあります：

　

$X$ の部分集合 $A$ を以下のように再帰的に定める：

  • $c \in A$ である。
  • 任意の $(a,t) \in A^n \times X^m$ に対し、$F(a,t) \in A$ である。

　

これはあくまで例であって、今回は $2$ つの条件としましたが一般には $2$ つとは限りませんし、写像を用いるのではなく関係を用いることもあります。再帰的定義の一般の定式化[1] 6.1.1 Definitionはかなり抽象的なので、今回はこの問題を解く上で必要な例のみを考えることにします。

ここで重要なのは、この定義文は $A$ が単に $2$ つの条件を全て満たす $X$ の任意の部分集合であるという意味を持つのではなく、次の定義文を表すということです：[1] 6.1.2 Definitionおよびその直後の段落参照

　

$X$ の部分集合 $A$ を、以下の $2$ 条件を全て満たす $X$ の部分集合 $B$ 全体の共通部分と定める：

  • $c \in B$ である。
  • 任意の $(a,t) \in B^n \times X^m$ に対し、$F(a,t) \in B$ である。

　

$B = X$ とすると確かに上の $2$ 条件を満たすので、条件を満たす $B$ 全体の集合は空でなく共通部分が定義されます。そして $A$ は $2$ 条件を満たす $B$ のうち最小のものである、ということが結果的に従います。

このように、部分集合の再帰的定義はただの条件の列挙ではなく最小性も含意するよう約束されていることに注意しましょう。ただしこれはあくまで再帰的定義に限った約束であり、通常の定義では最小性はもちろん含意されませんし、そもそも再帰的定義のような自己言及を通常の定義で行うと多くの場合循環論法となり定義が破綻します。

　

さて、$X$ 上の $1$ 項関係は $X$ の部分集合と等価であるため、$X$ 上の $1$ 項関係の再帰的定義においても同様の規則が適用されます。具体的には、

　

$X$ の要素が良い項であるということを以下のように再帰的に定める：

  • $c$ は良い項である。
  • 任意の $(a,t) \in X^n \times X^m$ に対し、$a$ の任意の成分が良い項であるならば、$F(a,t)$ も良い項である。

　

のように「良い項である」という $1$ 項関係の再帰的定義を書いた場合、これは「良い項である」という述語が $2$ 条件を満たす任意の $1$ 項関係を表すという意味ではありません。上の定義文は次の定義文と等価なものになります：

　

$X$ の要素 $x$ が良い項であるということを、以下の $2$ 条件を全て満たす $X$ の任意の部分集合 $B$ に対し $x \in B$ が成り立つということと定める：

  • $c \in B$ である。
  • 任意の $(a,t) \in B^n \times X^m$ に対し、$F(a,t) \in B$ である。

　

以上を踏まえると、今回の双頭ヒドラの再帰的定義は次の定義文と等価です：

　

$3$ 種類の文字(と|と)のみからなる文字列 $t$ が双頭ヒドラであるということを、(と|と)のみからなる文字列のみからなる任意の集合 $B$ に対し $B$ が以下の $2$ 条件を全て満たすならば $t \in B$ が成り立つということと定める：

  • 空文字列は $B$ の要素である。
  • $B$ の任意の要素 $t_0$ と $t_1$ と $t_2$ に対し、(と $t_0$ と|と $t_1$ と)と $t_2$ をこの順に結合した文字列は $B$ の要素である。

　

元の言い回しと比べてだいぶ複雑な言い回しとなりましたね。このような複雑な言い回しを避けるために、数学では今回紹介した簡潔な言い回しが定義され採用されているわけです。

例えば後で参考文献として挙げる

  • [1] における$1$ 項関係「be an $\mathcal{L}$-term」や「be an $\mathcal{L}$-formula」の再帰的定義など
  • [2] における集合 $T$ および $1$ 項関係「be a principal term」の再帰的定義など
  • [3] における集合 $B(\alpha,\beta)$ や $\textrm{K}_{\kappa}(\gamma)$ の再帰的定義など

で実際にそういった言い回しが採用されています。

　

参考文献

  1. W. Pohlers, "Proof Theory - The first step into impredicativity", Springer, 2010.
  2. W. Buchholz, "A New System of Proof-Theoretic Ordinal Functions", Annals of Pure and Applied Logic 32 (1986), pp. 195--207.
  3. M. Rathjen, "Ordinal Notations Based on a Weakly Mahlo Cardinal", Archive for Mathematical Logic 29 (1990), pp. 249--263.

　

　

空文字である双頭ヒドラを死んだ双頭ヒドラと呼びます。死んだ双頭ヒドラでない双頭ヒドラを生きた双頭ヒドラと呼びます。

双頭ヒドラ $t$ が温厚な双頭ヒドラであるとは、ある双頭ヒドラ $t'$ が存在して $t$ が $t'$ と(|)をこの順に結合した文字列であるということです。

温厚な双頭ヒドラでない生きた双頭ヒドラを獰猛な双頭ヒドラと呼びます。

　

双頭ヒドラ $t$ と非負整数 $n$ に対し、双頭ヒドラ $t[n]$ を以下のように再帰的に定義します：

  • $t$ が死んだ双頭ヒドラであるならば、$t[n]$ は死んだ双頭ヒドラである。
  • ある双頭ヒドラ $t_0$ と $t_1$ と $t_2$ が存在して $t$ が(と $t_0$ と|と $t_1$ と)と $t_2$をこの順に結合して得られる文字列であるとする。
    • $t_2$ が生きた双頭ヒドラであるならば、$t[n]$ は(と $t_0$ と|と $t_1$ と)と $t_2[n]$をこの順に結合して得られる文字列である。
    • $t_0$ と $t_1$ と $t_2$ が死んだ双頭ヒドラであるならば、$t[n]$ は死んだ双頭ヒドラである。
    • $t_0$ と $t_2$ が死んだ双頭ヒドラでありかつ $t_1$ が生きた双頭ヒドラであるとする。
      • $n = 0$ ならば、$t[n]$ は(| と $t_1[0]$ と)をこの順に結合して得られる文字列である。
      • $n > 0$ ならば、$t[n]$ は(| と $t_1[n]$ と)と $t[n-1]$ をこの順に結合して得られる文字列である。
    • $t_1$ と $t_2$ が死んだ双頭ヒドラでありかつ $t_0$ が生きた双頭ヒドラであるとする。
      • $n = 0$ ならば、$t[n]$ は(と $t_0[0]$ と|)をこの順に結合して得られる文字列である。
      • $n > 0$ ならば、$t[n]$ は(と $t_0[n]$ と|と $t[n-1]$ と)をこの順に結合して得られる文字列である。
    • $t_2$ が死んだ双頭ヒドラでありかつ $t_0$ が生きた双頭ヒドラでありかつ $t_1$ が温厚な双頭ヒドラであるとする。
      • $n = 0$ ならば、$t[n]$ は(と $t_0[0]$ と|(と $t_0$ と|と $t_1[0]$ と)(|))をこの順に結合して得られる文字列である。
      • $n > 0$ ならば、$t[n]$ は(と $t_0[n]$ と|と $t[n-1]$ と)をこの順に結合して得られる文字列である。
    • $t_2$ が死んだ双頭ヒドラでありかつ $t_0$ が生きた双頭ヒドラでありかつ $t_1$ が獰猛な双頭ヒドラであるならば、$t[n]$ は(と $t_0$ と|と $t_1[n]$ と)をこの順に結合して得られる文字列である。

　

双頭ヒドラ大好きbotは双頭ヒドラが大好きなbotです。

双頭ヒドラ大好きbot大好きbotは双頭ヒドラ大好きbotが大好きなbotです。もちろん２体は別物です。

相異なる生きた双頭ヒドラ $t_0$ と $t_1$ に対して、双頭ヒドラ大好きbotと双頭ヒドラ大好きbot大好きbotの２体をプレイヤーとする初期値 $t_0$ と $t_1$ の双頭ヒドラゲームを次のように定めます：

  1. まず双頭ヒドラ大好きbotには双頭ヒドラ $t_0$ が与えられ、双頭ヒドラ大好きbot大好きbotには双頭ヒドラ $t_1$ が与えられる。
  2. 次に２体のプレイヤーは双頭ヒドラ大好きbotから始めてお互いの双頭ヒドラが一致するまで交互に次の操作を行う：
    • 非負整数 $n$ を $1$ つ選び、自分の双頭ヒドラ $t$ を $t[n]$ に置き換える。

このゲームが有限回の操作で終わる時、最後に操作を行ったプレイヤーの勝利となります。

　

入力に生きた双頭ヒドラ $T_0$ と $T_1$ が与えられます。

初期値 $T_0$ と $T_1$ の双頭ヒドラゲームにおいて２体が自分の勝利を目指し相手の勝利を避けるように最善の手順を選んだ時、有限回の操作で勝敗がつくか否かと、勝敗がつく場合にどちらが勝利するかを求めてください。

入力

入力は次の形式で標準入力から与えられます： 

$T_0$
$T_1$

双頭ヒドラ $T_0$ が $1$ 行目に与えられ、双頭ヒドラ $T_1$ が $2$ 行目に与えられます。

制約

入力は以下の制約を満たします：

  • $T_0$ は文字列としての長さが $30$ 以下の生きた双頭ヒドラ
  • $T_1$ は文字列としての長さが $30$ 以下の生きた双頭ヒドラ
  • $T_0$ と $T_1$ は相異なる

出力

初期値 $T_0$ と $T_1$ の双頭ヒドラゲームにおいて２体が自分の勝利を目指し相手の勝利を避けるように最善の手順を選んだ時、

  • 有限回の操作で勝敗がつかないならば-1
  • 先攻である双頭ヒドラ大好きbotが勝利するならば0
  • 後攻である双頭ヒドラ大好きbot大好きbotが勝利するならば1

と出力してください。

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

サンプル

サンプル1
入力
(|)(|)
(|)
出力
0

まず双頭ヒドラ大好きbotの双頭ヒドラが(|)(|)、双頭ヒドラ大好きbot大好きbotの双頭ヒドラが(|)で初期化されます。

次に双頭ヒドラ大好きbotが $n = 0$ と選ぶと双頭ヒドラ大好きbotの双頭ヒドラが(|)に置き換わります。これは双頭ヒドラ大好きbot大好きbotの双頭ヒドラと一致します。

以上より、双頭ヒドラ大好きbotの必勝となります。

サンプル2
入力
(|)
(|)(|)
出力
1

まず双頭ヒドラ大好きbotの双頭ヒドラが(|)、双頭ヒドラ大好きbot大好きbotの双頭ヒドラが(|)(|)で初期化されます。

次に双頭ヒドラ大好きbotが非負整数 $n$ を選び、その双頭ヒドラ $t$ が $t[n]$ に置き換わりますが、これは $n$ の選び方によらず死んだ双頭ヒドラとなります。特にそれは双頭ヒドラ大好きbot大好きbotの双頭ヒドラと異なります。

更に双頭ヒドラ大好きbot大好きbotが $n=0$ と選ぶと、その双頭ヒドラ $t$ が $t[0]$ に置き換わりますが、これは生きた双頭ヒドラ(|)です。特にそれは双頭ヒドラ大好きbotの双頭ヒドラと異なります。

今度は双頭ヒドラ大好きbotが非負整数 $n$ を選び、その双頭ヒドラ $t$ が $t[n]$ に置き換わりますが、$t$ は死んだ双頭ヒドラであるため $t[n]$ も $n$ の選び方によらず死んだ双頭ヒドラとなります。特にそれは双頭ヒドラ大好きbot大好きbotの双頭ヒドラと異なります。

再度双頭ヒドラ大好きbot大好きbotが $n=0$ と選ぶと、その双頭ヒドラ $t$ が $t[0]$ に置き換わりますが、これは死んだ双頭ヒドラであり双頭ヒドラ大好きbotの双頭ヒドラと一致します。

以上より、双頭ヒドラ大好きbot大好きbotの必勝となります。

サンプル3
入力
(|(|))
(|)(|)(|)
出力
0
サンプル4
入力
(|)(|)(|)
(|(|))
出力
1
サンプル5
入力
((|)|)
(|(|(|)))
出力
0
サンプル6
入力
(|(|(|)))
((|)|)
出力
1
サンプル7
入力
((|)(|)|)
((|)|((|)|))
出力
0
サンプル8
入力
((|)|((|)|))
((|)(|)|)
出力
1

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