第二回日本最強プログラマー学生選手権(Unrated)

コンテスト前のレート：2011
（Ratedだとしたら）レート通りのパフォーマンスが得られる順位：272位（1600点、98分06秒）

A - Competition

問題
これまでやってきたABC級のA問題の中では圧倒的に最も時間がかかった。
しかも提出コードは怪しさ満載だと思う。

思考過程

1. 整数で誤差なく計算する方法が全然わからず、double型を使ってそのまま計算してみることにする。
2. スーパー高橋のグラム当たりの値段（以下単価とする）は。
3. とりあえずこれと同じ単価でパック作ると、その値段は円。
4. 上記3.を切り捨てればだいたいよいが、単価が同じになるなら円減らす。

答えを～の範囲で全探索してみるのもありだったかもしれない。

import java.util.Scanner;

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

        int ans = (int) ((double) y / x * z);
        if ((double) y / x <= (double) ans / z) {
            ans--;
        }
        System.out.println(ans);
    }
}

ここまで9分42秒＋0ペナ。2058位。

B - Xor of Sequences

問題

思考過程

1. とりあえずのSetとのSetを作る。
2. の全要素を見て、に含まれていないものを答えのPriorityQueueに追加する。
3. 逆も同様。
4. 拡張forループでPriorityQueueの要素を見ていって連結して出力する。　→WA
   　
5. もしかして重複要素でもあった？と、ないとは思いつつ、TreeSetに変えてみる。　→AC。

PriorityQueueは、拡張forループで全要素処理しようとしても昇順には取り出されないのが原因だった（TreeSetなら昇順になる）。きちんとpollメソッドで取得しないといけない。

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        // 1
        Set<Integer> a = new HashSet<>();
        for (int i = 0; i < n; i++) {
            a.add(sc.nextInt());
        }
        Set<Integer> b = new HashSet<>();
        for (int i = 0; i < m; i++) {
            b.add(sc.nextInt());
        }
        sc.close();

        TreeSet<Integer> set = new TreeSet<>(); // 5
        // 2
        for (int i : a) {
            if (!b.contains(i)) {
                set.add(i);
            }
        }
        // 3
        for (int i : b) {
            if (!a.contains(i)) {
                set.add(i);
            }
        }

        StringBuilder sb = new StringBuilder();
        // 4
        for (int i : set) {
            sb.append(i).append(' ');
        }
        if (sb.length() > 0) {
            sb.deleteCharAt(sb.length() - 1);
        }
        System.out.println(sb.toString());
    }
}

ここまで17分02秒＋1ペナ。1854位。

C - Max GCD 2

問題

思考過程

1. 以上以下の範囲に、答えの倍数が複数含まれている必要がある。
2. から（本当はからでよいが）まで全部試し、条件を満たした時点で答えとする。
   　
3. を割った商と、を割った商が、離れていれば満たしそう。
4. ただし、とが共にの倍数の場合は、商の差はでもよい。　→1ケースWA
   　
5. 上記3～4.を捨てて、より確実な判定方法を考える。
6. の倍数となる、以下で最大の値を求め、そこからを引いたものが、としてあり得る最大値。よって、がそれ以下であればOKとする。

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();
        int b = sc.nextInt();
        sc.close();

        for (int i = b; i >= 1; i--) {
            int c = b / i;
            if (i * c - i >= a) {
                System.out.println(i);
                return;
            }
        }
    }
}

ここまで23分34秒＋2ペナ。1207位。

D - Nowhere P

問題
3分足らずで解ける。どうせならこれのFAでも狙ってみたかった。

思考過程

1. は通り全部選べる。
2. 以降は、までの合計にを足した時にの倍数になるものが、必ずだけ存在するため、個から自由に選べる。
3. よって、を求める。

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 p = sc.nextInt();
        sc.close();

        int mod = 1000000007;
        long ans = power(p - 2, n - 1, mod);
        ans *= p - 1;
        ans %= mod;
        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) {
            val = val * x % m;
        }
        return val;
    }
}

ここまで26分17秒＋2ペナ。717位。

E - Level K Palindrome（2021/4/19追記）

問題
解けず。
まず問題は読んだが、すぐに解ける気はせず、順位表を見て先にFから解いた。
時間ギリギリで一応実装終わったので、動作確認の時間もなく残り4秒で投げてみるがRE。
サンプルが通るくらいにはすぐデバッグできたので、4分遅れで再提出してみるが、38/57しか通らず。
これを書いている時に反転を忘れていることに気付いたが、それを直してもあと1ケースWA。

思考過程

1. を回半分にしていくことで（途中で文字列の長さが奇数になったら、中央の文字も控えておく）、元になるレベルの回文に当たる部分を特定できる。
2. 半分にする操作が回できなければ"impossible"。
3. 上記1.の結果が文字の場合、それはレベルの回文たりえないので"impossible"。
   　
4. から抜き出したレベルの回文に当たる部分文字列個、上記1.の操作の過程で控えておいたレベルごとの中央の文字、それぞれを最多出現の文字に変えた場合の操作回数を数える。
5. ただし、最多出現の文字に変えるとレベルの回文に当たる部分が回文になってしまう場合は、どこか箇所を番目に多い文字に変える。何文字目を変えるかは、最多と番目の差が最も小さい箇所。

ということをやろうとしたつもりだったが、あと1ケースは何なのか・・・。

（以下2021/4/19追記）

1. アンサインさんのコメントの通り、上記5.で中央を変える候補から除外する処理の漏れがあったので修正。
2. そもそも上記5.で何故かminではなくmaxを取っていた（つまり、最多と最少の差が最も大きい箇所を変えようとしていた）ので修正。

こんな大ミスしていて1ケースしか落ちなかったのが不思議。2番目に多いのが0個というケースがほとんどだったのかもしれないが。
ちなみに当初1ケース通らないと言っていたのがケースNo.24で、中央を2番目に多い文字に変えていたら落ちるのがNo.57っぽい。
通ったと見せかけて最後の1ケースで落ちるとものすごくがっかりしそう。

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

public class Main {
    static int k;
    static List<String> base;
    static int[][] c;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        k = Integer.parseInt(br.readLine());
        String s = br.readLine();
        br.close();

        c = new int[20][26];
        List<String> ss = new ArrayList<>();
        ss.add(s);
        boolean ok = dfs(0, ss);
        if (!ok) {
            System.out.println("impossible");
            return;
        }
        int end = base.get(0).length(); // レベル0部分の文字列の長さ
        if (end == 1) {
            System.out.println("impossible");
            return;
        }

        int ans = 0;

        // レベル1以上部分で中央になる文字を最多に変える操作回数
        for (int i = 0; i < c.length; i++) {
            int max = 0;
            int sum = 0;
            for (int j = 0; j < 26; j++) {
                max = Math.max(max, c[i][j]);
                sum += c[i][j];
            }
            ans += sum - max;
        }

        int size = base.size(); // レベル0部分の文字列の個数(2^kのはず)
        int[] maxs = new int[end]; // レベル0文字列のi番目の文字の最多
        char[] lv0 = new char[end]; // 全部最多を選んだ時のレベル0文字列
        int[][] cnt = new int[end][26];
        for (int i = 0; i < end; i++) {
            for (String str : base) {
                cnt[i][str.charAt(i) - 'a']++;
            }
            for (int j = 0; j < 26; j++) {
                if (cnt[i][j] > maxs[i]) {
                    maxs[i] = cnt[i][j];
                    lv0[i] = (char) ('a' + j);
                }
            }
        }

        // 全部最多を選んだ時のレベル0文字列が回文になっていないか判定
        // （回文でなければtrue）
        ok = false;
        for (int i = 0; i < end / 2; i++) {
            if (lv0[i] != lv0[end - 1 - i]) {
                ok = true;
                break;
            }
        }
        if (end == 0) {
            ok = true;
        }
        if (!ok) {
            // どこか1箇所を2番目に多い文字（最多との差が最小）に変える
            int min = size;
            for (int i = 0; i < end; i++) {
                // 奇数長の場合の真ん中を変えるのは駄目
                if (end % 2 == 1 && i == end / 2) {
                    continue;
                }
                int ng = lv0[i] - 'a';
                int t = cnt[i][ng];
                for (int j = 0; j < 26; j++) {
                    if (j != ng) {
                        min = Math.min(min, t - cnt[i][j]);
                    }
                }
            }
            ans += min;
        }
        for (int i = 0; i < end; i++) {
            ans += size - maxs[i];
        }
        System.out.println(ans);
    }

    static boolean dfs(int lv, List<String> list) {
        // k回分割していたら終了
        if (lv == k) {
            base = list;
            return true;
        }
        List<String> wk = new ArrayList<>(list.size() * 2);
        int n = list.get(0).length();
        // k回分割できなかった場合
        if (n == 0) {
            return false;
        }
        int n2 = n / 2;
        boolean flg = n2 * 2 != n;
        for (String s : list) {
            // 前半
            wk.add(s.substring(0, n2));
            // 後半の反転
            StringBuilder sb = new StringBuilder(s.substring(n - n2));
            wk.add(sb.reverse().toString());
            // 奇数長の場合
            if (flg) {
                c[lv][s.charAt(n2) - 'a']++;
            }
        }
        return dfs(lv + 1, wk);
    }
}

F - Max Matrix

問題
実装が長ったらしくなってしまったが、奇跡的にバグらず一発で通った。

思考過程

1. 例１の最後のクエリを見て考える。（、から、に変化）
2. この時答えがからへと変化しているが、差分の内訳は、である。（のが回分減り、が回分増え、のが回分減る）
3. 上手いことデータ構造を更新しながら、この差分を求めていきたい。
   　
4. の要素が更新される時の差分を求めるにあたって知りたい情報は、
   • の内、の変更前の値以下である要素の数（上記2.のが何個か）
   • の内、の変更後の値以下である要素の数（上記2.のが何個か）
   • の内、の変更前後の値の間である要素の合計（上記2.の）
5. これは、BITを種類用意すれば管理できそうだが、なので、メモリ制限的にこのサイズのBITはつ用意できるかどうかというところ。
6. 値の種類数はなので、座標圧縮すればBITのサイズを小さくできる。
   　
7. 数を管理するBITについては、変更前の値の座圧後の位置を、変更後の値の座圧後の位置を
   値を管理するBITについては、変更前の値の座圧後の位置を「座圧前の値」、変更後の値の座圧後の位置を「座圧前の値」
   とすることで更新していける。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

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 q = Integer.parseInt(sa[2]);

        int[] t = new int[q];
        int[] x = new int[q];
        int[] y = new int[q];
        for (int i = 0; i < q; i++) {
            sa = br.readLine().split(" ");
            t[i] = Integer.parseInt(sa[0]);
            x[i] = Integer.parseInt(sa[1]) - 1;
            y[i] = Integer.parseInt(sa[2]);
        }
        br.close();

        int[] y2 = zaatu(y);
        // キー：座圧後の値、値：座圧前の値
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 0);
        for (int i = 0; i < q; i++) {
            map.put(y2[i], y[i]);
        }
        int[] a = new int[n];
        int[] b = new int[m];
        FenwickTree ca = new FenwickTree(q + 1); // aの数管理用
        FenwickTree cb = new FenwickTree(q + 1); // bの数管理用
        ca.add(0, n);
        cb.add(0, m);
        FenwickTree va = new FenwickTree(q + 1); // aの値管理用
        FenwickTree vb = new FenwickTree(q + 1); // bの値管理用

        long ans = 0;
        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < q; i++) {
            if (t[i] == 1) {
                int bef = a[x[i]]; // 変更前の値（座圧後）
                int aft = y2[i];   // 変更後の値（座圧後）
                ca.add(bef, -1);
                a[x[i]] = aft;
                ca.add(aft, 1);
                va.add(bef, -map.get(bef));
                va.add(aft, map.get(aft));

                long ubef = cb.sum(bef + 1); // bの内、aのbef以下の要素数
                long uaft = cb.sum(aft + 1); // bの内、aのaft以下の要素数
                long sub = -map.get(bef) * ubef;
                long add = map.get(aft) * uaft;
                ans += sub + add;
                // aの値が大きくなる場合、bで採用されなくなる分を引く
                if (bef < aft) {
                    long oth = vb.sum(bef + 1, aft + 1);
                    ans -= oth;
                }
                // aの値が小さくなる場合、bで採用されるようになる分を足す
                if (bef > aft) {
                    long oth = vb.sum(aft + 1, bef + 1);
                    ans += oth;
                }
            } else {
                // 上の分岐と比べ、aとbを入れ替えただけの内容
                int bef = b[x[i]];
                int aft = y2[i];
                cb.add(bef, -1);
                b[x[i]] = aft;
                cb.add(aft, 1);
                vb.add(bef, -map.get(bef));
                vb.add(aft, map.get(aft));

                long ubef = ca.sum(bef + 1);
                long uaft = ca.sum(aft + 1);
                long sub = -map.get(bef) * ubef;
                long add = map.get(aft) * uaft;
                ans += sub + add;
                if (bef < aft) {
                    long oth = va.sum(bef + 1, aft + 1);
                    ans -= oth;
                }
                if (bef > aft) {
                    long oth = va.sum(aft + 1, bef + 1);
                    ans += oth;
                }
            }
            pw.println(ans);
        }
        pw.flush();
    }

    // 以下ライブラリ

    static int[] zaatu(int[] a) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int i = 0; i < a.length; i++) {
            map.put(a[i], null);
        }
        Integer[] arr = map.keySet().toArray(new Integer[0]);
        int cnt = 0;
        for (Integer i : arr) {
            cnt++;
            map.put(i, cnt);
        }
        int[] b = new int[a.length];
        for (int i = 0; i < a.length; i++) {
            b[i] = map.get(a[i]);
        }
        return b;
    }
}

// 以下ACLを移植したFenwick Tree

提出
ABCDFと解いた時点で75分30秒＋2ペナ。158位。

Gは問題は読んだが全くわからず。解説見たら知らない単語が出てきていたので、知識不足で絶対解けない系だったと思われる。

Hは問題を開いてもいない。

最終結果：ABCDFの5完、85分30秒、235位、パフォーマンス2095相当
レート変動：2011（Unrated）

4完で終わってたらまたパフォ1300弱くらいしか出なかったところだったが、なんとかFを頑張れたおかげでレート相応の結果にはなった。
黄色でA問題にここまでハマる人が他にいるんだろうか。

あとはCにしろEにしろ、駄目だった1ケースが何だったのかは確認しておきたい。