AtCoder Beginner Contest 172

ABC

コンテスト前のレート：1719
レート通りのパフォーマンスが得られる順位：630位

A - Calc

問題
最近本当に問題文の通りやるだけのA問題が増えたような？
以前はもう少しif文を使った気がする。

思考過程
  1. 問題文の通り計算する。
  2. 累乗の関数とか使わなくても掛け算を並べた方が早い。
import java.util.Scanner;

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

        System.out.println(a + a*a + a*a*a);
    }
}

ここまで0分24秒＋0ペナ。116位。


B - Minor Change

問題
これはまあA問題よりは多少は問題文を言い換えられているが・・。

思考過程
  1. 文字を書き換える必要があるのは、S, Tのi文字目同士が異なる場合。
  2. 文字列の先頭から順にi文字目同士を比較し、異なった数をカウントする。
import java.util.Scanner;

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

        int ans = 0;
        for (int i = 0; i < t.length; i++) {
            if (s[i] != t[i]) {
                ans++;
            }
        }
        System.out.println(ans);
    }
}

ここまで1分23秒＋0ペナ。172位。


C - Tsundoku

問題
実装ミスが非常に怖かったがなんとかバグらせずに済んだ。

思考過程
  1. 前から貪欲にA, Bの先頭の小さい方を取ったのでは、ちょっと所要時間が大きい本の後ろに小さい本がたくさん並んでたりするとおかしそう。
  2. Aの方から何冊読むかを、0からNまで全探索する。
  3. ただし、毎回B_1からK分を超えないところまで足していたのでは、O(NM)でTLEになりそう。
  4. まずAを1冊も読まない場合にBを読めるところまで足しておき、以後Aを増やしていくごとに、Bを必要なだけ減らしていく。
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));
        String[] sa = br.readLine().split(" ");
        int n = Integer.parseInt(sa[0]);
        int m = Integer.parseInt(sa[1]);
        int k = Integer.parseInt(sa[2]);
        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[m];
        for (int i = 0; i < m; i++) {
            b[i] = Integer.parseInt(sa[i]);
        }
        br.close();

        int ans = 0;
        int sum = 0;
        int j = -1;
        for (int i = 0; i < m; i++) {
            if (sum + b[i] <= k) {
                sum += b[i];
                j = i;
            } else {
                break;
            }
        }
        ans = j + 1; // Aが0冊の場合の答え

        for (int i = 0; i < n; i++) {
            // Aを1冊増やす
            sum += a[i];
            // 合計がK以下になるまでBを減らす
            while (j >= 0 && sum > k) {
                sum -= b[j];
                j--;
            }
            if (sum <= k) {
                ans = Math.max(ans, i + j + 2);
            } else {
                // Bを0冊にしてもKを超える場合は終了
                break;
            }
        }
        System.out.println(ans);
    }
}

ここまで7分56秒＋0ペナ。179位。


D - Sum of Divisors

問題
持っているライブラリを使って通ってくれて助かった。
サンプルに最大ケースがあるのは優しい。

思考過程
  1. O(\sqrt{n})で約数を列挙するライブラリを使ってみる。　→10秒以上終わらない
  2. O(\sqrt{n})だが、多少は早くなると思い、素因数分解して累乗数を元に計算するライブラリを使ってみる。　→同じく無理
  3. 素因数分解部分をエラトステネスの篩に変えてみる。　→だいたい2秒くらい。一旦ネタ切れなのでとりあえず投げてみたら、時間制限が3秒だったおかげで通った。
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));
        int n = Integer.parseInt(br.readLine());
        br.close();

        Eratosthenes era = new Eratosthenes(n);
        long ans = 0;
        for (int i = 1; i <= n; i++) {
            ans += (long) i * getDivCnt(era, i);
        }
        System.out.println(ans);
    }

    // 以下ライブラリ

    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];
                if (soinsu.containsKey(d)) {
                    soinsu.put(d, soinsu.get(d) + 1);
                } else {
                    soinsu.put(d, 1);
                }
                x /= d;
            }
            return soinsu;
        }
    }

    // 2^p * 3^q * ・・・のように素因数分解されているものを
    // (p+1) * (q+1) * ・・・のように計算する
    static int getDivCnt(Eratosthenes era, int val) {
        Map<Integer, Integer> soinsu = era.bunkai(val);
        int cnt = 1;
        for (int key : soinsu.keySet()) {
            cnt *= soinsu.get(key) + 1;
        }
        return cnt;
    }
}

ここまで16分02秒＋0ペナ。232位。


E - NEQ

問題
5分ほど考えて全くわからず、先に一応F問題を見たらそちらの方がすぐに方針が見えてきたので先にそちらを解く。
戻った後も以下のようなことを考えたけど解けず。

思考過程
  1. とりあえずAだけ見ると、要素は全て異なるので、全部で_MP_N通り。
  2. Bも単体で見ればAと同様だが、Aと同じ位置に同じ要素があってはいけない。
  3. Aを(1, 2, \cdots, N)と固定した場合のBの並べ方が何通りかを求め、最後に_MP_N倍する。
  4. dp0[i]：i番目まででAと同じ要素なし
    dp1[i]：i番目まででAと同じ要素あり
    というものを考えてみるが、これではi+1番目を計算するときにi+1番目の要素が既に使われているかがわからないことにより、遷移が正しく計算できなくてNG。

F - Unfair Nim

問題
問題名にNimとか入ってるのが少しヒントになっているような。

思考過程
  1. 山からは石を何個でも取り除けるので、問題のA_1からA_2に移す操作がなければ、Grundy数は単純に全部のxorになる。
  2. 移す操作を行うことで、「A_1xorA_2=A_3～A_Nのxor」にできるかどうかという問題になった。
  3. 移す個数を0～A_1-1まで全部試し、条件を満たせばその時の個数、最後まで満たさなければ '-1' とする。　→A_i \leq 10^{12}なのでTLE。
  4. 少し言い方を変えると、A_1+A_2個の石を2つに分けて上記2.の条件を満たす方法をどのように高速に見つけるかとなる。
  5. A_1+A_2=A_1xorA_2+2(A_1&A_2)を変形して、
    2(A_1&A_2)=A_1+A_2-A_3～A_Nのxor　となる。
  6. 右辺は全て既知の値になっており、まずは右辺が2で割り切れなければ '-1'。
  7. A_1&A_2とA_1xorA_2で同じ箇所のビットが立っていたらおかしいので、そのようになるようなら '-1'。
  8. A_1に残す個数は最低A_1&A_2であり、A_1xorA_2を上の桁から貪欲に、i桁目が1かつ、減らす個数に加えてもA_i以上にならないように加えていく。　→1ケースWA。
  9. よくわからないので提出デバッグを試みる。'-1' を出力している箇所を全部REするように変えてみる。　→1ケースWAは残ったまま。
  10. 結果をよく見ると、サンプルが2ケースREになるべきところ、1ケースしかREになっていない。
  11. 例２で、A_1&A_2=4>A_1だが、3-4=-1となりたまたまACしていた。この場合を '-1' にする条件が漏れていた。
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(" ");
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = Long.parseLong(sa[i]);
        }
        br.close();

        // 3～N番目のxor
        long xor = 0;
        for (int i = 2; i < n; i++) {
            xor ^= a[i];
        }

        long sum = a[0] + a[1];
        sum -= xor;
        // 思考過程6
        if (sum % 2 == 1) {
            System.out.println(-1);
            return;
        }
        sum /= 2;
        // 思考過程7、11
        if ((sum & xor) != 0 || sum > a[0]) {
            System.out.println(-1);
            return;
        }

        // 思考過程8
        long b = sum; // A[0]に残す個数
        for (int i = 41; i >= 0; i--) {
            if ((xor >> i & 1) == 1) {
                if (b + (1L << i) <= a[0]) {
                    b += (1L << i);
                }
            }
        }
        if (b == 0) {
            System.out.println(-1);
        } else {
            System.out.println(a[0] - b);
        }
    }
}

ABCDFと解いた時点で42分47秒＋3ペナ。15位！
最大瞬間風速1ページ目は滅多にないことだが、結局ここから下がっていく順位を眺めてるだけ。



最終結果：ABCDFの5完、57分47秒、146位、パフォーマンス2288
レート変動：1719→1790

先週の2日連続爆死分-82を今回の+71でほとんど取り戻す結果に。
人々にとっての難易度がE＜Fなのに自分はE＞Fだったのが幸いした。あとDでハマり過ぎなくて助かった。
和とxorの関係の式がちゃんと出てきたのが進歩したところ。