AtCoder Regular Contest 135

コンテスト前のレート：2074
レート通りのパフォーマンスが得られる順位：308位（1300点、46分06秒）

A - Floor, Ceil - Decomposition

問題

思考過程

1. であれば操作を行うとすると、のものが存在する限り操作を行い続けることになる。
2. である限りQueueに分割後の値を追加し続けるシミュレーションを行ってみたら、しばらく待ってもプログラムが終了しなかったので、メモ化的な工夫が必要そう。
3. 今更メモ化再帰で書き直すのも面倒なので、データの持ち方をMap＜値、個数＞としてシミュレーションを行うことにする。

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);
        long x = sc.nextLong();
        sc.close();

        int mod = 998244353;
        Map<Long, Long> map = new HashMap<>();
        map.put(x, 1L);
        long ans = 1;
        while (!map.isEmpty()) {
            Map<Long, Long> wk = new HashMap<>();
            for (Long k : map.keySet()) {
                long v = map.get(k);
                if (k < 5) {
                    ans *= power(k, v, mod);
                    ans %= mod;
                } else {
                    wk.put(k / 2, wk.getOrDefault(k / 2, 0L) + v);
                    wk.put((k + 1) / 2, wk.getOrDefault((k + 1) / 2, 0L) + v);
                }
            }
            map = wk;
        }
        System.out.println(ans);
    }

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

ここまで11分09秒＋0ペナ。521位。

B - Sum of Three Terms

問題
感覚的にはどこか穴があってもおかしくはないと思いながら投げたが、通ったのでヨシ。

思考過程

1. 、の差分を比較すると、のようになり、これを最後まで見ていくと、 ごとにグループ化され、例えばはの形で表すことができる。
2. のグループごとにの最小値を求め、それぞれ最小のものがになるように調整する。
3. この時点で、がより大きくなる箇所があれば"No"。
4. というかとの差はによらず一定のはずなので、適当に先頭箇所でこの差を求めておく。
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));
        int n = Integer.parseInt(br.readLine());
        String[] sa = br.readLine().split(" ");
        int[] s = new int[n];
        for (int i = 0; i < n; i++) {
            s[i] = Integer.parseInt(sa[i]);
        }
        br.close();

        // 1
        int[] b = new int[n - 1];
        for (int i = 0; i < n - 1; i++) {
            b[i] = s[i + 1] - s[i];
        }
        long[] a = new long[n + 2];
        for (int i = 0; i < n - 1; i++) {
            a[i + 3] = a[i] + b[i];
        }

        // 2
        long[] min = new long[3];
        for (int i = 0; i < n + 2; i++) {
            min[i % 3] = Math.min(min[i % 3], a[i]);
        }
        for (int i = 0; i < n + 2; i++) {
            a[i] = a[i] - min[i % 3];
        }

        // 3
        for (int i = 0; i < n; i++) {
            if (a[i] + a[i + 1] + a[i + 2] > s[i]) {
                System.out.println("No");
                return;
            }
        }

        System.out.println("Yes");
        long d = s[0] - a[0] - a[1] - a[2]; // 4
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n + 2; i++) {
            if (i % 3 == 0) {
                sb.append(a[i] + d).append(' '); // 5
            } else {
                sb.append(a[i]).append(' ');
            }
        }
        sb.deleteCharAt(sb.length() - 1);
        System.out.println(sb.toString());
    }
}

ここまで30分15秒＋0ペナ。356位。

C - XOR to All

問題

思考過程

1. 進数表現の各桁について、の内であるものの方が多ければ、であるものの方が多ければとしたものをとするだけでは？と思ったら、はの中からしか選べなかった。
2. 最良のと上の方の桁が最も長く連続して一致するものを選べばよいかというと、桁つの違いは全然越えられない壁ではなく、上の方が桁一致してそれ以降全部不一致よりも、その逆の方がよいことはいくらでもありそう。
   　
3. 各桁がの場合の貢献度（の方がよい場合はマイナスになる）を求めておき、の中で貢献度が最大のものをとして選ぶことにする。
4. ただし、全てマイナスの場合は（操作しない）とする。

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

        int m = 30;
        long[] b = new long[m]; // 各桁の貢献度
        for (int i = 0; i < m; i++) {
            int c1 = 0; // aの中でi桁目が1の個数
            for (int j = 0; j < n; j++) {
                c1 += a[j] >> i & 1;
            }
            int c0 = n - c1; // aの中でi桁目が0の個数
            b[i] = (1L << i) * (c0 - c1);
        }

        // aの中で貢献度の最大値とそのindexを求める
        long max = 0;
        int idx = -1;
        for (int i = 0; i < n; i++) {
            long val = 0;
            for (int j = 0; j < m; j++) {
                if ((a[i] >> j & 1) == 1) {
                    val += b[j];
                }
            }
            if (val > max) {
                max = val;
                idx = i;
            }
        }

        long ans = 0;
        long x = 0;
        if (idx != -1) {
            x = a[idx];
        }
        for (int i = 0; i < n; i++) {
            a[i] ^= x;
            ans += a[i];
        }
        System.out.println(ans);
    }
}

ここまで58分19秒＋0ペナ。403位。

残り時間はDとFで嘘解法を書いていてやっぱりWA＆TLE。

最終結果：ABCの3完1300点、58分19秒、410位、パフォーマンス1930
レート変動：2074→2060（-14）

3完早解き勝負敗北。
まあでも傷は十分浅かったし、あまり時間かかり過ぎない範囲で通すべきものは通せてよかった。