AtCoder による 第四回 アルゴリズム実技検定 の問題を解きました.
L - マンションの改築
難しい. 偶数番目を奇数番目に分けて, 差分を imos で管理する.
$A_1=H_1$, $A_i=H _ i-H _ {i-1}$ $(1\lt i\leq N)$ として, 下図のように要素を並べる.
すると, クエリ 1 は上行の全要素を $+v$ して下行の全要素を $-v$ する操作である. 同様に, クエリ 2 は上行の $A_1$ 以外の要素を $-v$ して下行の全要素を $+v$ する操作である. クエリ 3 は, $A_i\leftarrow A_i+v$, $A_{i+1}\leftarrow A _ {i+1} -v$ とすればよい.
各クエリの後に 0 の個数が求まればよいので, 行ごとに値の頻度を Map で管理することを考える. クエリ 1 とクエリ 2 は Map の key を全て変化させる操作なので, 愚直に変更するわけにはいかない. そこで, 各行に対して下駄を表す変数 (プログラム中の g0, g1) を持ち, クエリ 1 とクエリ 2 ではこの下駄を $\pm v$ することにすればよい (クエリ 2 では のみ別で処理する必要があるので注意).
public static void solve(ExtendedScanner sc, FastPrintStream pw) { int n = sc.nextInt(); int q = sc.nextInt(); int n0 = n - n / 2; int n1 = n / 2; long[] h0 = new long[n0]; long[] h1 = new long[n1]; for (int i = 0; i < n; i++) { if ((i & 1) == 0) { h0[i >> 1] = sc.nextLong(); } else { h1[i >> 1] = sc.nextLong(); } } HashMap<Long, Integer> m0 = new HashMap<>(); HashMap<Long, Integer> m1 = new HashMap<>(); add1(m0, h0[0]); for (int i = n - 1; i > 0; i--) { if ((i & 1) == 0) { h0[i >> 1] -= h1[(i >> 1) - 1]; add1(m0, h0[i >> 1]); } else { h1[i >> 1] -= h0[i >> 1]; add1(m1, h1[i >> 1]); } } long g0 = 0, g1 = 0; while (q --> 0) { int t = sc.nextInt(); if (t == 1) { int v = sc.nextInt(); g0 += v; g1 -= v; } else if (t == 2) { int v = sc.nextInt(); g0 -= v; g1 += v; sub1(m0, h0[0]); h0[0] += v; add1(m0, h0[0]); } else { int u = sc.nextInt() - 1; int v = sc.nextInt(); if ((u & 1) == 0) { sub1(m0, h0[u >> 1]); h0[u >> 1] += v; add1(m0, h0[u >> 1]); if (u >> 1 < n1) { sub1(m1, h1[u >> 1]); h1[u >> 1] -= v; add1(m1, h1[u >> 1]); } } else { sub1(m1, h1[u >> 1]); h1[u >> 1] += v; add1(m1, h1[u >> 1]); if (u >> 1 < n0 - 1) { sub1(m0, h0[(u >> 1) + 1]); h0[(u >> 1) + 1] -= v; add1(m0, h0[(u >> 1) + 1]); } } } int ans0 = m0.getOrDefault(-g0, 0); int ans1 = m1.getOrDefault(-g1, 0); if (h0[0] == -g0) ans0--; pw.println(ans0 + ans1); } } static <Key> void add1(HashMap<Key, Integer> map, Key key) { map.putIfAbsent(key, 0); map.put(key, map.get(key) + 1); } static <Key> void sub1(HashMap<Key, Integer> map, Key key) { map.put(key, map.get(key) - 1); }
M - 筆塗り
HLD + 遅延セグ木をやるだけ. HLD は木上のパスに対するクエリを高速に処理できるので, 区間更新の遅延セグ木を載せれば OK.
実装例を貼ってもライブラリの中身がよく分からないと思うので省略. HLD や遅延セグ木の記事を見ると解けることが分かると思う.
N - マス目の穴埋め
二時間近くかかった, 大反省. 天才系の問題かと思って色々やったけど, 普通に DP だった...
まず, 入力の周りを 0 で囲っておく.
$$dp[i][S][T]=(i-1) 行目の 0,1 パターンが S で, i 行目の 0,1 パターンが T であるような場合の数$$
と DP テーブルを定義すればよい. 遷移は実装を見た方が早い気がする (希望があれば説明をちゃんと書きます).
static final int H = 18; static final int W = 6; public static void solve(ExtendedScanner sc, FastPrintStream pw) { char[][] _b = sc.charArrays(H); int[][] b = new int[H + 2][W + 2]; for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { b[i + 1][j + 1] = _b[i][j] == '?' ? -1 : _b[i][j] - '0'; } } long[][][] dp = new long[H + 2][1 << W][1 << W]; dp[0][0][0] = 1; for (int i = 1; i <= H + 1; i++) { for (int s = 0; s < 1 << W; s++) { int[] z = toArray(s); for (int t = 0; t < 1 << W; t++) { int[] y = toArray(t); for (int u = 0; u < 1 << W; u++) { int[] x = toArray(u); boolean ok = true; for (int j = 1; j <= W; j++) { ok &= b[i][j] < 0 || b[i][j] == x[j]; } if (!ok) continue; if (valid(z, y, x)) { dp[i][t][u] += dp[i - 1][s][t]; } } } } } long ans = 0; for (int s = 0; s < 1 << W; s++) { ans += dp[H + 1][s][0]; } pw.println(ans); } static int[] toArray(int s) { int[] x = new int[W + 2]; for (int i = 0; i < W; i++) { x[i + 1] = (s >> i) & 1; } return x; } static boolean valid(int[] z, int[] y, int[] x) { int[][] xyz = new int[][]{z, y, x}; for (int i = 1; i <= W; i++) { int[] c = new int[2]; for (int d = 0; d < 4; d++) { int ni = i + Const.dx4[d]; int nj = 1 + Const.dy4[d]; c[xyz[nj][ni]]++; } if (++c[y[i]] < 3) { return false; } } return true; }
O - 宝箱
ボス問かと思いきや後半 4 問の中では一番簡単だった.
初めに $A_i$ は全てもらっておき, もらえなかった $A_i$ を損失として考えることにすると, 以下のようなグラフを構築して頂点 $0$ から頂点 $N$ までの最短経路問題を解けば OK.
public static void solve(ExtendedScanner sc, FastPrintStream pw) { int n = sc.nextInt(); int m = sc.nextInt(); long s = 0; long[] a = sc.longs(n); s = Arrays.stream(a).sum(); Digraph<SimpleEdge> g = new Digraph<>(n + 1); for (int i = 0; i < m; i++) { int u = sc.nextInt(); int v = sc.nextInt(); long c = sc.nextLong(); g.addEdge(new SimpleEdge(u - 1, v, c)); } for (int i = 0; i < n; i++) { g.addEdge(new SimpleEdge(i, i + 1, a[i])); g.addEdge(new SimpleEdge(i + 1, i, 0)); } long cost = new Dijkstra<>(g, 0).distance(n); pw.println(s - cost); }
