Algoogle

Algorithm for Programming Contest

Codeforces 455B A Lot of Games

Category: Codeforces Tag: string

A Lot of Games

問題概要


n個の文字列がある.
2人のプレイヤーが交互に文字列の後ろに1文字追加する.
ただし追加後の文字列はそれ以外の文字列のprefixになっていなければならない.
最終的に追加できなくなったほうが負け.
これを負けた方を先攻にしてk回繰り返す.
最適な行動をとったとき, 勝つのは始め先攻だったほうか, 後攻だったほうか.

解法


まず与えられた文字列でTrie木を作る.
Trie木の根が文字列が空の時に対応していて, そこから先にノードが存在するように辿れば題意の動きができる.
あるノードの勝ち負けは, k=1で同じゲームをそのノードを根とする部分木での先攻の勝ち負けとする.

現在のノードから行けるノードが無いとき, そのノードは明らかに負け.
行けるノードのうち1つでも負けなノードがあれば, そこに進めば現在のノードは勝てる.
また, 行けるノードのうち1つでも勝ちノードがあれば, 現在のノードは負けることも可能.

kが奇数回で先攻が勝つことしか出来ない場合, 先攻の勝ち負け勝ち負け…負け勝ちとなるのは明らか.
kが偶数階で先攻が負けることしか出来ない場合は負け負け負け…負けとなる.
先攻が勝つことも負けることもできるとき, 最後から2番目のゲームまで負け続ければ最終回で先攻で勝てる.

コード


(455B.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i,a) repi(i,0,a)
#define all(u) begin(u),end(u)
#define pb push_back
#define mp make_pair

struct PMA{
    PMA* next[256];
    int matched;
    PMA(){memset(next, 0, sizeof(next)); matched = 0;}
    ~PMA(){for(int i = 0; i < 256; i++) if(next[i]) delete next[i];}
};

PMA *buildPMA(vector<string> pattern){
    PMA *root = new PMA, *now;
    root->next[0] = root;
    for(int i = 0; i < (int)pattern.size(); i++){
        now = root;
        for(int j = 0; j < (int)pattern[i].size(); j++){
            if(now->next[(int)pattern[i][j]] == 0)
                now->next[(int)pattern[i][j]] = new PMA;
            now = now->next[(int)pattern[i][j]];
        }
        now->matched++;
    }
    return root;
}

int rec(PMA *pma){
    int win = 0, lose = 0, cnt = 0;
    rep(i,26) {
        int ni = i + int('a');
        if(pma->next[ni]){
            ++cnt;
            int f = rec(pma->next[ni]);
            win |= (f^2)&2;
            lose |= (f^1)&1;
        }
    }
    if(!cnt) return 1;
    assert((win&1)==0);
    return win | lose;
}

int n, k;
vector<string> ss;

int solve(){
    PMA *root = buildPMA(ss);
    int f = rec(root);
    int win = f&2, lose = f&1;
    return (win and lose) or (win and k%2);
}

void input(){
    scanf("%d%d", &n, &k);
    ss.resize(n);
    rep(i,n) cin >> ss[i];
}

int main(){
    input();
    if(solve()) puts("First");
    else puts("Second");
    return 0;
}

Comments