ABC278-F Shiritori

問題概要

文字列$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$

リンク

• https://atcoder.jp/contests/abc278/tasks/abc278_f

解説

似たようなゲームの問題に、EDPC-Kがあります。


先手,後手とあるけど、先手が勝てるか?という判定問題を解けばいい。

まず、制約をよく見る。$N$がめちゃくちゃ小さい!!!これをうまく使っていこう。
結論を言うと、bitDP+後退解析を使うと解ける。bitDP,後退解析そのものについてはほかの記事を参照されたい。
次のようなDPを行う。

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

求めるのは$\bigvee_{i} dp[\{i\}][i]$です。
次のようなことになっていることが分かる。

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

「移れる」と書いたが、これは$S_i$の最後の文字が$S_j$の最初の文字に等しいということ。
わかりやすく書くなら、

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

という感じ。この通りにちゃんと書くと、次が成り立つ。

• $$dp[X][i]=\neg \bigvee_{back_i=front_j\land j\not\in X}{dp[X\cup\{j\}][j]}$$

$front_i,back_i$で、それぞれ$S_i$の最初の文字,最後の文字を表します。

実装

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

#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;
}

• AC:29ms