AtCoder Beginner Contest 209(Rated範囲外)

A - Counting
- 思考過程
B - Can you buy them all?
- 思考過程
C - Not Equal
- 思考過程
D - Collision
- 思考過程

コンテスト前のレート：
（Ratedだとしたら）レート通りのパフォーマンスが得られる順位：244位（1500点、90分36秒）

A - Counting

問題
サンプルも試さず適当に提出したらWA。まさかこれでパフォ200も下がることになろうとは・・・。
ちなみに初回提出は18秒だったので、通ってもFAと比べて3秒遅い。

思考過程

$B-A+1$ を求める。　→WA
よく見たら $A \leq B$ という制約はなかったので、 $0$ 未満は $0$ にする必要があった。

import java.util.Scanner;

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

        System.out.println(Math.max(b - a + 1, 0));
    }
}

ここまで1分11秒＋1ペナ。1076位。

B - Can you buy them all?

問題
問題文を読んだ後Aの提出結果を確認したらWAだったので、一旦Aに戻ってから実装。

思考過程

入力をそのまま合計に足していき、偶数番目（ループカウンタを $2$ で割って余りが奇数）の場合 $1$ を引く。
合計と $X$ を比較して答えを出力する。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int x = sc.nextInt();
        int s = 0;
        for (int i = 0; i < n; i++) {
            s += sc.nextInt();
            if (i % 2 == 1) {
                s--;
            }
        }
        sc.close();

        if (s <= x) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

ここまで1分53秒＋1ペナ。59位。

C - Not Equal

問題

思考過程

$C_1 \times (C_2-1) \times (C_3-2) \times \cdots$ 　になりそうな気がしたが、 $C_i \gt C_{i+1}$ になっている箇所がある場合、数列の前の方に大きい数を割り当てると、それまでの要素数分後ろの方の選択肢が減るとは限らない。
では最初に昇順ソートしてしまえばどうか？
上記1.最初の通りでよさそう。
A問題と同じ失敗をしないよう、今度はちゃんと $0$ とのmaxを取っておく。

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] c = new int[n];
        for (int i = 0; i < n; i++) {
            c[i] = sc.nextInt();
        }
        sc.close();

        int mod = 1000000007;
        Arrays.sort(c);
        long ans = 1;
        for (int i = 0; i < n; i++) {
            ans *= Math.max(c[i] - i, 0);
            ans %= mod;
        }
        System.out.println(ans);
    }
}

ここまで5分33秒＋1ペナ。193位。

D - Collision

問題
想定解は全然出てこなかった。

思考過程

$c$ と $d$ の距離が偶数の場合は"Town"、奇数の場合は"Road"となる。
毎回DFS/BFSするような $O(QN)$ は当然駄目な制約。
$2$ 点間の距離は、 $c$ と $d$ の最小共通祖先 $lca(c, d)$ がわかれば、点 $a$ の根からの深さを $dep(a)$ と表すと、 $dep(c) - dep(lca(c, d)) + dep(d) - dep(lca(c, d))$ 　となる。

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

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 q = Integer.parseInt(sa[1]);
        List<List<Integer>> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            list.add(new ArrayList<>());
        }
        for (int i = 0; i < n - 1; i++) {
            sa = br.readLine().split(" ");
            int a = Integer.parseInt(sa[0]) - 1;
            int b = Integer.parseInt(sa[1]) - 1;
            list.get(a).add(b);
            list.get(b).add(a);
        }

        DoublingLCA st = new DoublingLCA(list, 0);

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < q; i++) {
            sa = br.readLine().split(" ");
            int c = Integer.parseInt(sa[0]) - 1;
            int d = Integer.parseInt(sa[1]) - 1;
            DoublingLCA.Node lca = st.lca(c, d);
            int dist = st.nodes[c].dep + st.nodes[d].dep - lca.dep * 2;
            if (dist % 2 == 0) {
                pw.println("Town");
            } else {
                pw.println("Road");
            }
        }
        br.close();
        pw.flush();
    }

    // 以下ライブラリ

    /**
     * ダブリングで最小共通祖先（Lowest Common Ancestor）
     */
    static class DoublingLCA {
        int n, h = 1, root;
        List<List<Integer>> list;
        Node[] nodes;
        int[][] parent;

        /**
         * 初期化
         * @param list 隣接リスト
         * @param root 根の頂点番号
         */
        public DoublingLCA(List<List<Integer>> list, int root) {
            n = list.size();
            this.root = root;
            this.list = list;

            while ((1 << h) < n) {
                h++;
            }
            nodes = new Node[n];
            for (int i = 0; i < n; i++) {
                nodes[i] = new Node(i, -1);
            }
            parent = new int[h][n];
            for (int i = 0; i < h; i++) {
                Arrays.fill(parent[i], -1);
            }

            dfs(root, -1, 0);
            for (int i = 0; i < h - 1; i++) {
                for (int j = 0; j < n; j++) {
                    if (parent[i][j] != -1) {
                        parent[i + 1][j] = parent[i][parent[i][j]];
                    }
                }
            }
        }

        private void dfs(int x, int p, int dep) {
            parent[0][x] = p;
            nodes[x].dep = dep;
            for (int next : list.get(x)) {
                if (next != p) {
                    dfs(next, x, dep + 1);
                }
            }
        }

        /**
         * 頂点A,BのLCA取得（0≦A,B＜N）
         */
        public Node lca(int a, int b) {
            int u = a;
            int v = b;
            if (nodes[u].dep < nodes[v].dep) {
                u = b;
                v = a;
            }
            for (int i = 0; i < h; i++) {
                if ((nodes[u].dep - nodes[v].dep >> i & 1) == 1) {
                    u = parent[i][u];
                }
            }
            if (u == v) {
                return nodes[u];
            }
            for (int i = h - 1; i >= 0; i--) {
                if (parent[i][u] != parent[i][v]) {
                    u = parent[i][u];
                    v = parent[i][v];
                }
            }
            return nodes[parent[0][u]];
        }

        public static class Node {
            int i, dep;

            public Node(int i, int dep) {
                this.i = i;
                this.dep = dep;
            }
        }
    }
}

ここまで14分06秒＋1ペナ。376位。

EとFは解けず。残り時間のほとんどはE問題に使った。

Eは、"xxx"で終わる単語から"xxx"で始まる単語に辺を張る形でやろうとして上手くいかず。
後ろからやろうとすると、調べる頂点の順番をどうすればよいかよくわからず、前からやろうとすると、結果が確定しているかどうかがよくわからない感じになっていたと思う。

最終結果：ABCDの4完1000点、19分06秒、796位、パフォーマンス1601相当
レート変動：2129（Unrated）

最近のABCは3連続で400位台だったが、再びの800位前後。
まあ今回はA問題をちゃんとやれば500位前後ではあったが。

それよりもやっぱりEかFどちらかがちゃんと解けないと。
Unratedだから何が何でも解こうという意識がないのはあるけど、それにしても5完より4完の方が多いのはいい加減ひどいし。
とはいえ、直近5回は青diffまでは解けているから、さらに5回前の水diffまで落としていた頃より少しはマシになってきてはいるか。