Codeforces Round #406 (Div. 1): A. Berzerk

,

http://codeforces.com/contest/786/problem/A

solution

再帰的に埋めていく。$O(N^2)$。

手番が$y \in \{ \mathrm{First}, \mathrm{Second} \}$でモンスターが座標$x$にいるときの結果$f(y, x) \in \{ \mathrm{Win}, \mathrm{Lose}, \mathrm{Loop} \}$を更新していく。 $f(y, 1) \gets \mathrm{Lose}$から始めて、$\mathrm{Win}$/$\mathrm{Lose}$の確定したものを埋めていく。 $x = 1$以外の$\mathrm{Lose}$は、各座標に$\mathrm{Win}$に遷移する可能性が残っている$\delta_i \in s_y$の数のようなものを持たせておいて、それが$0$になったら$\mathrm{Lose}$に確定させるのがよい。

implementation

再帰でやるのが素直だが、なぜかqueueで書いていた。

#include <cstdio>
#include <vector>
#include <array>
#include <tuple>
#include <queue>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;
int main() {
    // input
    int n; scanf("%d", &n);
    array<int, 2> k;
    array<vector<int>, 2> s;
    repeat (y,2) {
        scanf("%d", &k[y]);
        s[y].resize(k[y]);
        repeat (i,k[y]) scanf("%d", &s[y][i]);
    }
    // compute
    enum result_t { LOOP = 0, WIN = 1, LOSE = 2 };
    array<vector<result_t>, 2> result = {{ vector<result_t>(n, LOOP), vector<result_t>(n, LOOP) }};
    array<vector<int>, 2> cnt = {{ vector<int>(n, k[0]), vector<int>(n, k[1]) }};
    queue<pair<bool, int> > que;
    que.emplace(false, 0);
    que.emplace(true,  0);
    while (not que.empty()) {
        bool y; int x; tie(y, x) = que.front(); que.pop();
        assert (result[y][x] == LOOP);
        result[y][x] = LOSE;
        for (int d1 : s[not y]) {
            int nx = (x - d1 + n) % n;
            if (nx == 0) continue;
            if (result[not y][nx] == WIN) continue;
            assert (result[not y][nx] == LOOP);
            result[not y][nx] = WIN;
            for (int d2 : s[y]) {
                int nnx = (nx - d2 + n) % n;
                if (nnx == 0) continue;
                if (not -- cnt[y][nnx]) {
                    que.emplace(y, nnx);
                }
            }
        }
    }
    // output
    repeat (y,2) {
        repeat (x,n-1) {
            if (x) printf(" ");
            printf("%s", result[y][x+1] == WIN ? "Win" : result[y][x+1] == LOSE ? "Lose" : "Loop");
        }
        printf("\n");
    }
    return 0;
}