CodeFestival 2014 上海 コンテスト感想
CodeFestival 2014 上海のコンテストは僕 (JAPLJ) ときゅうり (kyuridenamida) で writer/tester をしていました。
全体的には、セット前半は
- 落ち着く、焦らない
- 気づく
- しっかり実装する
あたりが試される感じで、セット後半はこれといった難問こそないものの、どの問題もそこそこの手応えがあるという感じを目指していました。
2 人で 3 時間 10 問のセットを準備する (しかも参加者は皆かなりの熟練者) ということでかなり大変ではありましたが、その分思い入れも強いセットになったので、ここで各問題について振り返ってみます。(解説をするわけではありません、オフィシャルな解説がそのうち出るはず？もう出てる？)
僕の書いた writer/tester 解も載せます。テンプレを略しているので謎の関数が出てきますが in() は整数入力、chmax(a, b) は a = max(a, b) で chmin も同様です。ライブラリとかも略。
A - Lock (原案: kyuridenamida)
A 問題なので簡単ではあるけれども意外と詰まってしまうこともあって、冷静な思考力と実装力でけっこう時間に差がつく、良い A 問題だなあという感じ。(もちろん熟練者相手という前提があるからこれが良い A 問題になるわけですが)
int N, D[5]; void solve(int u) { if (u == N) { for (int i = 0; i < N; ++i) { putchar('0' + D[i]); } puts(""); return; } solve(u + 1); for (int i = 0; i < 9; ++i) { (D[u] += 1) %= 10; solve(u + 1); } } int main() { N = in(); for (int i = 0; i < N; ++i) { putchar('9'); } puts(""); solve(0); return 0; }
B - n-th Points (原案: japlj)
これも A 問題と同様、落ち着いて式を出せるかという感じの問題。こういう系は細かい ±1 のミスとか数式のミスをどれだけ無くせるか (またはミスしたときに迅速に修正できるか) が効いてくるので、実際にコンテストで目にするとちょっと「うっ」となってしまうかもしれません。
void solve(Int n) { Int lo = -1, hi = 1000000000; while (hi - lo > 1) { Int mid = (hi + lo) / 2; if (n < 2 * mid * (mid + 1) + 1) { hi = mid; } else { lo = mid; } } if (lo >= 0) { n -= 2 * lo * (lo + 1) + 1; } Int x = -hi + (n + 1) / 2; printf("%lld %lld\n", x, (hi - llabs(x)) * (n % 2 ? -1 : 1)); } int main() { int Q = in(); for (int i = 0; i < Q; ++i) { solve(lin() - 1); } return 0; }
C - Regular Polygon (原案: japlj)
パッと見ちょっとびっくりするけど、気づけばとても簡単というタイプの問題。こういうのを前半に 1 つは仕込んでおきたかったので。
ところで、日本語だと "正多角形" となって分かりやすいと思うんですが、"Regular Polygon" になってしまうとやっぱりちょっと分かりづらいので、ちゃんと定義を書いた方が良かったなあという反省もあり。
Int X[1024], Y[1024]; map<pair<Int, Int>, int> M; int main() { int N = in(); for (int i = 0; i < N; ++i) { X[i] = lin(); Y[i] = lin(); M[make_pair(X[i], Y[i])] = i; } for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { if (i == j) { continue; } Int dx = X[j] - X[i], dy = Y[j] - Y[i]; Int x2 = X[j] - dy, y2 = Y[j] + dx; Int x3 = x2 - dx, y3 = y2 - dy; pair<Int, Int> p2(x2, y2), p3(x3, y3); if (M.count(p2) != 0 && M.count(p3) != 0) { int R[4]; puts("4"); R[0] = i; R[1] = j; R[2] = M[p2]; R[3] = M[p3]; sort(R, R + 4); for (int k = 0; k < 4; ++k) { printf("%d\n", R[k] + 1); } return 0; } } } puts("0"); return 0; }
D - Maze (原案: japlj)
これを見て、「とりあえず後回し」という判断ができるかどうかは結構戦略的に重要なのではないかなと思います。難しいわけではないけれど、実装が重そう/煩雑そうであることを見抜いて、こういう問題でハマると後々辛そうだなあと考えて飛ばす、というのが想定していた上位陣の流れというか。
最小費用流をしてもいいですし BFS して BFS してもいいです。どっちでも実装難度はそこまで変わらないかな？と思ったけど、これは結構人によりそうですね。最小費用流の扱いに (復元なども含めて) 慣れているとそっちが楽なのかも。
static int DR[] = {1, 0, -1, 0, 0}, DC[] = {0, 1, 0, -1, 0}; int H, W; char F[64][64]; int D[64][64]; void bfs1(int sr, int sc) { for (int i = 1; i <= H; ++i) { for (int j = 1; j <= W; ++j) { D[i][j] = INF; } } queue<int> qr, qc; qr.push(sr); qc.push(sc); D[sr][sc] = 0; while (!qr.empty()) { int r = qr.front(); qr.pop(); int c = qc.front(); qc.pop(); for (int d = 0; d < 4; ++d) { int rr = r + DR[d], cc = c + DC[d]; if (F[rr][cc] != '#' && D[rr][cc] > D[r][c] + 1) { D[rr][cc] = D[r][c] + 1; qr.push(rr); qc.push(cc); } } } } int V[64][64][64][64], P1[64][64][64][64], P2[64][64][64][64]; struct state { int r1, c1, r2, c2; state(int r1, int c1, int r2, int c2) : r1(r1), c1(c1), r2(r2), c2(c2) { } int& v() { return V[r1][c1][r2][c2]; } int& p1() { return P1[r1][c1][r2][c2]; } int& p2() { return P2[r1][c1][r2][c2]; } bool valid() { return (r1 != r2 || c1 != c2 || F[r1][c1] == 'S'); } }; bool bfs2(int ar, int ac, int br, int bc) { char ca = 'a', cb = 'b'; if (D[ar][ac] > D[br][bc]) { swap(ar, br); swap(ac, bc); swap(ca, cb); } queue<state> Q; Q.emplace(ar, ac, br, bc); while (!Q.empty()) { const state s = Q.front(); Q.pop(); if (F[s.r1][s.c1] == 'S' && F[s.r2][s.c2] == 'S') { state p = s; while (p.r1 != ar || p.c1 != ac || p.r2 != br || p.c2 != bc) { if (F[p.r1][p.c1] == '.') F[p.r1][p.c1] = ca; if (F[p.r2][p.c2] == '.') F[p.r2][p.c2] = cb; p = state(p.r1 + DR[p.p1()], p.c1 + DC[p.p1()], p.r2 + DR[p.p2()], p.c2 + DC[p.p2()]); } return true; } if (D[s.r1][s.c1] < D[s.r2][s.c2]) { for (int d = 0; d < 4; ++d) { int rr = s.r2 + DR[d], cc = s.c2 + DC[d]; state ss(s.r1, s.c1, rr, cc); if (F[rr][cc] != '#' && D[rr][cc] < D[s.r2][s.c2] && ss.valid() && ss.v() == 0) { ss.v() = 1; ss.p1() = 4; ss.p2() = (d + 2) % 4; Q.push(ss); } } } else { for (int d1 = 0; d1 < 4; ++d1) { for (int d2 = 0; d2 < 4; ++d2) { state ss(s.r1 + DR[d1], s.c1 + DC[d1], s.r2 + DR[d2], s.c2 + DC[d2]); if (F[ss.r1][ss.c1] != '#' && F[ss.r2][ss.c2] != '#' && D[ss.r1][ss.c1] < D[s.r1][s.c1] && D[ss.r2][ss.c2] < D[s.r2][s.c2] && ss.valid() && ss.v() == 0) { ss.v() = 1; ss.p1() = (d1 + 2) % 4; ss.p2() = (d2 + 2) % 4; Q.push(ss); } } } } } return false; } int main() { H = in(); W = in(); int sr, sc, ar, ac, br, bc; memset(F, '#', sizeof(F)); for (int i = 1; i <= H; ++i) { scanf("%s", &F[i][1]); F[i][W + 1] = '#'; for (int j = 1; j <= W; ++j) { if (F[i][j] == 'S') { sr = i; sc = j; } else if (F[i][j] == 'A') { ar = i; ac = j; } else if (F[i][j] == 'B') { br = i; bc = j; } } } bfs1(sr, sc); if (bfs2(ar, ac, br, bc)) { for (int i = 1; i <= H; ++i) { F[i][W + 1] = '\0'; puts(&F[i][1]); } } else { puts("NA"); } return 0; }
E - Game (原案: kyuridenamida)
最初見たときは「ありがちな期待値 DP だな」という感想でしたが、期待値 DP の基本的な式のたて方や漸化式のループ解消といった基礎的な部分から、1プレー (最大 4 ステージ) まとめて考えると計算量が 27 倍とか 81 倍になってかなり厳しいみたいな絶妙な設定まであって、意外と面白いなというのが今の感想です。
提出された解を眺めているとやっぱりこういうのはメモ化再帰がすっきりしそうだなーという感じで、僕はループで書いてしまって結構見た目がえらいことになってしまいました。そういう所 (実装に大きく差が出る点) もなかなか面白い。
const double INFF = 1e12; double dp[128][128][128][4]; int main() { int N1 = in(); int N2 = in(); int N3 = in(); double P1 = in() / 100.0; double P2 = in() / 100.0; double P3 = in() / 100.0; for (int i = 0; i <= 3; ++i) { dp[0][0][0][i] = 0.0; } for (int n1 = 0; n1 <= N1; ++n1) { for (int n2 = 0; n2 <= N2; ++n2) { for (int n3 = 0; n3 <= N3; ++n3) { if (n1 + n2 + n3 == 0) { continue; } dp[n1][n2][n3][0] = INFF; if (n1) chmin(dp[n1][n2][n3][0], dp[n1 - 1][n2][n3][1] + 1 / P1); if (n2) chmin(dp[n1][n2][n3][0], dp[n1][n2 - 1][n3][1] + 1 / P2); if (n3) chmin(dp[n1][n2][n3][0], dp[n1][n2][n3 - 1][1] + 1 / P3); dp[n1][n2][n3][1] = INFF; if (n1) chmin(dp[n1][n2][n3][1], P1 * dp[n1 - 1][n2][n3][2] + (1 - P1) * dp[n1][n2][n3][0]); if (n2) chmin(dp[n1][n2][n3][1], P2 * dp[n1][n2 - 1][n3][2] + (1 - P2) * dp[n1][n2][n3][0]); if (n3) chmin(dp[n1][n2][n3][1], P3 * dp[n1][n2][n3 - 1][2] + (1 - P3) * dp[n1][n2][n3][0]); dp[n1][n2][n3][2] = INFF; if (n1) chmin(dp[n1][n2][n3][2], P1 * dp[n1 - 1][n2][n3][0] + (1 - P1) * dp[n1][n2][n3][0]); if (n2) chmin(dp[n1][n2][n3][2], P2 * dp[n1][n2 - 1][n3][3] + (1 - P2) * dp[n1][n2][n3][0]); if (n3) chmin(dp[n1][n2][n3][2], P3 * dp[n1][n2][n3 - 1][3] + (1 - P3) * dp[n1][n2][n3][0]); dp[n1][n2][n3][3] = INFF; if (n1) chmin(dp[n1][n2][n3][3], P1 * dp[n1 - 1][n2][n3][0] + (1 - P1) * dp[n1][n2][n3][0]); if (n2) chmin(dp[n1][n2][n3][3], P2 * dp[n1][n2 - 1][n3][0] + (1 - P2) * dp[n1][n2][n3][0]); if (n3) chmin(dp[n1][n2][n3][3], P3 * dp[n1][n2][n3 - 1][0] + (1 - P3) * dp[n1][n2][n3][0]); } } } printf("%.9f\n", dp[N1][N2][N3][0]); return 0; }
F - Yakiniku (原案: japlj)
僕が原案を出した問題の中だとたぶん唯一、「作ろうとして作った問題」ではなくて「自然にできた問題」です。シンプルな設定でなかなか綺麗な解法 (累積積) が出てきてお気に入りです。
segtree を書いてもよいし log とって累積和にしてもよいです。
int S[100050], T[100050], C[200050]; double seg[1<<19]; void init() { for (int i = 0; i < (1<<19); ++i) { seg[i] = 1.0; } } void update(int x, double v) { x += (1 << 18); seg[x] = v; x >>= 1; while (x > 0) { seg[x] = seg[2 * x] * seg[2 * x + 1]; x >>= 1; } } double calc(int l, int r, int x = 1, int L = 0, int R = 1<<18) { if (l == L && r == R) { return seg[x]; } double res = 1.0; int mid = (L + R) / 2; if (l < mid) res *= calc(l, min(r, mid), 2 * x + 0, L, mid); if (r > mid) res *= calc(max(l, mid), r, 2 * x + 1, mid, R); return res; } int main() { int N = in(); vector<int> ts; for (int i = 0; i < N; ++i) { S[i] = in(); T[i] = in(); ts.push_back(S[i]); ts.push_back(T[i]); } sort(ts.begin(), ts.end()); init(); memset(C, 0, sizeof(C)); for (int i = 0; i < N; ++i) { S[i] = lower_bound(ts.begin(), ts.end(), S[i]) - ts.begin(); T[i] = lower_bound(ts.begin(), ts.end(), T[i]) - ts.begin(); ++C[S[i]]; --C[T[i] + 1]; } for (int i = 1; i <= 2 * N; ++i) { C[i] += C[i - 1]; } for (int i = 0; i < N; ++i) { update(T[i], 1.0 - 1.0 / C[T[i]]); } for (int i = 0; i < N; ++i) { double ok = calc(S[i], T[i]) / C[T[i]]; double sc = calc(S[i], T[i] + 1); printf("%.9f %.9f\n", 1.0 - ok - sc, sc); } return 0; }
G - Ammunition Dumps (原案: kyuridenamida)
僕はこの原案を提案されたのを見た瞬間に「全域木の数え上げかな」と分かったので (知識さえあれば) かなり簡単な問題だと思っていましたが、意外と分からないものというか個人差がかなりあるようで、最終的に準急とすぬけome さんの 2 人にしか解かれなかったのはかなりびっくりでした。(準急とすぬけだけが解いたのは H だった……)
問題文は、うーん。どういう風に書くのがよかったんでしょうね……。設定と問題自体はそこまで複雑ではないのに、ちゃんと書こうとして色々考えているとどうしても問題文がわかりにくくなってしまって、力量不足だなあ……という感じ。日本語力も鍛えたい。
int I[32][32]; char F[32][32]; const Int MO = 1000000009; Int pow(Int x, Int e) { Int v = 1; for (; e; e >>= 1, (x *= x) %= MO) { if (e & 1) { (v *= x) %= MO; } } return v; } Int inv(Int x) { return pow(x, MO - 2); } int main() { int R = in(); int C = in(); int V = 0; for (int i = 0; i < R; ++i) { scanf("%s", F[i]); for (int j = 0; j < C; ++j) { if (F[i][j] == 'W') { I[i][j] = V++; } } } vector<vector<Int>> A(V, vector<Int>(V, 0)); for (int i = 0; i < R; ++i) { for (int j = 0; j < C; ++j) { if (F[i][j] == '.') { continue; } static int DR[] = {1, 0, -1, 0}, DC[] = {0, 1, 0, -1}; for (int d = 0; d < 4; ++d) { int r = i, c = j; while (true) { r += DR[d]; c += DC[d]; if (r < 0 || c < 0 || r >= R || c >= C) { break; } if (F[r][c] == 'W') { ++A[I[i][j]][I[i][j]]; --A[I[i][j]][I[r][c]]; break; } } } } } Int res = 1; --V; for (int i = 0; i < V; ++i) { if (A[i][i] == 0) { int piv = i + 1; while (piv < V && A[piv][piv] == 0) { ++piv; } if (piv == V) { res = 0; break; } swap(A[i], A[piv]); } Int iv = inv(A[i][i]); for (int j = i + 1; j < V; ++j) { if (A[j][i] == 0) { continue; } Int ma = iv * A[j][i] % MO; for (int k = 0; k < V; ++k) { A[j][k] = (A[j][k] - A[i][k] * ma % MO + MO) % MO; } } } for (int i = 0; i < V; ++i) { (res *= A[i][i]) %= MO; } printf("%lld\n", res); return 0; }
H - Dungeon (原案: japlj)
最初は賢い DP とか貪欲みたいな感じで綺麗に解けないかなあと試行錯誤していましたが、結局フローに落ち着いてしまって、なんだかつまらなくなったな……と思っていました。しかし、いざ自分でちゃんと実装してみて、またコンテストの様子も見ていると、最小費用流のアルゴリズムの仕組みや計算量などについてしっかり問う問題、という印象で今ではわりとお気に入りです。
int A[1024], B[1024]; int main() { int N = in(); for (int i = 0; i < N; ++i) { A[i] = in(); B[i] = in(); } MCF::init(602); int S = 600, T = 601; Int allD = 0; vector<int> key, treasure, enemy; map<int, int> kv, tv; for (int i = 0; i < N; ++i) { if (A[i] == 0) { MCF::ae(S, key.size(), 1, 0); key.push_back(i); kv[i] = key.size() - 1; } else if (A[i] == 1) { MCF::ae(300 + treasure.size(), T, 1, 0); treasure.push_back(i); tv[i] = treasure.size() - 1; } else { allD += B[i]; enemy.push_back(i); } } for (const int k : key) { for (const int t : treasure) { Int damage = B[k], def = B[t]; for (const int e : enemy) { if (e > max(k, t)) { damage -= def; } } if (damage < 0) { MCF::ae(kv[k], 300 + tv[t], 1, damage); } } } MCF::solve(S, T); printf("%lld\n", allD + MCF::minc); return 0; }
I - Obstruction (原案: japlj)
Lapin Noir と似てる……似てない？というか、間違いなく類題です。とはいえ、実際にやることはそこそこ違う、後半にこういった考察+軽実装問題が欲しかった、(そもそも問題数が不足していた)という感じで出題しました。
個人的にはこういうの結構苦手で時間がかかってしまうんですが、後半の問題の中ではとっつきやすいというか、あれやこれやと考えてみやすい感じで (しかも得意な人にはすぐ解ける感じで) 解いた人数的には (オープンの方でも) 人気でした。
int DR[] = {1, 0, -1, 0}, DC[] = {0, 1, 0, -1}; int N; char F[1024][1024]; bool G[1024][1024]; int C[1024][1024]; void toggle(int r, int c) { G[r][c] = true; for (int d = 0; d < 4; ++d) { int rr = r + DR[d], cc = c + DC[d]; if (0 <= rr && rr < N && 0 <= cc && cc < N) { ++C[rr][cc]; } } } int main() { N = in(); for (int i = 0; i < N; ++i) { scanf("%s", F[i]); } queue<int> qr, qc; qr.push(N - 1); qc.push(N - 1); toggle(N - 1, N - 1); while (!qr.empty()) { int r = qr.front(); qr.pop(); int c = qc.front(); qc.pop(); for (int d = 0; d < 4; ++d) { int rr = r + DR[d], cc = c + DC[d]; if (0 <= rr && rr < N && 0 <= cc && cc < N && !G[rr][cc]) { if (F[r][c] == '#' || C[rr][cc] >= 2) { qr.push(rr); qc.push(cc); toggle(rr, cc); } } } } puts(G[0][0] ? "YES" : "NO"); return 0; }
J - XORAND (原案: japlj)
見るからに重そうなデータ構造で殴る系の問題っぽいです。が、実際はそこまで難しくない事実/テクニックなどの積み重ねで、実装もそんなに重いわけではありません。
- 範囲 AND は高々 31 通りの値しかとらない。
- 範囲 XOR は累積 XOR をとっておけば S[a] XOR S[b] で出せる。
- S[x] を Trie に入れておけば範囲 XOR を最小化できる。
- Trie を永続化しておけば右端固定の範囲 XOR を最小化できる。
と分けてみると、本質は永続で、どれもそこまで難しいわけではないなーという感じです。
const int MAXN = 100050; #define bit(A, i) (((A) >> i) & 1) struct trie { int minidx, ptr[2]; trie() { minidx = INF; ptr[0] = ptr[1] = -1; } } pool[1<<22]; int T; int trie_alloc(int from = -1) { pool[T] = from >= 0 ? trie(pool[from]) : trie(); return T++; } int trie_insert(int p, int i, int a) { int res = T, cur = trie_alloc(p); pool[cur].minidx = i; for (int b = 30; b >= 0; --b) { int x = bit(a, b); pool[cur].ptr[x] = p < 0 ? trie_alloc() : trie_alloc(pool[p].ptr[x]); cur = pool[cur].ptr[x]; pool[cur].minidx = i; if (p >= 0) { p = pool[p].ptr[x]; } } return res; } int trie_search(int p, int ma, int x) { int res = 0; for (int b = 30; b >= 0; --b) { int y = bit(x, b); for (int t = 0; t < 2; ++t) { int pp = pool[p].ptr[y ^ t]; if (pp >= 0 && pool[pp].minidx <= ma) { res |= (y ^ t) << b; p = pp; break; } } } return res; } int roots[MAXN]; int A[MAXN], X[MAXN], B[MAXN][32]; int main() { int N = in(); int Q = in(); for (int i = 0; i < N; ++i) { A[i] = in(); X[i] = (i > 0 ? X[i - 1] : 0) ^ A[i]; } T = 0; roots[N] = trie_alloc(); for (int i = N - 1; i >= 0; --i) { roots[i] = trie_insert(roots[i + 1], i, X[i]); } for (int i = 0; i < 31; ++i) { B[N][i] = N; } for (int i = N - 1; i >= 0; --i) { for (int j = 0; j < 31; ++j) { if (bit(A[i], j)) { B[i][j] = B[i + 1][j]; } else { B[i][j] = i; } } } int pans = 0; for (int i = 0; i < Q; ++i) { int l = in(); int r = in(); if (i) { l = (l + abs(pans) % N) % N + 1; r = (r + abs(pans) % N) % N + 1; } --l; --r; int a = A[l]; pans = numeric_limits<int>::min(); while (l < r) { int nl = r; for (int b = 0; b < 31; ++b) { if (bit(a, b)) { chmin(nl, B[l][b]); } } chmax(pans, a - (X[r] ^ trie_search(roots[l], nl - 1, X[r]))); for (int b = 0; b < 31; ++b) { if (bit(a, b) && B[l][b] == nl) { a ^= (1 << b); } } l = nl; } printf("%d\n", pans); } return 0; }
