NECプログラミングコンテスト2021(AtCoder Beginner Contest 229)

コンテスト前のレート：1982
レート通りのパフォーマンスが得られる順位：338位（2000点、63分28秒）

A - First Grid

問題

思考過程

1. 一瞬BFSなどすることが頭をよぎるが、例２を見て、分断されるのは白と黒が個ずつで斜めになっている場合のみだと気付く。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        char[][] s = new char[2][2];
        s[0] = sc.next().toCharArray();
        s[1] = sc.next().toCharArray();
        sc.close();

        if (s[0][0] == '.' && s[1][1] == '.' ||
                s[0][1] == '.' && s[1][0] == '.') {
            System.out.println("No");
        } else {
            System.out.println("Yes");
        }
    }
}

ここまで1分28秒＋0ペナ。46位。

B - Hard Calculation

問題

思考過程

1. 各桁ごとに和を求め、どこか桁でも以上ならば"Hard"。
2. の桁数が異なる場合を考慮すると、文字列で受け取って反転させれば位を揃えることができ、の位から調べていける。

import java.util.Scanner;

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

        int min = Math.min(a.length, b.length);
        reverse(a);
        reverse(b);
        for (int i = 0; i < min; i++) {
            int aa = a[i] - '0';
            int bb = b[i] - '0';
            if (aa + bb >= 10) {
                System.out.println("Hard");
                return;
            }
        }
        System.out.println("Easy");
    }

    // 以下ライブラリ（配列を逆順にする）

    static void reverse(char[] a) {
        for (int i = 0; i < a.length / 2; i++) {
            char tmp = a[i];
            a[i] = a[a.length - 1 - i];
            a[a.length - 1 - i] = tmp;
        }
    }
}

ここまで3分33秒＋0ペナ。104位。

C - Cheese

問題

思考過程

1. 一瞬ナップサック問題に見えたりしたが全くそんなことはなく、の大きい順にソートして貪欲に使えるだけ使うだけだった。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

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 w = Integer.parseInt(sa[1]);
        PriorityQueue<Obj> que = new PriorityQueue<>((o1, o2) -> o2.a - o1.a);
        for (int i = 0; i < n; i++) {
            sa = br.readLine().split(" ");
            Obj o = new Obj();
            o.a = Integer.parseInt(sa[0]);
            o.b = Integer.parseInt(sa[1]);
            que.add(o);
        }
        br.close();

        long ans = 0;
        while (!que.isEmpty()) {
            Obj o = que.poll();
            long c = Math.min(o.b, w);
            ans += o.a * c;
            w -= c;
        }
        System.out.println(ans);
    }

    static class Obj {
        int a, b;
    }
}

ここまで6分58秒＋0ペナ。132位。

D - Longest X

問題

思考過程

1. "X"を連続させる区間の左端を全探索してみるとすると、対応する右端をとかで求めたい。
2. これは、"."の数の累積和を前計算しておけば、二分探索で求められる。

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));
        char[] s = br.readLine().toCharArray();
        int k = Integer.parseInt(br.readLine());
        br.close();

        // 累積和
        int n = s.length;
        int[] a = new int[n + 1];
        for (int i = 0; i < n; i++) {
            a[i + 1] = a[i];
            if (s[i] == '.') {
                a[i + 1]++;
            }
        }

        int ans = 0;
        // 左端を全探索
        for (int i = 0; i < n; i++) {
            // 対応する右端を二分探索
            int ok = i;
            int ng = n + 1;
            while (Math.abs(ok - ng) > 1) {
                int mid = (ok + ng) / 2;
                if (a[mid] - a[i] <= k) {
                    ok = mid;
                } else {
                    ng = mid;
                }
            }
            ans = Math.max(ans, ok - i);
        }
        System.out.println(ans);
    }
}

ここまで13分21秒＋0ペナ。162位。

E - Graph Destruction

問題

思考過程

1. 連結成分を管理するならUnionFind。
2. UnionFindは辺を追加していくことしかできないので、逆からやることを考える。
3. 連結成分数を求める際は、頂点で作成しているUnionFindの連結成分数から、存在していないことになっている頂点数を引けばよい。
4. 頂点と繋がる辺を追加する際は、番号がより大きい頂点と繋がっている辺のみに絞って追加する必要がある。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
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 m = 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 < m; 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);
        }
        br.close();

        UnionFind uf = new UnionFind(n);
        int[] ans = new int[n];
        for (int i = n - 1; i > 0; i--) {
            List<Integer> list2 = list.get(i);
            for (int e : list2) {
                if (e > i) { // 4
                    uf.union(i, e);
                }
            }
            ans[i - 1] = uf.num - i; // 3
        }

        PrintWriter pw = new PrintWriter(System.out);
        for (int i : ans) {
            pw.println(i);
        }
        pw.flush();
    }

    // 以下ライブラリ

    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];
        }
    }
}

ここまで21分02秒＋0ペナ。170位。

F - Make Bipartite

問題
重みの辺を「中の辺」、重みの辺を「周の辺」と呼ぶ。

思考過程

1. 例１にが奇数の場合の図があるので、が偶数の場合の図も描いてみて構造を考えるが、各についてとの片方を選ぶか両方を選ぶかなどに規則性は見えてこない。
2. 二部グラフということは各頂点をつのグループに分類することになるので、頂点をグループ1固定、頂点をグループ1かグループ2かで場合分けして、あとは頂点～と順にDPで埋めていけないかを考えてみる。
   　
3. 「頂点まで見た時、頂点がグループの場合に残せる辺の重みの最大値」とすると遷移は、
   • へは、グループ2→1の場合の「周の辺」、グループ1→1の場合の「」の大きい方。
   • へは、グループ1→2の場合の「周の辺中の辺」、グループ2→2の場合の「中の辺」の大きい方。
4. しかしこれだと、最後に頂点と頂点間の周の辺を残せるのかどうかがわからない。
   　
5. 「頂点まで見た時、頂点がグループで頂点がグループの場合に残せる辺の重みの最大値」に変更すると、上記4.の判断ができるようになる。　（ここを間違えて1回WA）
6. 異なる間で遷移することはないので、とは最初が異なるだけで遷移は同じ。
   　
7. グループ1ばかりが回以上続くと非連結なグラフができてしまうが、そのケースが発生しないように何か考慮する必要があるか？
8. 仮にグループ1が回続くとすると、番目をグループ2にすることで連続部分以外には影響を与えることなく辺を本追加可能であり、確実に得をするので、DPの遷移条件により発生することはなさそう。

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));
        int n = Integer.parseInt(br.readLine());
        String[] sa = br.readLine().split(" ");
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(sa[i]);
        }
        sa = br.readLine().split(" ");
        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
            b[i] = Integer.parseInt(sa[i]);
        }
        br.close();

        long[] dp11 = new long[n];
        long[] dp12 = new long[n];
        long[] dp21 = new long[n];
        long[] dp22 = new long[n];
        dp12[1] = a[0] + b[0];
        dp21[1] = b[0] + a[1];
        dp22[1] = a[0] + a[1];
        for (int i = 2; i < n; i++) {
            dp11[i] = Math.max(dp21[i - 1] + b[i - 1], dp11[i - 1]);
            dp12[i] = Math.max(dp22[i - 1] + b[i - 1], dp12[i - 1]);
            dp21[i] = Math.max(dp11[i - 1] + b[i - 1] + a[i], dp21[i - 1] + a[i]);
            dp22[i] = Math.max(dp12[i - 1] + b[i - 1] + a[i], dp22[i - 1] + a[i]);
        }

        long rem = 0;
        rem = Math.max(rem, dp11[n - 1]);
        rem = Math.max(rem, dp12[n - 1] + b[n - 1]);
        rem = Math.max(rem, dp21[n - 1] + b[n - 1]);
        rem = Math.max(rem, dp22[n - 1]);

        long sum = 0;
        for (int i = 0; i < n; i++) {
            sum += a[i] + b[i];
        }
        System.out.println(sum - rem);
    }
}

ここまで54分49秒＋1ペナ。194位。

G - Longest Y

問題
思考過程6.までで延々と時間が過ぎていき、終了5分前にやっと解法がわかってきたが、添え字がややこしく実装間に合わず。
一応30秒前に勢いで実装終わらせ、サンプルが通ったので終了直前に提出してみるもRE。
終了後ゆっくりデバッグして16分後にAC。ちなみに実装ミスは1箇所や2箇所ではなく山ほどあった。

以下、"Y"が文字存在するとする。

思考過程

1. 答えの二分探索をして、"Y"が文字続くことにすると、その中で中央（約番目）の"Y"に寄せるのが最善。
2. どの"Y"を中央にするかについて全探索し、前後約個ずつの"Y"を移動させる合計回数を高速に求められれば、とかにできる。
   　
3. あるいは、どの"Y"を中央にするかについて全探索し、各"Y"について合計回以下で前後何個までの"Y"を移動させられるかを高速に求められるのでもよい。
   　
4. だがどちらも「高速に求められれば」の部分がしか思いつかない。
5. 例えば例１で全部の"Y"を繋げるとすると、"Y"同士の間の"."の数がであるため、左から番目の"Y"を中央として見たときの総移動回数は以下のようになる。
   • ：
   • ：
   • ：
   • ：
   • ：
6. 上記5.の数列の各要素の貢献度が、中央として見る位置に近いほど階段状に大きくなっており、簡単な累積和では求められそうにない。
   　
7. 中央とする"Y"の左側と右側に分けて計算する。
8. 左側の移動回数については、以下のような累積和をつ組み合わせることで、台形から長方形を引くような形で求められる。（コード内コメントも参照）
   • の累積和：
   • の通常の累積和：
9. 右側についても同様に、とを用意しておく。

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] s = br.readLine().toCharArray();
        long k = Long.parseLong(br.readLine());
        br.close();

        int n = s.length;
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (s[i] == 'Y') {
                list.add(i);
            }
        }
        int m = list.size(); // "Y"の数
        if (m == 0) {
            System.out.println(0);
            return;
        }

        long[] b = new long[m]; // "Y"間の"."の個数配列
        for (int i = 0; i < m - 1; i++) {
            b[i + 1] = list.get(i + 1) - list.get(i) - 1;
        }
        long[] c1 = new long[m];  // 左側用階段状累積和
        long[] c11 = new long[m]; // 左側用通常累積和
        for (int i = 1; i < m; i++) {
            c1[i] = b[i] * i;;
            c1[i] += c1[i - 1];
            c11[i] = b[i];
            c11[i] += c11[i - 1];
        }
        long[] c2 = new long[m];  // 右側用階段状累積和
        long[] c21 = new long[m]; // 右側用通常累積和
        for (int i = m - 1; i > 0; i--) {
            c2[i - 1] = b[i] * (m - i);;
            c2[i - 1] += c2[i];
            c21[i - 1] = b[i];
            c21[i - 1] += c21[i];
        }

        int ok = 0;
        int ng = m + 1;
        label:
        while (Math.abs(ok - ng) > 1) {
            int mid = (ok + ng) / 2;
            int x1 = mid / 2;
            int x2 = mid - 1 - x1;
            // 中央にする"Y"を全探索
            for (int i = 0; i < m; i++) {
                int l = i - x1;
                int r = i + x2;
                if (0 <= l && r < m) {
                    // 左側（以下の3の部分を求めたい）
                    // 1122244
                    //  122244
                    //   33344
                    //    3344
                    //     344
                    //      44
                    //       4
                    long v1 = c1[i] - c1[l];    // 2の部分＋3の部分
                    long v11 = c11[i] - c11[l]; // 2の部分1行目のみ
                    long v12 = v11 * l;         // 2の部分全体
                    v1 -= v12;                  // 3の部分
                    long v1 = c1[i] - c1[l];
                    long v11 = c11[i] - c11[l];
                    long v12 = v11 * l;
                    v1 -= v12;
                    // 右側
                    long v2 = c2[i] - c2[r];
                    long v21 = c21[i] - c21[r];
                    long v22 = v21 * (m - r - 1);
                    v2 -= v22;
                    if (v1 + v2 <= k) {
                        ok = mid;
                        continue label;
                    }
                }
            }
            ng = mid;
        }
        System.out.println(ok);
    }
}

最終結果：ABCDEFの6完2000点、59分49秒、323位、パフォーマンス2006
レート変動：1982→1984（+2）

Eまで十分早いつもりだったのに、A時点が最高で以降ゆるやかに落ちていっているのが厳しい・・。
約9か月ぶりのRatedABCだったが、とりあえず無難な結果で終われて何より。

Gが時間に間に合わなかったとはいえ一応自力で解けたのでよしとする。
あと何でハマらなければ間に合ったんだろうかとは考えてしまうけど。