第四回 アルゴリズム実技検定 (バーチャル参加) [G-K]

AtCoder による 第四回 アルゴリズム実技検定 の問題を解きました.

G - 村整備

問題文

が小さいので, 全ての '#' に対して愚直にシミュレーションしても十分間に合う. BFS をしてもよかったが, UnionFind の方が個人的には楽.

    public static void solve(ExtendedScanner sc, FastPrintStream pw) {
        int n = sc.nextInt();
        int m = sc.nextInt();
        char[][] s = sc.charArrays(n);
        int sx = -1, sy = -1;
        int cnt = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (s[i][j] == '.') {
                    cnt++;
                    sx = i;
                    sy = j;
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
            if (s[i][j] == '.') continue;
            boolean[][] g = GridUtil.build(s, '.');
            g[i][j] = true;
            DisjointSetUnion uf = new DisjointSetUnion(n * m);
            for (int r = 0; r < n; r++) for (int c = 0; c < m; c++) {
                if (!g[r][c]) continue;
                if (r < n - 1) {
                    if (g[r + 1][c]) {
                        uf.merge(r * m + c, (r + 1) * m + c);
                    }
                }
                if (c < m - 1) {
                    if (g[r][c + 1]) {
                        uf.merge(r * m + c, r * m + c + 1);
                    }
                }
            }
            if (cnt == uf.size(sx * m + sy)) {
                ans++;
            }
        }
        pw.println(ans);
    }

H - マス目のカット

問題文

正方形領域を固定すると, 一番多い数以外を変えるのが明らかに最適. 制約が小さいので, (プログラム中では t ) と正方形の角の座標を全て愚直に試しても間に合う.

    public static void solve(ExtendedScanner sc, FastPrintStream pw) {
        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();
        int[][] s = new int[n][m];
        for (int i = 0; i < n; i++) {
            char[] row = sc.nextChars();
            for (int j = 0; j < m; j++) {
                s[i][j] = row[j] - '0';
            }
        }
        int ans = 1;
        for (int t = 1; t <= Math.min(n, m); t++) {
            for (int i = 0; i + t <= n; i++) for (int j = 0; j + t <= m; j++) {
                int[] cnt = new int[10];
                for (int r = i; r < i + t; r++) for (int c = j; c < j + t; c++) {
                    cnt[s[r][c]]++;
                }
                int max = IntArrays.max(cnt);
                int change = t * t - max;
                if (change <= k) {
                    ans = t;
                }
            }
        }
        pw.println(ans);
    }

I - ピザ

問題文

ここからは計算量削減を考えて解く必要がある.

とする. 各 に対して, を満たす最大の と, が求まればいい. 従って, 累積和+二分探索を用いると合計 で解くことが出来る.

を二つ繋げた配列 を用意して, に対して累積和を取ったり二分探索を行うと楽に実装できる.

    public static void solve(ExtendedScanner sc, FastPrintStream pw) {
        int n = sc.nextInt();
        long[] a = sc.longs(n);
        long sum = 0;
        for (long v : a) {
            sum += v;
        }
        long[] b = new long[2 * n];
        System.arraycopy(a, 0, b, 0, n);
        System.arraycopy(a, 0, b, n, n);
        long[] bsum = CumulativeSum.build(b);
        long ans = Const.LINF;
        for (int i = 0; i < n; i++) {
            int l = i - 1;
            int r = i + n;
            while (r - l > 1) {
                int m = (l + r) >> 1;
                long s = bsum[m + 1] - bsum[i];
                if (s << 1 <= sum) {
                    l = m;
                } else {
                    r = m;
                }
            }
            long x1 = bsum[l + 1] - bsum[i];
            long y1 = sum - x1;
            long x2 = bsum[r + 1] - bsum[i];
            long y2 = sum - x2;
            ans = Longs.min(ans, Math.abs(x1 - y1), Math.abs(x2 - y2));
        }
        pw.println(ans);
    }

J - ワープ

問題文

突然難しくなる.

実は AtCoder で上位互換 ARC061 C - すぬけ君の地下鉄旅行 が出題されており, 同じ考え方で解ける.

頂点 を追加する. さらに, タイプ A の頂点からは頂点 にコスト の有向辺, 頂点 にコスト の有向辺, 頂点 にコスト の有向辺, 頂点 にコスト の有向辺を追加する. タイプ B, C についても同様に有向辺を追加する. 追加される辺の数は 本である.

頂点および辺を追加したグラフ上で Dijkstra をすれば, 全体 でこの問題は解ける.

    public static void solve(ExtendedScanner sc, FastPrintStream pw) {
        int n = sc.nextInt();
        int m = sc.nextInt();
        long xab = sc.nextLong();
        long xca = sc.nextLong();
        long xbc = sc.nextLong();
        char[] s = sc.nextChars();
        // Digraph は有向グラフを表すクラス. SimpleEdge は始点, 終点, コストを持つ辺 のクラス
        Digraph<SimpleEdge> g = new Digraph<>(n + 6);
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt() - 1;
            int v = sc.nextInt() - 1;
            long c = sc.nextLong();
            g.addEdge(new SimpleEdge(u, v, c));
            g.addEdge(new SimpleEdge(v, u, c));
        }
        int vab = n + 0, vbc = n + 1, vca = n + 2;
        int vba = n + 3, vcb = n + 4, vac = n + 5;
        for (int i = 0; i < n; i++) {
            if (s[i] == 'A') {
                g.addEdge(new SimpleEdge(i, vab, xab));
                g.addEdge(new SimpleEdge(vba, i, 0));

                g.addEdge(new SimpleEdge(vca, i, 0));
                g.addEdge(new SimpleEdge(i, vac, xca));
            } else if (s[i] == 'B') {
                g.addEdge(new SimpleEdge(i, vbc, xbc));
                g.addEdge(new SimpleEdge(vcb, i, 0));

                g.addEdge(new SimpleEdge(vab, i, 0));
                g.addEdge(new SimpleEdge(i, vba, xab));
            } else if (s[i] == 'C') {
                g.addEdge(new SimpleEdge(i, vcb, xbc));
                g.addEdge(new SimpleEdge(vbc, i, 0));

                g.addEdge(new SimpleEdge(vac, i, 0));
                g.addEdge(new SimpleEdge(i, vca, xca));
            }
        }
        var dij = new Dijkstra<>(g, 0);
        pw.println(dij.distance(n - 1));
    }

K - 転倒数

[問題文] (https://atcoder.jp/contests/past202010-open/tasks/past202010_k)

列 の転倒数を と表すことにする. 列 に対して列 を追加してできる列 の転倒数 がどうなるかを考えると,

$$ I(Z)=I(X)+I(Y)+\# \{ (i, j)\mid X_i\gt Y_j \} $$

が成り立つことが分かる. $I(X)$ は一つ前のクエリの答えであり, $I(Y)$ は前計算できる. 従って, $ \# \{ (i, j)\mid X_i\gt Y_j \} $ をどう高速に求めるかが問題となるが, ここで $1\leq X_i \leq 20$, $1\leq Y_j \leq 20$ の制約が活きる.

$$ \# \{ (i, j)\mid X_i\gt Y_j \}=\sum _ {u=1}^{20} \# \{ i\mid X_i=u \} \cdot \sum _ {v=1}^{u-1} \# \{ j\mid Y_j=u \}$$

と変形できるので, $C_u = \# \{ i\mid X_i=u \}$ を満たす配列 $C$ を持っておけばよい.

    public static void solve(ExtendedScanner sc, FastPrintStream pw) {
        int k = sc.nextInt();
        long[] inum = new long[k];
        int[][] a = new int[k][];
        int[][] cnta = new int[k][20];
        for (int i = 0; i < k; i++) {
            int n = sc.nextInt();
            a[i] = sc.ints(n, e -> e - 1);
            for (int v : a[i]) {
                cnta[i][v]++;
            }
            // 数列 A の転倒数は O(|A|log|A|) で求められる.
            inum[i] = InversionNumber.solveCompressed(a[i]);
        }
        int q = sc.nextInt();
        long[] cnt = new long[20];
        long ans = 0;
        while (q --> 0) {
            int i = sc.nextInt() - 1;
            ans += inum[i];
            for (int v = 0; v < 20; v++) {
                long s = cnta[i][v];
                long t = 0;
                for (int w = v + 1; w < 20; w++) {
                    t += cnt[w];
                }
                ans += s * (t % MOD) % MOD;
            }
            ans %= MOD;
            for (int v = 0; v < 20; v++) {
                cnt[v] += cnta[i][v];
            }
        }
        pw.println(ans);
    }