AtCoder Regular Contest 112

コンテスト前のレート：1950
レート通りのパフォーマンスが得られる順位：436位（1200点、83分33秒）
黄色になれるパフォーマンスが得られる順位：163位（1800点、95分30秒）

A - B = C

問題

思考過程

1. とりあえずと変形する。
2. これを満たす組を探索したいが、制約が大きく、を全探索するようなことすらできないので、数学をする方向で考える。
   　
3. の最大値は。の最小値は、の場合なので。
4. 例１を観察してもわかるが、の場合は通り、の場合は通り、と増えていく。
5. 結局、として、～の和（）が答え。ただし、の場合は。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < t; i++) {
            String[] sa = br.readLine().split(" ");
            int l = Integer.parseInt(sa[0]);
            int r = Integer.parseInt(sa[1]);

            int a = 2 * l;
            long x = Math.max(r - a + 1, 0);
            long ans = x * (x + 1) / 2;
            pw.println(ans);
        }
        pw.flush();
        br.close();
    }
}

ここまで4分29秒＋0ペナ。192位。

B - -- - B

問題
すんなり解けなくて辛い。

思考過程

1. これも制約が大きく、ダブリング等ができそうな感じもせず、むしろで計算できそうな感じにしか見えないので、の方針で考える。
2. とりあえず実際に書き出してみる。
   　
3. 例えばの場合、以下のようになり、円から先は円増えるごとに個ずつ増える。
   • 円で
   • 円で
   • 円で
   • 円で
   • 円で
4. よって、基本的にはになりそう。あとはコーナーケースをつぶしていく。
   　
5. まず、がと比べて小さい場合、に達した後は個ずつしか増えない。
6. が小さい場合も考えると、何回目の操作が個か個か、はたまた個なのかぱっとわからなかったので、が小さい場合は愚直にシミュレーションしてしまうことにする。
   　
7. 以降はが大きい場合。
   　
8. の場合は、円で個、円で増えない、円以降は個ずつ増える。制約によりはないので、を出力する。
   　
9. が正の場合、の場合はに達しないので、上記4.の通り。
10. の場合は、円までで個。残りの円が個ずつ増えるので、となる。
    　
11. が負の場合、円まで個ずつ増えるのでその分の帳尻を合わせる。（詳細は省略するが、分くらいは試行錯誤してしまっている）
    　
12. 上記9.のところをにしてしまうミスがありWA。提出デバッグを試み、分岐箇所にTLEとRE*1を仕込んだりしたのでもうペナ。

import java.util.ArrayDeque;
import java.util.HashSet;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        long b = sc.nextLong();
        long c = sc.nextLong();
        sc.close();

        if (c < 10) {
            // 6
            Set<Long> set = new HashSet<>();
            Queue<Obj> que = new ArrayDeque<>();
            que.add(new Obj(b, 0));
            set.add(b);
            while (!que.isEmpty()) {
                Obj cur = que.poll();
                if (!set.contains(-cur.b) && cur.c + 1 <= c) {
                    que.add(new Obj(-cur.b, cur.c + 1));
                    set.add(-cur.b);
                }
                if (!set.contains(cur.b - 1) && cur.c + 2 <= c) {
                    que.add(new Obj(cur.b - 1, cur.c + 2));
                    set.add(cur.b - 1);
                }
            }
            System.out.println(set.size());

        } else {
            if (b == 0) {
                System.out.println(c); // 8
            } else if (b > 0) {
                if (b * 2 >= c) {
                    System.out.println(c * 2 - 1); // 9
                } else {
                    System.out.println(b * 2 - 1 + c); // 10
                }
            } else {
                // 11
                b = -b;
                if (b * 2 >= c) {
                    System.out.println(c * 2 - 1);
                } else {
                    System.out.println(b * 2 + c);
                }
            }
        }
    }

    static class Obj {
        long b, c;

        public Obj(long b, long c) {
            this.b = b;
            this.c = c;
        }
    }
}

ここまで43分34秒＋2ペナ。839位。

C - DFS Game

問題
B問題で出遅れたと思ったが、B通した時点での正解者数はまだ60人程度しかおらず、巻き返し可能なのではと思った。
しかし、大筋は割と早くわかったが、木DPの遷移に当たる部分というか、子の結果を貪欲でまとめる部分で大苦戦。

途中で何度もDに行きかけたが諦めきれず、経過時間100分頃の4ペナ目でやっと諦めてDへ。
Dを18分で通し、残り1分半ほどというところで戻ってきて、そんなわずかな時間では何もできないだろうと思ったが、一応見直したら貪欲のソート部分が目に留まったのでそこだけ直し、動作確認もしていられないと思いながら残り19秒で提出してAC。

思考過程

1. 操作の流れを追っていくと、必ずDFSの順序で木をたどっていき、子の頂点に入っていく順序だけ選択の余地があることがわかる。
2. ある頂点について見たとき、各子頂点に入った時に先手と後手がそれぞれ何個ずつのコインを得られるのかがわかっていれば、自頂点についても同様の個数が求められそうで、それを葉から順に求めていく。
   　
3. 親頂点からある頂点の処理に入ってきた時、まずは先手がに置かれているコインを取る。
4. 後手から順に、最適な子頂点を選んでいくことになる。
5. どの子頂点から入っていくのが最適かは、比較的最近で言えばABC187-Dと似たような見た目の問題で、評価値を決めて貪欲をすればよさそうだと当たりを付ける。
   　
6. ある頂点に入ってきて最初に頂点のコインを取る方を「における先手」とすると、に入ることを選ぶのは、必ずにおける後手である。
7. つまり、現在の手番が誰であろうと、後手が得する子頂点から選んでいきたいことになる。
8. 「先手が得られる数後手が得られる数」をとすると、の昇順に選べばいいのではないか。
   　
9. 手番が変わらないならの昇順だけでよいが、子の頂点数の偶奇で手番が入れ替わるため、連続で選べるかどうかも考慮する必要がある。
10. なお、各辺は必ず往復するため、移動は必ず偶数回。コインを拾う回数子の頂点数のため、子の頂点数が奇数の場合に、自頂点まで戻ってきた時に手番が入れ替わっていることになる。
    　
11. 結局、後手得の範囲では手番を変えないことを優先、先手得の範囲では手番を変えることを優先するとよい。
    • WA回目：の昇順ソートしかしていなかった、先後が必ず入れ替わるものとしていた
    • WA回目：の昇順ソートしかしていなかった
    • WA回目：後手得、先手得の範囲で分けずに常に手番を変えること優先にしていた
    • WA回目：先手得の範囲は手番変わるのを優先にしたが、後手得の範囲は手番をソート条件に入れていなかった

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
    static int n;
    static List<List<Integer>> list;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            list.add(new ArrayList<>());
        }
        String[] sa = br.readLine().split(" ");
        for (int i = 0; i < n - 1; i++) {
            int p = Integer.parseInt(sa[i]) - 1;
            list.get(p).add(i + 1);
        }
        br.close();

        Obj res = dfs(0, -1);
        System.out.println(res.f);
    }

    static Obj dfs(int x, int p) {
        Obj ret = new Obj();
        ret.f++;
        List<Obj> wk = new ArrayList<>();
        for (int c : list.get(x)) {
            wk.add(dfs(c, x));
        }

        List<Obj> wk1 = new ArrayList<>(); // 後手の方が多く得られる子頂点
        List<Obj> wk2 = new ArrayList<>(); // 先手の方が多く得られる子頂点
        for (Obj o : wk) {
            if (o.d < 0) {
                wk1.add(o);
            } else {
                wk2.add(o);
            }
        }
        // 後手が多い場合、偶数優先、偶奇同じなら後手がより多く得られる方が優先
        Collections.sort(wk1, (o1, o2) -> {
            if (o1.w != o2.w) {
                return o1.w - o2.w;
            }
            return o1.d - o2.d;
        });
        // 先手が多い場合、奇数優先、偶奇同じなら後手がより多く得られる方が優先
        Collections.sort(wk2, (o1, o2) -> {
            if (o1.w != o2.w) {
                return o2.w - o1.w;
            }
            return o1.d - o2.d;
        });

        boolean flg = true; // 手番判定用
        wk1.addAll(wk2);
        for (int i = 0; i < wk1.size(); i++) {
            Obj o = wk1.get(i);
            if (flg) {
                ret.f += o.f;
                ret.s += o.s;
            } else {
                ret.f += o.s;
                ret.s += o.f;
            }
            // 子部分木の頂点数が奇数の場合は先後入れ替え
            if (o.w == 1) {
                flg = !flg;
            }
        }
        ret.d = ret.f - ret.s;
        ret.w = (ret.f + ret.s) % 2;
        return ret;
    }

    static class Obj {
        // f：先手の個数　s：後手の個数　d：f-s(ソート用)　w：頂点数の偶奇
        int f, s, d, w;
    }
}

ABDCと解いた時点で119分41秒＋6ペナ。282位。

D - Skate

問題
半分エスパーで通した。

思考過程

1. 「どのマスから見ても」については、周囲（もっと言えば隅）のマスは内部のマスの下位互換でしかないので、隅からたどり着けるかどうかだけ調べればよさそう。
   　
2. 例２でからスタートした場合を考えてみると、初期状態ではを経由することでしか内部のマスには入れない。
3. '#'のマスに止まれば、そこから十字にはどこへでも行け、十字の範囲内に別の'#'があればさらにそこから十字に進める。この時点でUnionFindっぽさを感じる。あるいはABC131-Fのような二部グラフとか。
   　
4. 例２の答えがとあるが、具体的にどんなマスで達成できるのかを考える。
5. とか、とか。（下図）
6. 後者では、につなげることで列目には新たに'#'を置かなくてもよくなっている。
   　
7. 元々同一行に'#'が存在する列同士を連結成分とすると、連結成分同士を行き来可能にするのに個かかり、'#'が存在しない列（UnionFind上は頂点数の連結成分）に行けるようにするのにも個かかるので、連結成分の数が答えになりそう。
8. これを縦と横で同様のことを行い、より小さい方が最終的な答え。

..........　　..........
#...#.....　　#...#.....
....#.....　　..........
....#.....　　..........
....#.....　　..........
....#.....　　.#######..
.#..#...#.　　.#......#.
....#.....　　..........
....#.....　　..........
..........　　..........

import java.io.BufferedReader;
import java.io.InputStreamReader;

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 h = Integer.parseInt(sa[0]);
        int w = Integer.parseInt(sa[1]);
        char[][] s = new char[h][w];
        for (int i = 0; i < h; i++) {
            s[i] = br.readLine().toCharArray();
        }
        br.close();

        UnionFind uf1 = new UnionFind(h);
        UnionFind uf2 = new UnionFind(w);
        uf1.union(0, h - 1); // 先頭行と最終行を連結
        uf2.union(0, w - 1); // 先頭列と最終列を連結
        for (int i = 0; i < h; i++) {
            // 同一行内最初の#の列index
            int x = -1;
            // 最初と最後の行は、1列目と連結可能
            if (i == 0 || i == h - 1) {
                x = 0;
            }
            for (int j = 0; j < w; j++) {
                if (s[i][j] == '#') {
                    if (x == -1) {
                        x = j;
                    } else {
                        uf2.union(x, j);
                    }
                }
            }
        }
        // 行と列入れ替えて同様
        for (int j = 0; j < w; j++) {
            int x = -1;
            if (j == 0 || j == w - 1) {
                x = 0;
            }
            for (int i = 0; i < h; i++) {
                if (s[i][j] == '#') {
                    if (x == -1) {
                        x = i;
                    } else {
                        uf1.union(x, i);
                    }
                }
            }
        }
        System.out.println(Math.min(uf1.num - 1, uf2.num - 1));
    }

    // 以下ライブラリ

    static class UnionFind {
        int[] parent, size;
        int num = 0; // 連結成分の数

        UnionFind(int n) {
            parent = new int[n];
            size = new int[n];
            num = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }

        void union(int x, int y) {
            int px = find(x);
            int py = find(y);
            if (px != py) {
                parent[px] = py;
                size[py] += size[px];
                num--;
            }
        }

        int find(int x) {
            if (parent[x] == x) {
                return x;
            }
            parent[x] = find(parent[x]);
            return parent[x];
        }
    }
}

ABDと解いた時点で117分46秒＋2ペナ。380位。

最終結果：ABCDの4完、149分41秒、289位、パフォーマンス2136
レート変動：1950→1970（+20）

C問題が全然通らず、完全に爆死したと思っていたところからラスト3分の大逆転。
Dが通った時点で十分に救われて満足しかけたのだが、ダメ元で簡単にでも見直すだけ見直してよかった。
（なお、2完ならパフォ1420ほど）

まだもうしばらくの間は、黄色になれるかもという夢を捨てずに済みそう。
今回はパフォ2371で黄色だったが、次回は2238で足りるようになった。

*1:分岐が多いときはもう1箇所MLEも仕込みたいが、Javaだと大きなMLEはRE（OutOfMemoryError）になってしまうようで、紛らわしいのでやめた