AtCoder Beginner Contest 214(Rated範囲外)

ABC

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

A - New Generation ABC

問題

思考過程
  1. 問題文の通り場合分けする。
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();
        sc.close();

        if (n < 126) {
            System.out.println(4);
        } else if (n < 212) {
            System.out.println(6);
        } else {
            System.out.println(8);
        }
    }
}

ここまで0分52秒＋0ペナ。164位。


B - How many?

問題

思考過程
  1. O(S^3)が間に合う制約なので、全探索する。
import java.util.Scanner;

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

        int ans = 0;
        for (int a = 0; a <= s; a++) {
            for (int b = 0; b <= s - a; b++) {
                for (int c = 0; c <= s - a - b; c++) {
                    if (a * b * c <= t) {
                        ans++;
                    }
                }
            }
        }
        System.out.println(ans);
    }
}

ここまで2分29秒＋0ペナ。170位。


C - Distribution

問題

思考過程
  1. 基本的には、高橋君から渡される時刻T_iと、前のすぬけ君から渡される時刻Ans_{i-1} + S_{i-1}の小さい方がAns_iとなる。
  2. これを1番目だけT_1で決め打ちしてやっていくとWA。
    　
  3. T_iが最小であるすぬけ君を起点にしないと、そもそもAns_{i-1}が求められておらず、破綻する。
  4. 実際に起点を探さなくても、2周回せば1周目途中のどこからか正しくなり、そこから1周以上回るので問題ない。
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 n = Integer.parseInt(br.readLine());
        String[] sa = br.readLine().split(" ");
        int[] s = new int[n];
        for (int i = 0; i < n; i++) {
            s[i] = Integer.parseInt(sa[i]);
        }
        sa = br.readLine().split(" ");
        int[] t = new int[n];
        for (int i = 0; i < n; i++) {
            t[i] = Integer.parseInt(sa[i]);
        }
        br.close();

        long[] ans = new long[n];
        ans[0] = t[0];
        for (int i = 1; i < n * 2; i++) {
            int i1 = (i - 1) % n;
            int i2 = i % n;
            ans[i2] = Math.min(ans[i1] + s[i1], t[i2]);
        }

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < n; i++) {
            pw.println(ans[i]);
        }
        pw.flush();
    }
}

ここまで9分01秒＋1ペナ。261位。


D - Sum of Maximum Weights

問題

思考過程
  1. ある辺に注目した時、その辺の答えへの寄与数は、辺の両側の頂点数の積。
  2. 重みが大きい辺から見ていって、辺の両側の頂点数の積に重みを掛けた値を答えに足して、辺を切り離すということをやっていきたい。
  3. 頂点数はあらかじめ木DPをしておけばわかる。
  4. と、そこまで実装してから、切り離すってどうやれば？　となる。
    　
  5. 逆に重みが小さい辺から見ていって、くっつけていくことを考えてみると、UnionFindを使って、結合する前に両側の連結成分のサイズを掛ければよさそうとわかる。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

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]);
        Hen[] arr = new Hen[n - 1];
        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;
            int c = Integer.parseInt(sa[2]);

            Hen h = new Hen(a, b, c);
            arr[i] = h;
        }
        br.close();

        // cの昇順
        Arrays.sort(arr, (o1, o2) -> o1.c - o2.c);

        UnionFind uf = new UnionFind(n);
        long ans = 0;
        for (Hen h : arr) {
            long v1 = uf.size(h.a);
            long v2 = uf.size(h.b);
            ans += v1 * v2 * h.c;
            uf.union(h.a, h.b);
        }
        System.out.println(ans);
    }

    static class Hen {
        int a, b, c;

        public Hen(int a, int b, int c) {
            this.a = a;
            this.b = b;
            this.c = c;
        }
    }

    // 以下ライブラリ

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

        /**
         * xを含む連結成分のサイズ
         */
        int size(int x) {
            return size[find(x)];
        }
    }
}

ここまで26分04秒＋1ペナ。417位。


E - Packing Under Range Regulations

問題
ハマりすぎ。だがそれでもF問題以降よりはできそうな気がしたので飛ばさずやり続けた。

思考過程
  1. LとRを混ぜて昇順に並べ、Lの箇所で+1、Rの箇所で-1して累積和を取り（いもす法）、同じ値が続く区間の長さが常に値以上であれば"Yes"のような感じ？　とか考えたりするが全然違う。
    　
  2. 最後にボールを入れた位置と、まだ箱に入れられていないボールの数を管理しながら進めていくような感じを考えるが、まだ15/62ケースくらいしか合わない。（手元で適当にケースを作る限りでは駄目なケースが全然見つからないのだが）
    　
  3. 区間スケジューリング問題のように、ボールをRの昇順に並べて貪欲？　いやこれはLが小さいボールを先に決めた方が良いケースが普通にあるので明らかに違う。
  4. ならLの昇順？と思うが、Lが近いものが大量にあったりすると、Rが小さいものを先に処理しなければならないケースもある。
    　
  5. つまり、Rの昇順に取り出すPriorityQueueに、Lの昇順に入れていくような感じが正しそう。
  6. 次にボールを入れられる位置をxとすると、L \leq xであるボールを全てPriorityQueueに入れ、Rが最小のものを1つ取り出して処理していく形にする。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.PriorityQueue;

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);
        label:
        for (int z = 0; z < t; z++) {
            int n = Integer.parseInt(br.readLine());
            Obj[] arr = new Obj[n];
            for (int i = 0; i < n; i++) {
                String[] sa = br.readLine().split(" ");
                Obj o = new Obj();
                o.l = Integer.parseInt(sa[0]);
                o.r = Integer.parseInt(sa[1]);
                arr[i] = o;
            }
            Arrays.sort(arr);

            // Rの昇順に取り出すキュー
            PriorityQueue<Obj> que = new PriorityQueue<>((o1, o2) -> o1.r - o2.r);

            int x = 0; // ボールを入れる箱の位置
            int idx = 0;
            for (int i = 0; i < n; i++) {
                // キューが空の場合は、次にキューに追加するボールの位置まで進める
                if (idx < n && que.isEmpty()) {
                    x = arr[idx].l;
                }
                while (idx < n && arr[idx].l <= x) {
                    que.add(arr[idx]);
                    idx++;
                }
                Obj o = que.poll();
                if (x > o.r) {
                    pw.println("No");
                    continue label;
                }
                x++;
            }
            pw.println("Yes");
        }
        pw.flush();
        br.close();
    }

    static class Obj implements Comparable<Obj> {
        int l, r, x;

        @Override
        public int compareTo(Obj o) {
            if (l != o.l) {
                return l - o.l;
            }
            return r - o.r;
        }
    }
}

ここまで89分56秒＋9ペナ。522位。



残り10分でF問題以降は無理。

FはDPっぽさだけは感じていたが、重複排除の方法とかが全くわからず。
Gは問題読んだだけ。
Hは見てもいない。



最終結果：ABCDEの5完、134分56秒、590位、パフォーマンス1762相当
レート変動：2101（Unrated）


6問制の最後の方は4完だらけだったけど、8問になってから一応全部5完なので、E問題は解きやすくはなっているのかな・・・。
F問題は青diffだったのでとりあえず明日には埋める。