Zenn
🍣

ABC278-F Shiritori

2023/01/28に公開
AtCoder
tech

問題概要

文字列 S_1,S_2,\dots,S_N でしりとりをする。先手と後手,どっちが勝ちますか?
なお,ここでのしりとりのルールは次の通りです。

自分の手番が回ってきたら,次の条件を満たす整数 i(1\leq i\leq N) を好きに選ぶ。
(条件):

  1. iは,ゲームが開始してから先手,後手のどちらにも選ばれていない
  2. 「この手番が最初の手番である」か,「直前に選ばれた整数を j として S_j の最後の文字は S_i の最初の文字に等しい」
  • 1\leq N\leq 16
  • N は整数
  • S_i は英小文字のみからなる長さ 10 以下の空でない文字列
  • i \neq j \Rightarrow S_i \neq S_j

リンク

解法

まず,制約をよく見ましょう.
Nがめちゃくちゃ小さいです!!!これをうまく使っていきましょう.

この問題では,数字の使う順番が重要ですが,全探索(N!通り)することはできません.
こういう時はbitDPを使うと良いです.今回もそれで行きましょう.

以下のようにdpを定義します.

  • dp[X][i]:=「すでに選んだ数字の集合が X 」という状況で手番が回ってきたとき,整数 i を選ぶと勝てるだろうか? (\text{true}/\text{false})

求めるのはすべての i に対する dp[\{i\}][i] のORです.

次のようなことになっていることが分かります.

  • dp[X][i] から遷移できる dp[Y][j] であって dp[Y][j]=\text{true} なるものがあれば dp[X][i]=\text{false}
  • そうじゃないときは dp[X][i]=\text{true}

直感的に書くなら,

  • 相手がうまくやることで勝てるなら,自分は負ける。
  • 相手がどうやっても勝てないなら,自分は勝てる。

という感じです.

遷移を詰めると,以下が得られます.

dp[X][i]=\neg \bigvee_{\mathtt{back}_i=\mathtt{front}_j , j\not\in X}{dp[X\cup\{j\}][j]}

\bigvee は論理和を表します.

\mathtt{front}_i,\mathtt{back}_iで,それぞれS_iの最初の文字,最後の文字を表します.

後はこの通り計算していくことで答えが得られます.

計算量は

  • dpの状態数は O(N2^N)
  • 遷移の計算に O(N)

であることから O(N^22^N) となり十分間に合います.

実装

この通りに実装すればいいです...が,普通にやると少し大変かもしれません.メモ化再帰を用いた実装が分かりやすいと思います.

#include <bits/stdc++.h>
using namespace std;

bool dp[1 << 16][16], flag[1 << 16][16];

int n;
char front[16], back[16];

bool f(int X, int i) {
    if (flag[X][i]) return dp[X][i];  // メモしてたらreturn
    flag[X][i] = true;

    for (int j = 0; j < n; j++) {
        if (X & (1 << j)) continue;  // すでに使ってたらダメ
        if (back[i] != front[j]) continue;

        if (f(X | (1 << j), j))
            return dp[X][j] =
                       false;  // 相手が最善を尽くすとき,相手が勝てるならfalse;
    }
    return dp[X][i] = true;  // どう来ても勝てるときはtrue
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        front[i] = s.front();
        back[i] = s.back();
    }

    for (int i = 0; i < n; i++) {
        if (f(1 << i, i)) {
            // 先手がiから始めてめて勝てるとき
            cout << "First\n";
            return 0;
        }
    }
    cout << "Second\n";
    return 0;
}

Discussion