AtCoder Beginner Contest 278F
// rem: v = -1 にしてしまうと memo[s][v] の indexx で RE.
auto dfs = [&](auto self, ll s, ll v) -> bool {
if(in(v,n) && memo[s][v] != -1){
return memo[s][v];
}
rep(i,n) if(!(s >> i & 1)){
if(!in(v,n) || str[v].back() == str[i].front()){
if(!self(self, s|(1LL<<i), i)) {
return memo[s][v] = true;
}
}
}
return memo[s][v] = false;
};
if(dfs(dfs,0,n)){
cout << "First" << endl;
}else{
cout << "Second" << endl;
}
return 0;
}
*1:s,v)\)で決まる． ここで， \(s \in 2^{N}\) は選んだ文字列の集合， \(v \in N \cup \{*\}\) は最後に選んだ文字． ただし，ゲーム開始時点では \(v = *\) とする．
計算量: 状態が \(O(2^{N}N)\), 遷移が \(O(N)\). 合計で \(O(2^{N}N^{2})\).
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
