AtCoder Regular Contest 106 - ks2mのブログ

A - 106
- 思考過程
B - Values
- 思考過程
C - Solutions
- 思考過程
D - Powers
- 思考過程

コンテスト前のレート：1702
レート通りのパフォーマンスが得られる順位：652位（1200点、50分24秒）

A - 106

思考過程

$A$ と $B$ の組み合わせを全探索する。
$1 \leq A, B \lt 60$ くらいで調べれば、探索範囲としては十分だが、オーバーフローした値が条件を満たすようなケースが用意されていたら困る。
$3^1$ ～ $3^{50}$ くらいまで出力してみて、何乗で $10^{18}$ を超えるかを調べ、探索範囲を絞る。 $5$ についても同様。

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));
        long n = Long.parseLong(br.readLine());
        br.close();

        for (int a = 1; a < 39; a++) {
            for (int b = 1; b < 27; b++) {
                if (power(3, a) + power(5, b) == n) {
                    System.out.println(a + " " + b);
                    return;
                }
            }
        }
        System.out.println(-1);
    }

    // 以下ライブラリ

    static long power(long x, long n) {
        if (n == 0) {
            return 1;
        }
        long val = power(x, n / 2);
        val = val * val;
        if (n % 2 == 1) {
            val = val * x;
        }
        return val;
    }
}

ここまで4分06秒＋0ペナ。296位。

B - Values

問題
ACLのDSUにgroupsがあったのを完全に忘れていた。
BFS自力実装で損した時間は3分程度だろうか。

思考過程

連結成分内では、操作を伝播させていけば合計値が変わらない中で自由に値を変えられる。
つまり、連結成分ごとに $a$ の合計と $b$ の合計が一値していればYes。
自分のUnionFindには、連結成分に含まれる頂点の集合を取得する機能がないので、BFSで頑張ることにする。
BFSの始点として全ての頂点を調べ、まだどの連結成分にも含まれていない頂点からのみBFSを行う。

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

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

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

        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            sa = br.readLine().split(" ");
            int c = Integer.parseInt(sa[0]) - 1;
            int d = Integer.parseInt(sa[1]) - 1;
            list.get(c).add(d);
            list.get(d).add(c);
        }
        br.close();

        boolean[] used = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (used[i]) {
                continue;
            }
            long suma = a[i];
            long sumb = b[i];
            Queue<Integer> que = new ArrayDeque<>();
            que.add(i);
            used[i] = true;
            while (!que.isEmpty()) {
                int cur = que.poll();
                for (int j : list.get(cur)) {
                    if (!used[j]) {
                        que.add(j);
                        used[j] = true;
                        suma += a[j];
                        sumb += b[j];
                    }
                }
            }
            if (suma != sumb) {
                System.out.println("No");
                return;
            }
        }
        System.out.println("Yes");
    }
}

ここまで10分13秒＋0ペナ。171位。

C - Solutions

問題

思考過程

高橋君実装が求めているのは最適解。これは緑difficultyのキーエンス2020-B：Robot Armsが解けなくて悔しい思いをしたのを覚えていた。
よって、 $M \lt 0$ の場合は-1。
　
とりあえず $[10:20], [30:40], [50:60], \cdots$ のような $N-1$ 個の区間を作ってみる。
青木君実装の最適でない場合を考えると、残り個の区間をとして、
- $A=2$ とすると、どちらも $N$ 個になって $M=0$ 。
- $A=11$ とすると、どちらも $N-1$ 個になって $M=0$ 。
- $A=31$ とすると、高橋君 $N-1$ 個、青木君 $N-2$ 個になって $M=1$ 。
- $A=51$ とすると、高橋君 $N-1$ 個、青木君 $N-3$ 個になって $M=2$ 。
このように、 $A$ の調節次第で $0 \leq M \leq N-2$ を自由に構築できる。
実装上、 $[10:15], [20:25], [30:35], \cdots$ のようにした方が、 $A$ の計算を間違えなそうだったので、そのようにする。
　
青木君側を $0$ 個にはできないため、この方法では $M \geq N-1$ の場合は構築できない。
高橋君 $N$ 個、青木君 $1$ 個にするのも無理なので、やはり $M \geq N-1$ の場合は無理そう。　→1ケースWA
$N=1, M=0$ の場合は構築可能であったので、-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));
        String[] sa = br.readLine().split(" ");
        int n = Integer.parseInt(sa[0]);
        int m = Integer.parseInt(sa[1]);
        br.close();

        if (m < 0 || (n > 1 && m >= n - 1)) {
            System.out.println(-1);
            return;
        }

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 1; i < n; i++) {
            int a = i * 10;
            pw.println(a + " " + (a + 5));
        }
        int a = m * 10 + 11;
        if (m == 0) {
            a = 2;
        }
        pw.println(1 + " " + a);
        pw.flush();
    }
}

ここまで26分09秒＋1ペナ。119位。

D - Powers

問題
解けず。EとFも10分ずつくらいは考えたが無理。
$_NC_2$ 通り全部の計算をしたいけど、 $N \leq 10^5$ で愚直は無理。というタイプの問題がなかなかできるようにならない。

思考過程

愚直に計算すると $O(KN^2logK)$ くらい。 $X$ 乗の部分を繰り返し二乗法ではなく、前回の結果を残しておいても $O(KN^2)$ 。
$_NC_2$ 部分については、二次元表にしてみたときに、 $N^2$ 個のマスの総和から斜めを引いて半分にするとか、縦か横に上手くまとめて $N^2$ かかるのを $N+N$ にするとかを考える。
後者で考え、累積和や二項係数を駆使して $N$ を落とすことはできたが、 $1 \leq X \leq K$ の各 $X$ について $O(XN)$ かかる計算になってしまったため、全体で $O(K^2N)$ となり、TLE。