ABC278 - F - Shiritori
問題
$ DP_{ij}\coloneqq未使用の文字列集合が$ i(bit列)で、最後に使われた文字列が$ S_jのときの手番プレイヤーの勝敗
相手に負け盤面を($ 1つでも)渡せるならその手番プレイヤーの勝ちである。
よって負けの状態から$ 1手で遷移できる状態はすべて勝ち。
$ DP_{ij}の$ 1手前は、$ iの$ jbit目を$ 1にして(これを$ xと表す)、$ S_jとしりとりになるような($ S_jの先頭と$ S_kの末尾が一致している)$ kを最後に使った状態$ DP_{xk}である。
最後の手が$ jなのに$ iの$ jbit目が$ 1であるような、矛盾する状態もDPテーブルの中に含まれるが、そのような状態は無視する。
初手$ 1111\dots1は前の手がないのでよしなに遷移する。
code: f.py
N = int(input())
M = (1 << N) - 1
DP = [0 * N for _ in range(1 << N)] for i in range(1 << N):
for j in range(N):
if (i >> j) & 1: continue
x = i | (1 << j)
for k in range(N):
if x != M:
if (x >> k) & 1: continue
print("First" if 1 in DP-1 else "Second")