Codeforces Round #206 (Div. 1) B. Game with Strings

問題

codeforces.com

解法

まず, 問題文をちゃんと把握します。
普通の問題と違って, この問題の場合だと, それまでに通ってきた文字列が一致していれば, 自分のターンに遷移させるマスが変わっても良いというのがポイントです。
と言ってもアレなので例を挙げます。
5
cbbbb
bcbbb
aacbb
aaacb
aaaac

という入力では, FIRST が 'c' に動いてから, SECOND が右側の 'b' に動けば SECOND の勝ち確な感じがしますが, この問題の場合だと左上からの文字列が "cb" となっていれば何でも良いので, FIRST が次のマスを選択する際, 「'c' -> 'c' の下の 'b'」 と文字列を構成したと解釈してよく, FIRST は c -> b -> a と進めます。こうなると, 逆に FIRST のほうが勝ち確になるので, この入力の場合の出力は FIRST です。

問題を把握したところで, 解法を説明します。

各ターン step において, どのマスにいることになるかは, たかだか n 通りしかありません。すなわち, step ターン後に (y, x) にいるとすると, y+x = step, 0 <= y < n, 0 <= x < n となるような (y, x) の組しかありません。

よって, 各ターン時に上のような「自分はこのマスにいたと解釈しても良い」というのは, たかだか 2^n 通りしかありません。
よって, dp[step][mask] = (step ターン時に, 自分がいると解釈できるマスは mask で表されている際の, a の数と b の数の差の最大(小)値) とすれば, うまく時間内に問題に答えることが出来ます。

下のコードでは mask には, そのターンにおいていると解釈出来る y 座標を取りました。FIRST のターンの時は, a - b がなるべく大きくなるような戦略を取り, SECOND のターンの時はなるべく小さくなるような戦略を取ります。

メモ化再帰の遷移では, 次にどの文字が来ることがありえるのかでアルファベット(a から z)を場合分けしています。

const int MAXN = 20;
const int INF = 1e8;

string T[MAXN];
int n;
int memo[2*MAXN][1<<MAXN];

int dfs(int step, int mask) {
    int& ret = memo[step][mask];
    if (ret != -INF) return ret;
    if (step == 2*n-2) return ret = 0;
    if (step%2) ret = -INF;
    else ret = INF;
    for (char c = 'a'; c <= 'z'; c++) {
        int nmask = 0;
        for (int y = 0; y < n; y++) {
            if ((mask&(1<<y)) == 0) continue;
            int x = step-y;
            if (x < 0 || x >= n) continue;
            int ny = y+1, nx = x+1;
            if (ny < n && T[ny][x] == c) nmask |= 1<<ny;
            if (nx < n && T[y][nx] == c) nmask |= 1<<y;
        }
        if (nmask) {
            int tmp = dfs(step+1, nmask);
            if (c == 'a') tmp++;
            else if (c == 'b') tmp--;
            if (step%2) ret = max(ret, tmp);
            else ret = min(ret, tmp);
        }
    }
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; i++) cin >> T[i];
    for (int i = 0; i < 2*MAXN; i++) for (int j = 0; j < (1<<MAXN); j++) memo[i][j] = -INF;
    int ans = dfs(0, 1);
    if (T[0][0] == 'a') ans++;
    else if (T[0][0] == 'b') ans--;
    if (ans > 0) cout << "FIRST" << endl;
    else if (ans == 0) cout << "DRAW" << endl;
    else cout << "SECOND" << endl;
    return 0;
}