AtCoder Beginner Contest 210(Rated範囲外)

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

A - Cabbages

問題
いつもよりややこしめ。

思考過程

1. とりあえず、が以下かどうかで分けて考える。
2. の場合、円が個。
3. の場合、円が個と円が個。

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 a = sc.nextInt();
        int x = sc.nextInt();
        int y = sc.nextInt();
        sc.close();

        if (n <= a) {
            System.out.println(x * n);
        } else {
            System.out.println(x * a + y * (n - a));
        }
    }
}

ここまで1分29秒＋0ペナ。378位。

B - Bouzu Mekuri

問題

思考過程

1. 前から順に見ていって、初めて'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();
        char[] s = sc.next().toCharArray();
        sc.close();

        for (int i = 0; i < n; i++) {
            if (s[i] == '1') {
                if (i % 2 == 0) {
                    System.out.println("Takahashi");
                } else {
                    System.out.println("Aoki");
                }
                return;
            }
        }
    }
}

ここまで2分43秒＋0ペナ。109位。

C - Colorful Candies

問題

思考過程

1. まず最初の個を何らかの集合に入れる。
2. それ以降は個目をに入れて個目をから取り出す。
3. 上記2.を繰り返しながら内の種類数の最大値を求めたい。
4. には、＜色、個数＞のMapを使えばよい。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

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

        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < k; i++) {
            addCntMap(map, c[i]);
        }
        int ans = map.size();
        for (int i = k; i < n; i++) {
            addCntMap(map, c[i]);
            delCntMap(map, c[i - k]);
            ans = Math.max(ans, map.size());
        }
        System.out.println(ans);
    }

    // 以下ライブラリ  というほどでもないけど元々用意していたもの

    static void addCntMap(Map<Integer, Integer> map, Integer key) {
        map.put(key, map.getOrDefault(key, 0) + 1);
    }

    static void delCntMap(Map<Integer, Integer> map, Integer key) {
        if (key != null && map.containsKey(key)) {
            int val = map.get(key);
            if (val == 1) {
                map.remove(key);
            } else {
                map.put(key, val - 1);
            }
        }
    }
}

ここまで5分30秒＋0ペナ。64位。

D問題は解けず。
答えの二分探索でできないかとか、45度回転で何か起こらないかとかは考えていたが、DPという発想が全くなかった。

E - Ring MST

問題
勝手にくらいだと思い込んでいた。

思考過程

1. クラスカル法をすれば最小値は求められそう。
2. の小さい順にペアソートし、とが同一連結成分でない限りを答えに足していく。
3. これだと全部調べるとだが、各 について、 の探索を、同一連結成分に当たった時点で打ち切れば（最初は実験的ではあったが、根拠は下記7～8.）、で解けそう。　→RE
   　
4. どこかで添え字ミスでもしたのかと数分悩んだが、ここでであることに気付き、実際はMLEであったらしいことがわかる。*1
   　
5. やっていること自体は合っていそうだったので、実際にクラスカル法をせずに答えを計算する方法を考える。
6. 要は、種類の各操作がそれぞれ何回行われるかが問題。
   　
7. 最初の操作は、とすると、回行え、個の連結成分が残る。
8. この時、各連結成分はを満たすを先頭（代表）として構成されているので、これに対して元の問題を解けばよい。
9. 最終的に、全体のgcdがでなければ（合計回の操作を行えていなければ）となる。

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]);
        int m = Integer.parseInt(sa[1]);
        Obj[] arr = new Obj[m];
        for (int i = 0; i < m; i++) {
            sa = br.readLine().split(" ");
            Obj o = new Obj();
            o.a = Integer.parseInt(sa[0]);
            o.c = Integer.parseInt(sa[1]);
            arr[i] = o;
        }
        br.close();

        Arrays.sort(arr, (o1, o2) -> o1.c - o2.c);
        int gcd = n;
        long ans = 0;
        for (Obj o : arr) {
            int b = gcd(gcd, o.a);
            ans += (long) (gcd - b) * o.c;
            gcd = b;
        }
        if (gcd != 1) {
            ans = -1;
        }
        System.out.println(ans);
    }

    static class Obj {
        int a, c;
    }

    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

ここまで25分39秒＋1ペナ。73位。

F問題は解けず。
実は真っ先に2-SATじゃないかと一瞬思ったりはしていたのだが、その考えをすぐに捨て去っていた。
何度かD問題と行ったり来たりしつつ、フローの構成方法を考えて、複数の素因数を持つ場合をどうしても表せないと思ったりしていた。

最終結果：ABCEの4完1100点、30分39秒、542位、パフォーマンス1782相当
レート変動：2129（Unrated）

またまた4完しかできず、レート以上のパフォを勝ちとしてABC7連敗。
今回はそれなりにスピードも出ていて、あとDさえすんなり解ければ2400もあり得たくらいだったのに、毎回DかEのどちらかでことごとくコケ続けている。

なんかABC＝典型のような風潮があるけど、個人的には今回典型と思えたのはC問題だけだった。
D問題もまあ後から見方を変えてみれば、似たようなのはないこともないと思えないこともないけど、今回は正直盲点だった。

*1:Javaでは、MLEの場合OutOfMemoryErrorが発生してREという結果になるらしい。