ACL Contest 1 - ks2mのブログ

A - Reachable Towns
- 思考過程
C - Moving Pieces
- 思考過程

コンテスト前のレート：1775
レート通りのパフォーマンスが得られる順位：364位

ソース中の省略部分はACLをJavaに移植の記事参照。

A - Reachable Towns

思考過程

例２の $1, 2, 6$ 番目の点 $\{(6, 4), (4, 3), (5, 2)\}$ を見て、Union-Findを使い、該当の点を含む連結成分のサイズを答えればよいものだとわかる。
とりあえずx座標の小さい順に見ていくとすると、ある点 $i$ について処理するときは、点 $1$ ～ $(i-1)$ の内、点 $i$ よりy座標が小さいものとのみ結合させていきたいが、これをそのままやると $O(N^2)$ 。
点 $1$ ～ $(i-1)$ が右肩下がりになっている場合は、全部と結合する必要があるが、右肩上がりの場合は $1$ つと結合すれば十分。これを無駄なくやるにはどうすればいいのかを延々と考える。
　
既に連結成分になっている点の内、y座標が最も小さいものだけ代表として覚えておきたい。
TreeMap＜y座標の値、対象の点＞を作り、点 $i$ について連結対象が見つからなかったときだけエントリを追加していくようにする。
本当は結合する度に最小以外は削除していくべきだと思うが、それを忘れていても通った。（連結対象が見つからなかったときだけ追加を忘れたらさすがにTLE）

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] sa = br.readLine().split(" ");
        int n = Integer.parseInt(sa[0]);
        Obj[] arr = new Obj[n];
        Obj[] arr2 = new Obj[n];
        for (int i = 0; i < n; i++) {
            sa = br.readLine().split(" ");
            Obj o = new Obj();
            o.i = i;
            o.x = Integer.parseInt(sa[0]);
            o.y = Integer.parseInt(sa[1]);
            arr[i] = o;
            arr2[i] = o;
        }
        br.close();

        Arrays.sort(arr, (o1, o2) -> o1.x - o2.x); // x座標昇順
        DSU uf = new DSU(n);
        TreeMap<Integer, Obj> map = new TreeMap<>();
        for (Obj o : arr) {
            Integer now = o.y;
            boolean flg = false; // 1回以上結合したか
            while (true) {
                Integer key = map.lowerKey(now);
                if (key == null) {
                    if (!flg) {
                        map.put(o.y, o);
                    }
                    break;
                }
                map.remove(now); // 後日追加してみて、956→883msであまり変わらず
                Obj v = map.get(key);
                uf.merge(o.i, v.i);
                now = key;
                flg = true; // ここを忘れて1回TLE
            }
        }

        PrintWriter pw = new PrintWriter(System.out);
        for (Obj o : arr2) {
            pw.println(uf.size(o.i));
        }
        pw.flush();
    }
}

class Obj {
    int i, x, y;
}

/**
 * Disjoint Set Union（Union Find）
 */
class DSU {
    // 省略
}

ここまで30分15秒＋1ペナ。161位。

B問題はあまり書けるようなこともないので省略。

C - Moving Pieces

問題
後から思えば、多分Practice-Eよりよっぽど簡単だったんじゃないかと。

思考過程

操作回数を負のコストとして上手いこと辺を張り、MinCostFlowをすればいいのではと考える。
以下の辺を張ればいいのではと考える。（容量は全て）（BIGは適当な大きな値）
- スタート→'o'マス：コスト $=0$
- 'o'マス→到達可能マス：コスト $=$ BIG $-$ 移動回数
- 'o'マスからの到達可能マスの和集合→ゴール：コスト $=0$
  　
実際それで合っているのだが、本番中は以下の誤りを解消できず、解けなかった。
- 「'o'マス」と「到達可能マス」を同じマスにしてしまっていた。
  例１では例えば以下のようにマス番号を付けるべきところ、「'o'マス」を0と6にしていた。
  - 到達可能マス：0～8（8は'#'のため除く）
  - スタート：9
  - ゴール：10
  - 'o'マス：11～12
- 到達可能マスに'o'自身（移動回数 $0$ ）が抜けていた。
そもそも辺の張り方が誤っている時点でどうしようもないのだが、最後の「BIG * cnt - result[1]」のcntがなかなか合わずに苦戦していたので、「% BIG」でどうにかしようとしていたりもした。（当然WA）

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] sa = br.readLine().split(" ");
        int n = Integer.parseInt(sa[0]);
        int m = Integer.parseInt(sa[1]);
        char[][] s = new char[n][m];
        for (int i = 0; i < n; i++) {
            s[i] = br.readLine().toCharArray();
        }
        br.close();

        long BIG = 100000000000L;
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (s[i][j] == 'o') {
                    cnt++;
                }
            }
        }
        MinCostFlow mf = new MinCostFlow(n * m + 2 + cnt);
        int x = n * m;
        int y = x + 1;

        cnt = 0;
        Set<Integer> ends = new HashSet<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (s[i][j] == 'o') {
                    cnt++;
                    mf.addEdge(x, y + cnt, 1, 0); // スタート→'o'マス
                    int start = i * m + j;
                    ends.add(start);
                    mf.addEdge(y + cnt, start, 1, BIG); // 'o'マス→到達可能マス
                    Queue<Integer> que = new ArrayDeque<>();
                    que.add(start);
                    int[][] d = new int[n][m];
                    d[i][j] = 1;
                    while (!que.isEmpty()) {
                        int cur = que.poll();
                        int cx = cur / m;
                        int cy = cur % m;
                        if (cx < n - 1) {
                            int nx = cx + 1;
                            int ny = cy;
                            if (d[nx][ny] == 0 && s[nx][ny] != '#') {
                                d[nx][ny] = d[cx][cy] + 1;
                                int next = nx * m + ny;
                                que.add(next);
                                ends.add(next);
                                // 'o'マス→到達可能マス
                                mf.addEdge(y + cnt, next, 1, BIG - d[cx][cy]);
                            }
                        }
                        if (cy < m - 1) {
                            int nx = cx;
                            int ny = cy + 1;
                            if (d[nx][ny] == 0 && s[nx][ny] != '#') {
                                d[nx][ny] = d[cx][cy] + 1;
                                int next = nx * m + ny;
                                que.add(next);
                                ends.add(next);
                                // 'o'マス→到達可能マス
                                mf.addEdge(y + cnt, next, 1, BIG - d[cx][cy]);
                            }
                        }
                    }
                }
            }
        }
        // 到達可能マス→ゴール
        for (Integer end : ends) {
            mf.addEdge(end, y, 1, 0);
        }

        long[] result = mf.flow(x, y);
        System.out.println(BIG * cnt - result[1]);
    }
}

/**
 * 最小費用流
 */
class MinCostFlow {
    // 省略
}

解説等を見てわかったが、以下のような辺の張り方でもよかった。
- スタート→'o'マス：容量 $=1$ 、コスト $=0$
- 各マス→1つ下のマス：容量 $=\infty$ 、コスト $=0$
- 各マス→1つ右のマス：容量 $=\infty$ 、コスト $=0$
- 各マス→ゴール：容量 $=1$ 、コスト $=$ BIG $-(i+j)$
ついでに、'o'マスの数はresult[0]（流量）と同じだった。

提出

最終結果：Aの1完、35分15秒、491位、パフォーマンス1546
レート変動：1775→1754 (-21)

最小費用流の問題にまともに触れたのが、ACL Practice-Eと今回のC問題の2問だけなので、まだこれから慣れていくしかないのかなというところ。
B問題がCRTにたどり着けなかった辺り、数学も弱いなという感じ。