🍣
ABC278-F Shiritori
問題概要
文字列
でしりとりをする。先手と後手,どっちが勝ちますか? S_1,S_2,\dots,S_N
なお,ここでのしりとりのルールは次の通りです。自分の手番が回ってきたら,次の条件を満たす整数
を好きに選ぶ。 i(1\leq i\leq N)
(条件):
は,ゲームが開始してから先手,後手のどちらにも選ばれていない i - 「この手番が最初の手番である」か,「直前に選ばれた整数を
として j の最後の文字は S_j の最初の文字に等しい」 S_i
1\leq N\leq 16 -
は整数N -
は英小文字のみからなる長さS_i 以下の空でない文字列10 i \neq j \Rightarrow S_i \neq S_j
リンク
解法
まず,制約をよく見ましょう.
この問題では,数字の使う順番が重要ですが,全探索(
こういう時はbitDPを使うと良いです.今回もそれで行きましょう.
以下のようにdpを定義します.
-
「すでに選んだ数字の集合がdp[X][i]:= 」という状況で手番が回ってきたとき,整数X を選ぶと勝てるだろうか?i (\text{true}/\text{false})
求めるのはすべての
遷移は次のようになっていると分かります.
-
から遷移できるdp[X][i] であってdp[Y][j] なるものがあればdp[Y][j]=\text{true} dp[X][i]=\text{false} - そうじゃないときは
dp[X][i]=\text{true}
直感的に書くなら,
- 相手がうまくやることで勝てるなら,自分は負ける。
- 相手がどうやっても勝てないなら,自分は勝てる。
という感じです.
ちゃんと書くと以下の通りです.
後はこの通り計算していくことで答えが得られます.
計算量は
- dpの状態数は
O(N2^N) - 遷移の計算に
O(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