AtCoder が提供しているABC（AtCoder Beginner Contest）278 のF問題をC++とPythonで解いてみました。ABC278は、2022年11月19日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
F問題 Shiritori（Difficulty : 1452）
問題はリンク先をご覧ください。
bitDPを使ってゲーム問題を解きます。AtCoder Problems による Difficulty は、1452 でした。
解答案
DPを使います。dp[i][c] は、残っている文字列の集合 i、しりとりで使われた最後の文字 c（この文字が、次に選ぶ最初の文字列の最初の文字になっている必要があります）のときに、勝つ文字列を選べる場合に 1、どの文字列を選んでも負けるもしくは文字列が選べない場合に 0 とします。集合 i は、整数と考えて2進数の下位 j bit目が 1 であれば、文字列 Sj は使われず残っているとします。
残っている文字列の集合 i と、次に選ぶ文字列 j、文字 c は、以下を満たす必要があります。
- 集合 i の下位から j bit目が 1 になっている（文字列 j が使われずに残っている）。
- 文字 c と文字列 j の最初の文字が一致している。
この場合、dp[i から j を抜いた集合][文字列 j の最後の文字] が相手の負け（0）になっていれば、文字列 j を選べば勝つことができます。逆にどの文字列を選んでも勝てなければ、負けとなります。また、文字列が選べない場合も負けになります。
集合 i は、値が少ない方から調べていけばよいです（bitDP の考え方です）。初期値は、以下となります。
dp[0][c]=0、c はすべての文字
選べる文字列が無ければ、その時点で負けになるためです。
C++ プログラム例（ABC278F）
プログラムを補足します。
- 文字列は、最初の文字と最後の文字が分かればよいので、それを first_char、last_char として格納します。
- 配列 dp の初期値を定めます（18ー20行目）。
- 上で考察したように dp を更新します。
- すべての j に対して、集合 i の下位から j bit目が 1 になっていて、文字 c と文字列 j の最初の文字が一致していることを確認します。
- dp[i から j を抜いた集合][文字列 j の最後の文字] が相手の負け（0）になっていれば、dp[i][c] は勝ち（1）になります。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> first_char(n);
vector<int> last_char(n);
for (int i = 0; i < n; ++i) {
string s;
cin >> s;
first_char[i] = s[0] - 'a';
last_char[i] = s[s.length() - 1] - 'a';
}
vector<vector<int>> dp(1 << n, vector<int>(26, -1));
for (int c = 0; c < 26; ++c) {
dp[0][c] = 0;
}
for (int i = 1; i < (1 << n); ++i) {
for (int c = 0; c < 26; ++c) {
int w_or_l = 0;
for (int j = 0; j < n; ++j) {
if (((((1 << j) & i) != 0)&&(first_char[j] == c))
&&(dp[i ^ (1 << j)][last_char[j]] == 0)) {
w_or_l = 1;
}
}
dp[i][c] = w_or_l;
}
}
for (int c = 0; c < 26; ++c) {
if (dp[(1 << n) - 1][c] == 1) {
cout << "First" << endl;
return 0;
}
}
cout << "Second" << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC278F）
Python 版も基本的な考え方は同じです。
以下のプログラムは、「Python (CPython 3.11.4)」では、TLE判定となり、「Python (PyPy 3.10-v7.3.12)」で、AC判定となりました。
"""AtCoder Beginner Contest 278 F"""
n = int(input())
first_char = [0] * n
last_char = [0] * n
for i in range(n):
s = input()
first_char[i] = ord(s[0]) - ord('a')
last_char[i] = ord(s[-1]) - ord('a')
dp = [[-1 for _ in range(26)] for _ in range(1 << n)]
for c in range(26):
dp[0][c] = 0
for i in range(1, 1 << n):
for c in range(26):
w_or_l = 0
for j in range(n):
if (i & (1 << j)) != 0 and first_char[j] == c and \
dp[i ^ (1 << j)][last_char[j]] == 0:
w_or_l = 1
dp[i][c] = w_or_l
result = False
for c in range(26):
if dp[(1 << n) - 1][c] == 1:
result = True
print("First" if result else "Second")こちらも「AC」と判定されました。
最後に
ABC354E問題（解説記事）と同じ構造の問題でした。理解を深めるために、この問題を記事にしました。
引き続き ABC の問題を紹介していきます。
