エイシング プログラミング コンテスト 2020

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

A - Number of Multiples

問題
この手の問題は2通りの解法を思いつくけど、思考停止でできる方でやる。

思考過程

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

        int ans = 0;
        for (int i = l; i <= r; i++) {
            if (i % d == 0) {
                ans++;
            }
        }
        System.out.println(ans);
    }
}

ここまで1分05秒＋0ペナ。690位。

B - An Odd Problem

問題
やっぱりB問題のdifficultyは100～200くらいはあってほしいと思う。

思考過程

1. マス数分ループを回して、各マスが条件を満たすか判定する。
2. 「番号が奇数」の条件は、0-indexedのループカウンタが偶数の場合に満たしているとする。

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[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        sc.close();

        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0 && a[i] % 2 == 1) {
                ans++;
            }
        }
        System.out.println(ans);
    }
}

ここまで2分20秒＋0ペナ。436位。

C - XYZ Triplets

問題
余計なことして実装に手間をかけてしまったらしい。
とりあえずとしてみると数えやすいと思ってしまったところから抜け出せなかった。実際は思考過程5.以降は不要。

思考過程

1. がとなる個数を、適切なの範囲で全探索する。というのを～の回やるのは間に合わなそう？
2. 各について毎回全探索するのではなく、全探索で上記の式を計算する度に、計算結果をとしてをインクリメントしていけば、実質の時の全探索回だけで済む。
3. の探索範囲は、としたときなので、まででよい。
4. 計算結果となった場合、それより大きいで以下にはならないので、次のの探索に進む。
5. とすると、をの並び替えの通り数だけ加算すればよい。
6. が全て異なるなら通り、つ異なるなら通り、全て同じなら通り。

import java.io.PrintWriter;
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();
        sc.close();

        int[] ans = new int[n + 1];
        int n2 = (int) Math.sqrt(n);
        for (int x = 1; x <= n2; x++) {
            for (int y = x; y <= n2; y++) {
                for (int z = y; z <= n2; z++) {
                    int v = x*x + y*y + z*z + x*y + y*z + z*x;
                    if (v > n) {
                        break;
                    }
                    int cnt = 0;
                    if (x == y) {
                        cnt++;
                    }
                    if (y == z) {
                        cnt++;
                    }
                    if (cnt == 0) {
                        ans[v] += 6;
                    } else if (cnt == 1) {
                        ans[v] += 3;
                    } else {
                        ans[v]++;
                    }
                }
            }
        }

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 1; i <= n; i++) {
            pw.println(ans[i]);
        }
        pw.flush();
    }
}

ここまで9分47秒＋0ペナ。832位。

D - Anything Goes to Zero

問題
サンプルが通らないものを提出して1ペナ余計に増やしてしまった。
どうして2回目の提出時に例２しか試さなかったのか。

思考過程

1. →→のように、各を始点としたグラフを作ることをイメージしてみると、から回遷移した先は以下になる。
2. とりあえず～について、として前計算しておいてみる。（実際は、以下くらい→以下くらい→以下くらいと一気に減るので、毎回計算しても問題ない。）
   　
3. からを求めて最初の遷移を行うまでを、BigIntegerを使って愚直に計算して大丈夫か？と思ったりするが、計算量に自信がないので使わない方法を考えることにする。　→後で一応やってみたけどやっぱりTLE
4. は、のどちらかであるため、まずはとを求めておく。
   　
5. 左から桁目が（に変える）の場合、を足す。
6. 左から桁目が（に変える）の場合、を引く。
7. 上記5. 6.の遷移先からまでの遷移回数（前計算済み）にを足せば答え。　→5ケースRE
8. がになる場合に除算が発生していた。
9. そのような場合はとしておき、の場合はを出力する。　→例１のみWA
10. 除算ではなく計算した結果となる場合もあるので、ちゃんとの場合にを出力するようにする。　→AC

import java.io.PrintWriter;
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();
        char[] x = sc.next().toCharArray();
        sc.close();

        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (x[i] == '1') {
                cnt++;
            }
        }
        int p0 = cnt + 1;
        int p1 = cnt - 1;
        // 思考過程2
        int[] dp = new int[n];
        for (int i = 1; i < n; i++) {
            int next = i % Integer.bitCount(i);
            dp[i] = dp[next] + 1;
        }

        // 思考過程4
        long v0 = 0;
        for (int i = 0; i < n; i++) {
            v0 *= 2;
            v0 %= p0;
            if (x[i] == '1') {
                v0++;
            }
        }
        v0 %= p0;

        // 思考過程4
        long v1 = 0;
        if (p1 > 0) { // 0除算回避
            for (int i = 0; i < n; i++) {
                v1 *= 2;
                v1 %= p1;
                if (x[i] == '1') {
                    v1++;
                }
            }
            v1 %= p1;
        }

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < n; i++) {
            if (x[i] == '0') {
                long a = power(2, n - 1 - i, p0);
                long val = v0 + a; // 思考過程5
                int next = (int) (val % p0);
                pw.println(dp[next] + 1); // 思考過程7
            } else {
                if (p1 == 0) { // 思考過程10
                    pw.println(0);
                } else {
                    long a = power(2, n - 1 - i, p1);
                    long val = v1 - a + p1; // 思考過程6
                    int next = (int) (val % p1);
                    pw.println(dp[next] + 1); // 思考過程7
                }
            }
        }
        pw.flush();
    }

    // 以下ライブラリ

    // x^n % m
    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;
    }
}

ここまで35分25秒＋2ペナ。296位。
ここまでの4完で終わっていたとしても、レートはぎりぎりプラスであった。

E - Camel Train

問題
今度はサンプルと出力が異なっているのに気付かずに提出して余計な1ペナを増やした。
それから、実装を手抜いたせいで余計な1ペナを増やした。（駄目なことに気付いていなかったのもあるが、そもそも駄目かどうか考えずに済む実装をしなかった。）

思考過程

1. 以下か超か、適切な位置に置けたらの大きい方、置けなければ小さい方を足すことになるので、その差が大きいラクダの位置を優先的に決めていきたい。
2. の絶対値の降順に見ていき、の場合は以下で最大の位置に、の場合は超で最小の位置に置くようにしていく。置ければ大きい方、置けなければ小さい方を足す。　→サンプルの2、3ケース目はACだが1ケース目はWA、他も全てWA
   　
3. 全ラクダがならばなるべく後ろに置こうとして問題ないが、後ろに置きすぎると後ろに置きたいラクダの邪魔になってしまうことがある。
4. 「なるべく後ろに置こうとする」の上限を全探索？　それはさすがに最低でもになって時間がアウトっぽいし、全ラクダで同じ上限でいいのかどうか、正当性も怪しい。
   　
5. 差のことを一旦忘れ、置きたいところに置けるラクダの数を最大化することを考えると、左に寄せたい中ではの昇順、右に寄せたい中ではの降順に処理し、端から貪欲に埋めていくのが最適。
6. 左側について見ると、ラクダを置こうとした際、～が全て埋まっていたらNG（の大きい方を取れない）となるが、既に埋めている中でが最小のものを代わりにNGにすることで、後からがより大きいものをOK（の大きい方を取れる）とすることができる。
7. 右側の場合は逆。の場合はによらずOKとしておく。
8. 左右から貪欲を行っても、位置決めの試行回数が合計以下のため、競合はしない。
   　
9. 上記2.の時の名残で、TreeSetを使っていたままだったが、何故か要素が重複することはないだろうと思い込む。　→サンプル以外全てWA（この実装ではが重複するとアウト）
10. 普通に重複要素あり得るので、TreeSetをPriorityQueueに変更する。　→まだ6ケースしか通らず13ケースWA
    　
11. 上記6.で、代わりにNGにするものを選ぶ際、実際には位置を決めていないのものを選んでしまう可能性があった。はOKではなく別の集合に入れるようにする。（以下の実装では別の集合を新たに用意しているが、大きい方でも小さい方でも同じなのでNGに入れればよかった。）

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        int t = Integer.parseInt(br.readLine());
        for (int x = 0; x < t; x++) {
            int n = Integer.parseInt(br.readLine());
            Obj[] arr = new Obj[n];
            for (int i = 0; i < n; i++) {
                String[] sa = br.readLine().split(" ");
                Obj o = new Obj();
                o.k = Integer.parseInt(sa[0]);
                o.l = Integer.parseInt(sa[1]);
                o.r = Integer.parseInt(sa[2]);
                o.d = Math.abs(o.l - o.r);
                arr[i] = o;
            }
            Arrays.sort(arr, (o1, o2) -> o1.k - o2.k); // Kの昇順

            long ans = 0;
            Queue<Obj> fix = new ArrayDeque<>();
            PriorityQueue<Obj> ok = new PriorityQueue<>((o1, o2) -> o1.d - o2.d);
            Queue<Obj> ng = new ArrayDeque<>();
            int used = 0;
            for (int i = 0; i < n; i++) { // 左から貪欲
                Obj o = arr[i];
                if (o.l == o.r) {
                    fix.add(o); // 思考過程11
                } else if (o.l > o.r) {
                    if (o.k > used) {
                        // 置き場所が残っている場合
                        ok.add(o);
                        used++;
                    } else {
                        // 置き場所が残っていない場合
                        Obj f = ok.peek();
                        if (o.d > f.d) {
                            // 差がより小さいものがいたら入れ替え
                            ng.add(ok.poll());
                            ok.add(o);
                        } else {
                            ng.add(o);
                        }
                    }
                }
            }

            PriorityQueue<Obj> ok2 = new PriorityQueue<>((o1, o2) -> o1.d - o2.d);
            Queue<Obj> ng2 = new ArrayDeque<>();
            used = n;
            for (int i = n - 1; i >= 0; i--) { // 右から貪欲
                Obj o = arr[i];
                if (o.l < o.r) {
                    if (o.k < used) {
                        // 置き場所が残っている場合
                        ok2.add(o);
                        used--;
                    } else {
                        // 置き場所が残っていない場合
                        // ※K=Nの場合、誰も埋めてなくても置けないので空チェック
                        if (!ok2.isEmpty() && o.d > ok2.peek().d) {
                            // 差がより小さいものがいたら入れ替え
                            ng2.add(ok2.poll());
                            ok2.add(o);
                        } else {
                            ng2.add(o);
                        }
                    }
                }
            }
            // L=Rのもの、OKのものは大きい方
            for (Obj o : fix) {
                ans += Math.max(o.l, o.r);
            }
            for (Obj o : ok) {
                ans += Math.max(o.l, o.r);
            }
            for (Obj o : ok2) {
                ans += Math.max(o.l, o.r);
            }
            // NGのものは小さい方
            for (Obj o : ng) {
                ans += Math.min(o.l, o.r);
            }
            for (Obj o : ng2) {
                ans += Math.min(o.l, o.r);
            }
            pw.println(ans);
        }
        br.close();
        pw.flush();
    }

    static class Obj {
        int k, l, r, d;
    }
}

ここまで79分16秒＋5ペナ。152位。

F - Two Snuke

問題
E問題の初回WA（48分）時点で一度問題は見たのだが、全く解ける気がしなかったので、残り時間を全部E問題に使うことを決めていた。
20分残して戻ってこられたが、やっぱり解けず。

思考過程

1. 各添え字のつは以上である必要があるため、添え字のつに個ずつは固定。残りの最大個をつに自由に分配することを考えてみる。
2. これは重複組み合わせであり、どこにも分配しないとするつ目の場所も作ると、仕切りがつとなり、全部で通りの分け方がある。
3. しかし、各分け方で差の積が同じわけでもなく、上手く差の積が同じパターンを集めてまとめて数えるとかもできる気がしない。

最終結果：ABCDEの5完、104分16秒、238位、パフォーマンス2129
レート変動：1762→1805

今回はとにかくペナルティがもったいない。3回は減らせたはずで、その場合パフォ2250くらいだったかもしれない。

それにしても、最近パフォーマンスのブレが激しい。上にもブレてるのが救いだが。
パフォ青以外Streakが、初めて青パフォ出した2019/4/20（当時レート1125）以来で最長の5となった。（水色になる直前の頃まで遡っても、5回に1回以上は青パフォを出せているのに、最近出ない。）
なお、青パフォLongest Streakは7であり、非常に安定していた時期もあった。