Codeforces Round #406 (Div. 1): A. Berzerk
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;
}