AtCoder Regular Contest 116

コンテスト前のレート：2030
レート通りのパフォーマンスが得られる順位：378位（1700点、59分45秒）

A - Odd vs Even

問題

思考過程

1. 素因数にが個でも含まれていたら偶数の方が多かったりする？などと思いつつ、とかとかで数えてみると、同数になる。
2. 素因数にが個の場合は、以外の素因数の組み合わせにを掛けるか掛けないかで同数になる模様。
3. 素因数にがもう個あれば、明らかに偶数がもっと増える。
4. で割り切れれば"Even"、それ以外でで割り切れれば"Same"、それ以外は"Odd"とする。

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 t = Integer.parseInt(br.readLine());
        PrintWriter pw = new PrintWriter(System.out);
        for (int z = 0; z < t; z++) {
            long n = Long.parseLong(br.readLine());
            if (n % 4 == 0) {
                pw.println("Even");
            } else if (n % 2 == 0) {
                pw.println("Same");
            } else {
                pw.println("Odd");
            }
        }
        br.close();
        pw.flush();
    }
}

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

B - Products of Min-Max

問題

思考過程

1. をソートすると、をと固定したときのの和は、～の和になる？（和を求める部分は累積和を使って）と思ったが、例１がとなり、のケースが漏れている。
2. 、となる回数が何回あるかを考えると、との間の要素はに含めるかどうかを自由に選べるので、回となる。（は間の要素数）
3. 累積和を求める時点で、単純にを足していくのではなく、を足すようにしておく。
   　
4. あとは、上記1.で～の和に相当する部分を求める際に、全体が倍くらいになっているので、その分を割る。
5. 正確には、欲しいのは「」なので、累積和の～部分をで割ったものにを足す。
   　
6. 結構WAが出たが、計算途中でマイナスになることがあるのを対処していなかったせいっぽかったので直す。

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

        int mod = 998244353;
        Arrays.sort(a);

        // 2のi乗
        long[] p = new long[n + 1];
        p[0] = 1;
        for (int i = 1; i < p.length; i++) {
            p[i] = p[i - 1] * 2 % mod;
        }

        // 3
        long[] b = new long[n + 1];
        for (int i = 0; i < n; i++) {
            b[i + 1] = b[i] + a[i] * p[i];
            b[i + 1] %= mod;
        }

        long ans = 0;
        for (int i = 0; i < n; i++) {
            long d = b[n] - b[i + 1];
            d %= mod;
            // 6
            if (d < 0) {
                d += mod;
            }
            // 4, 5
            d *= modinv(p[i + 1], mod);
            d += a[i];
            d %= mod;
            ans += d * a[i] % mod;
            ans %= mod;
        }
        System.out.println(ans);
    }

    // 以下ライブラリ

    static long modinv(long a, int m) {
        long b = m;
        long u = 1;
        long v = 0;
        long tmp = 0;

        while (b > 0) {
            long t = a / b;
            a -= t * b;
            tmp = a;
            a = b;
            b = tmp;

            u -= t * v;
            tmp = u;
            u = v;
            v = tmp;
        }

        u %= m;
        if (u < 0) u += m;
        return u;
    }
}

ここまで19分49秒＋1ペナ。647位。

C - Multiple Sequences

問題
どうして下記7.から単純な掛け算ではなく、8.のような余計なことをしてしまったのか。それで大幅ロス。

思考過程

1. とりあえず例１の通りを辞書順に列挙してみる。
2. 列挙したものを、の最後の要素ごとに分けることもしてみる。
3. 「番目まで見て最後の要素がである場合の数」をしたいが、これだとメモリだけでかかってしまう。
   　
4. 例１をもう少し大きくして「4 6」くらいの入力に対して遷移を書き出してみると、約数の個数ごとに同じ階差数列になっているように見えたので、そうなっているものと決め付けて、約数の個数ごとに番目の値を算出してみる。
5. 約数の個数の最大は160個程度っぽかったので、約数の個数ごとにで前計算しても間に合いそう。だが例２が全く合わない。
   　
6. 上記2.まで戻って、の最後の要素をとしたときの数列の数は、の素因数を個の要素の間（の前からの前までの箇所）に任意に配置する場合の数とみなせそう。
7. これは、素因数を種類とすれば、個の素因数と個の仕切りを並べる場合の数となる。
   　
8. 素因数が複数種類ある場合は、例えば「2223355|||」を並べる場合の数と同じか？と思ったが、「222|35|3|5」と「222|53|3|5」のように仕切りの間内で並び順が異なるケースは通りと数える必要があり、これでは合わない。
9. 仕切りとある種類の素因数との位置関係のパターンは上記7.で求まっており、種類以上に増えたところで、それぞれの上記7.の結果を単純に掛け算すればいいだけだった。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;
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 m = Integer.parseInt(sa[1]);
        br.close();

        int mod = 998244353;
        Eratosthenes era = new Eratosthenes(m);

        int n2 = n + 1000; // mを2で割れる回数が必要な最大値なので、20くらいで十分だった
        Kaijou kai = new Kaijou(n2, mod);

        long ans = 1; // 数列の最後が1の場合
        // 最後が2～mまで全部試す
        for (int i = 2; i <= m; i++) {
            Map<Integer, Integer> map = era.bunkai(i);
            long val = 1;
            for (int v : map.values()) {
                val *= kai.comb(n + v - 1, v); // 7
                val %= mod;
            }
            ans += val;
        }
        ans %= mod;
        System.out.println(ans);
    }

    // 以下ライブラリ

    // 階乗を前計算して組合せnCrをO(1)で求める
    static class Kaijou {
        long[] p, pi;
        int m;

        public Kaijou(int n, int mod) {
            n++;
            m = mod;
            p = new long[n];
            pi = new long[n];
            p[0] = 1;
            pi[0] = 1;
            for (int i = 1; i < n; i++) {
                p[i] = p[i - 1] * i % m;
            }
            pi[n - 1] = BigInteger.valueOf(p[n - 1])
                    .modInverse(BigInteger.valueOf(m)).longValue();
            for (int i = n - 1; i > 1; i--) {
                pi[i - 1] = pi[i] * i % m;
            }
        }

        public long comb(int n, int r) {
            if (n < r) return 0;
            return p[n] * pi[r] % m * pi[n - r] % m;
        }
    }

    // エラトステネスの篩
    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;
        }
    }
}

ここまで97分02秒＋1ペナ。904位。

D以降は解けず。

D問題は、「番目まで見てxorがで合計が」といったDPくらいしか思いつかなかった。
くらいはかかりそうなので無理だと、さっさと諦めた。

E問題の方が、だいぶ怪しいけど一応思い付いたことはあったので、やるだけやってみた。
公式解説通り二分探索と問題を作るところまではできていたが、それが20分では解けず。
深い葉から見ていって、その葉に対する特別な頂点がまだ存在しなければ個先の親を特別な頂点とする貪欲をしたつもりで、例３が4になってしまった。

F問題は問題見てすぐに閉じた。

最終結果：ABCの3完、102分02秒、927位、パフォーマンス1496
レート変動：2030→1986（-44）

正直悪くても-25くらいで、一発で青に落ちる方が難しいだろうと思っていたが、だいぶ甘かった。
とはいえ、D問題は解説チラ見程度では全くわからないままだし、ここ最近のABCのボロボロさからしても、これでもマシな方だったかもしれない。
果たして、再び黄色に上がることはできるのだろうか。