AtCoder Beginner Contest 206(Rated範囲外)

A - Maxi-Buying
- 思考過程
B - Savings
- 思考過程
C - Swappable
- 思考過程
D - KAIBUNsyo
- 思考過程
E - Divide Both
- 思考過程

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

A - Maxi-Buying

思考過程

とりあえず $N \times 1.08$ を計算する。
int型にキャストすれば、切り捨ての値を求められる。
あとは計算結果と $206$ を比較して出力し分ける。
面倒だが出力する文字列は一応コピペする。（"so-so"を"50-50"と手書きしそうになった）

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();

        int x = (int) (n * 1.08);
        if (x > 206) {
            System.out.println(":(");
        } else if (x == 206) {
            System.out.println("so-so");
        } else {
            System.out.println("Yay!");
        }
    }
}

ここまで1分36秒＋0ペナ。269位。

B - Savings

問題

思考過程

$i$ 日目に入っている金額は $\frac{i(i+1)}{2}$ 円なので、 $N$ 以上になるまで無制限にループを回しても $O(\sqrt{N})$ 。
毎回上記の通り計算してもいいが、題意通り毎回 $i$ を足してもよい。

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();

        int s = 0;
        for (int i = 1; ; i++) {
            s += i;
            if (s >= n) {
                System.out.println(i);
                return;
            }
        }
    }
}

ここまで2分22秒＋0ペナ。63位。

C - Swappable

問題

思考過程

$N$ 個から $2$ 個を選ぶ全組合せ $_NC_2=\frac{N(N-1)}{2}$ 通りから、同じ値である要素の中から $2$ 個を選ぶ組合せを引く。

import java.util.HashMap;
import java.util.Map;
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();
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int a = sc.nextInt();
            map.put(a, map.getOrDefault(a, 0) + 1);
        }
        sc.close();

        long ans = (long) n * (n - 1) / 2;
        for (int v : map.values()) {
            ans -= (long) v * (v - 1) / 2;
        }
        System.out.println(ans);
    }
}

ここまで4分23秒＋0ペナ。94位。

D - KAIBUNsyo

問題

思考過程

最終的に、前から $i$ 番目と後ろから $i$ 番目の値を同じにする必要がある。
例えば、 $A=(1, 2, 2, 1, 3, 4, 1)$ のような場合、 $2, 3, 4$ を同じ値にする。
UnionFindを使って前から $i$ 番目と後ろから $i$ 番目の値を連結していけば、同じ値にするものが同じ連結成分になっている。
　
答えは異なる連結成分を連結した回数となり、それは「 $N-$ 連結成分の個数」と求めることもできる。　→RE
UnionFindのサイズは $N$ ではなく $A_{max}$ だった。

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 = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        sc.close();

        int m = 200001;
        UnionFind uf = new UnionFind(m);
        int n2 = n / 2;
        for (int i = 0; i < n2; i++) {
            if (a[i] != a[n - 1 - i]) {
                uf.union(a[i], a[n - 1 - i]);
            }
        }
        System.out.println(m - uf.num);
    }

    // 以下ライブラリ

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

ここまで8分30秒＋1ペナ。89位。
5分経過後には300位程度。

E - Divide Both

問題

思考過程

$L \leq x \lt R$ の全ての $x$ について、 $x$ の約数の倍数 $y$ の内 $x \lt y \le R$ であるものを数える？
それだと例えば $x=12$ の時に、 $2$ の倍数と $4$ の倍数を重複して数えてしまったりする。
　
$g$ を全探索して、 $g$ の倍数 $y$ の内 $L \le y \le R$ であるものを $z$ 個として $_zC_2$ の総和を求める？
それだと最大公約数が $g$ でない組合せを数えてしまう。
　
上記1.に戻って、重複して数えずに済む方法を考える。
$y$ の重複を避けようとしたときに、 $x$ の約数として考えるべきは、 $x$ の各素因数が $1$ 個以下である値のみ。
例えば $x=2^p \times 3^q \times 5^r$ だとしたら、 $2, 3, 5, 6, 10, 15, 30$ の倍数を重複なく数えることを考える。
これは包除原理を用いて、素因数の数が奇数なら足し、偶数なら引くことで、 $x$ 超 $R$ 以下の範囲の「 $2$ の倍数の個数 $+$ $3$ の倍数の個数 $+$ $5$ の倍数の個数 $-$ $6$ の倍数の個数 $-$ $10$ の倍数の個数 $-$ $15$ の倍数の個数 $+$ $30$ の倍数の個数」のように求められる。
素因数が $1$ 個以下である値の列挙は、素因数の個数を $n$ として、 $2^n-1$ 通り（全素因数が $0$ 個は除く）を調べる。
これだけだと最大公約数が $x$ の場合を数えてしまっているので、それを引く。
　
まだ例３が合わない。
$x$ が素数の場合、素因数が $1$ つで最大公約数が $x$ になるケースしか調べられないので、一応スキップさせてみる。
さらにデバッグしてみると、 $x=1$ の場合におかしなことになっていたので、スキップさせてみる。

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

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

        Eratosthenes era = new Eratosthenes(r);
        long ans = 0;
        for (int x = l; x < r; x++) {
            // 12, 13
            if (x == 1 || era.isSosuu(x)) {
                continue;
            }

            Map<Integer, Integer> map = era.bunkai(x); // 素因数分解
            Integer[] arr = map.keySet().toArray(new Integer[0]);
            int n = arr.length;
            int cnt = 0;
            // 9
            int end = 1 << n;
            for (int i = 1; i < end; i++) {
                int a = 1;
                int c = 0; // 使った素因数の個数
                for (int j = 0; j < n; j++) {
                    if ((i >> j & 1) == 1) {
                        a *= arr[j];
                        c++;
                    }
                }
                // 8
                int v = r / a - x / a;
                if (c % 2 == 1) {
                    cnt += v;
                } else {
                    cnt -= v;
                }
            }
            // 10
            int v = r / x - x / x;
            cnt -= v;
            ans += cnt;
        }
        System.out.println(ans * 2);
    }

    // 以下ライブラリ

    static class Eratosthenes {
        int[] div;

        public Eratosthenes(int n) {
            if (n < 2) return;
            div = new int[n + 1];
            div[0] = -1;
            div[1] = -1;
            int end = (int) Math.sqrt(n) + 1;
            for (int i = 2; i <= end; i++) {
                if (div[i] == 0) {
                    div[i] = i;
                    for (int j = i * i; j <= n; j+=i) {
                        if (div[j] == 0) div[j] = i;
                    }
                }
            }
            for (int i = end + 1; i <= n; i++) {
                if (div[i] == 0) div[i] = i;
            }
        }

        public Map<Integer, Integer> bunkai(int x) {
            Map<Integer, Integer> soinsu = new HashMap<>();
            while (x > 1) {
                Integer d = div[x];
                soinsu.put(d, soinsu.getOrDefault(d, 0) + 1);
                x /= d;
            }
            return soinsu;
        }

        public boolean isSosuu(int x) {
            return div[x] == x;
        }
    }
}

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

Fは解けず。
共有点を持つ区間同士に辺を張ったグラフを作って、連結成分ごとにGrundy数を求められればなどと考えていた。

最終結果：ABCDEの5完1500点、64分27秒、402位、パフォーマンス1912相当
レート変動：2074（Unrated）

最近のABCではDまでを結構早く解けていることが多く、今回も1ミスはあったもののすんなり解けてよかった。

Eはあと20分早く通せないとレート2000台の平均には並べないっぽいけど、やっている時は全然できる気がしなかったので、通せただけでもマシだった。

Fができなかったことから、やっぱりEDPCやTDPCはそろそろ埋め切っておかないと駄目かなという感じ。
埋めるといっても、ほとんど解説ACすることになると思うけど。
確認したら、現在EDPCが23/26でTDPCが7/20。