「これまでに使っていない単語の集合」と「最後の文字」のペアを状態に持った DP を行うことでこの問題を解くことができます。

• \(\operatorname{dp}[S][c]\coloneqq\) これまでに使っていない単語の集合が \(S\subseteq\{s _ 1,\ldots,s _ N\}\) であり、最後の文字が \(c\) である状態について、その状態から勝てるとき \(1\) 、そうでないとき \(0\)

であるような DP テーブルを考えます。 このとき、この DP テーブルは次のようにして値を決めることができます。

\[\operatorname{dp}[S][c]=\left\{\!\!\begin{array}{cll}1&&({}^\exists s\in S.\;s[0]=c\wedge\operatorname{dp}[S\setminus\{s\}][s[-1]]=0)\\0&&(\text{otherwise})\end{array}\right. \]

ただし、\(s[0],s[-1]\) はそれぞれ \(s\) の最初の文字、最後の文字を表します。 この式は、「残っている単語のうち、それを言ったら相手を負かせるものがあるとき、かつそのときに限り勝つ」ことを DP の遷移に書き下したものです。

\(\operatorname{dp}[\{s_1,\ldots,s_N\}][c]\) が \(1\) であるような \(c\) が存在すれば高橋くんは勝つことができます。

この DP テーブルを正しく埋めるためには、\(\operatorname{dp}[S][c]\) を計算しようとするより先に \(\operatorname{dp}[S\setminus\{s\}][s[-1]]\) を計算していなければなりません。 この条件はいわゆる bit DP で用いる方法で \(S\) を \(N\operatorname{bit}\) の整数に変換して昇順に計算を行えば満たされます。

文字の種類数を \(\sigma\) として、状態が \(2^N\sigma\) 通りあり、状態 \(1\) つあたり \(O(N)\) 時間かけて DP テーブルの計算を行うので全体で時間計算量は \(O(2^NN\sigma)\) となります。

実装例は以下のようになります。 ここではワードサイズ \(w\) に対して \(\sigma\lt w\) が成り立っていることを仮定した実装をしています。

#include <iostream>
#include <vector>
#include <utility>
#include <string>

int main() {
    using namespace std;

    unsigned N;
    cin >> N;

    // i 番目の文字列の最初の文字/最後の文字
    vector<pair<unsigned char, unsigned char>> info(N);
    for (auto&&[first, last] : info) {
        string S;
        cin >> S;
        first = S.front() - 'a';
        last = S.back() - 'a';
    }

    // dp[S] の c bit 目 = S が残っていて直前の文字が c のときの勝敗
    vector<unsigned> dp(1UL << N);
    for (unsigned S{1}; S < 1UL << N; ++S)
        for (unsigned c{}; c < N; ++c)
            if (1 & S >> c)
                dp[S] |= (1UL & ~dp[S ^ 1UL << c] >> info[c].second) << info[c].first;

    // dp[2^N - 1] に立っているビットがあれば先手の勝ち
    cout << (dp.back() ? "First" : "Second") << endl;

    return 0;
}