鹿島建設プログラミングコンテスト2020（AtCoder Regular Contest 110）

コンテスト前のレート：1766
レート通りのパフォーマンスが得られる順位：551位（1200点、51分22秒）

A - Redundant Redundancy

問題

思考過程

1. どれで割っても余る数は、どれで割っても割り切れる数と同じこと。
2. ～の最小公倍数を求めてを足す。
3. の場合に以下に収まっていることを確認して提出。

import java.math.BigInteger;
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();

        long ans = 1;
        for (int i = 2; i <= n; i++) {
            ans = lcm(ans, i);
        }
        System.out.println(ans + 1);
    }

    // 以下ライブラリ

    static long lcm(long a, long b) {
        BigInteger ba = BigInteger.valueOf(a);
        BigInteger bb = BigInteger.valueOf(b);
        return ba.multiply(bb).divide(ba.gcd(bb)).longValue();
    }
}

ここまで1分35秒＋0ペナ。56位。

B - Many 110

問題
結構時間かかってしまったし、公式解説と比べると、以下の思考過程は遠回りしていて無理矢理帳尻合わせしている感じ。

思考過程

1. サンプルを見た感じでは、からに含まれる”110”の数を引いて、したくらい。
2. が"1"の場合は。まとめて処理しにくそうなので、まずこれだけ場合分けしてみる。
   　
3. は、"xx110110...110yy"という形をしているので、途中"110"が何回続いたかを数えつつ、最初と最後の部分だけを抜き出す。
4. 最初の"xx"の部分は"0"か"10"かしかないので、その部分を取り除いて"110"から始まるようにして処理することにする。
5. がに含まれるならば、最初と最後の"xxyy"の部分は"110110"に含まれるはず（"1011"でよかったかもしれない）。これを満たさない場合は。
   　
6. "xx"と"yy"が共に空文字列ではない場合は、サンプルのように。
7. そうでなければ自由度が増えるので？　→思考過程3の実装にバグがありWA。直してもまだ3ケースWA。
8. "xx"と"yy"が共に空文字列の場合は、自由度でだった。

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();
        String t = sc.next();
        sc.close();

        long mx = 10000000000L;
        // 思考過程2
        if (t.equals("1")) {
            System.out.println(2 * mx);
            return;
        }

        // 思考過程4
        StringBuilder sb = new StringBuilder();
        if (t.startsWith("01")) {
            sb.append("0");
            t = t.substring(1);
        } else if (t.startsWith("101")) {
            sb.append("10");
            t = t.substring(2);
        }

        // 思考過程5
        int cnt = 0;
        char[] ct = t.toCharArray();
        for (int i = 0; i < ct.length - 2; i+=3) {
            if (ct[i] == '1' && ct[i + 1] == '1' && ct[i + 2] == '0') {
                cnt++;
            } else {
                break;
            }
        }
        for (int i = cnt * 3; i < ct.length; i++) {
            sb.append(ct[i]);
        }
        String x = sb.toString();
        if ("110110".indexOf(x) == -1) {
            System.out.println(0);
            return;
        }

        mx -= cnt;
        if ("110".indexOf(x) == -1) {
            System.out.println(mx - 1);
        } else if (x.equals("")) { // 思考過程8
            System.out.println(mx + 1);
        } else {
            System.out.println(mx);
        }
    }
}

ここまで26分14秒＋2ペナ。635位。

C - Exoswap

問題

思考過程

1. まずはとを両端に持っていこうとしてみる。
2. その場合、から左端までの間と、から右端までの間を順に回ずつ選ぶ以外に方法はない。
3. を左端に移動させた時点で、元々があった場所をとするならば、～までが揃っている必要があり、次はをどこか右の方からまで動かしてきてと続けていくことができる。
4. 実装上は、から順に処理していき、既に操作している位置を再度使う必要が生じた時点で-1とする。　→19ケースWA
5. 箇所全て使っているかの確認が漏れていた。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.LinkedHashSet;

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

        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[p[i]] = i;
        }

        LinkedHashSet<Integer> set = new LinkedHashSet<>();
        for (int i = 0; i < n; i++) {
            for (int j = a[i]; j > i; j--) {
                if (set.contains(j)) {
                    System.out.println(-1);
                    return;
                }
                set.add(j);
                int pl = p[j - 1];
                int pr = p[j];
                a[pl]++;
                a[pr]--;
                p[j - 1] = pr;
                p[j] = pl;
            }
        }
        // 思考過程5
        if (set.size() != n - 1) {
            System.out.println(-1);
            return;
        }

        PrintWriter pw = new PrintWriter(System.out);
        for (int i : set) {
            pw.println(i);
        }
        pw.flush();
    }
}

ここまで40分54秒＋1ペナ。375位。

F - Esoswap

問題
D問題は数学色が強そうでよくわからず。
E問題は簡単なDPをしてみたが、重複カウントが出ていそうで、排除方法が全く見当もつかず。

なんとなくこのF問題をこねくり回していたら1つの方法を思いつき、証明できなかったが駄目元で投げてみたら通ってしまった。
正当性は不明。
思考過程3のところで、同じ状態のループにならない保証があるのかわからないがどうなのか・・・。

思考過程

1. 整数が位置に移動するときの最後の手を考えると、以下のいずれかしかない。
   • 位置に整数が存在して位置に整数が存在する状態でを宣言する
   • 位置に整数が存在する状態でを宣言する。
2. 簡単なのは後者なので、例１や、他の適当な程度の数列を手で動かしてみて、を宣言し続けた場合にどうなるかを見てみる。
3. 昇順になりきらずに先頭がになってしまう場合もあるが、となっていないところを適当に動かせば、その内でなくなりそう。
4. 結局、数列を前から見ていって最初にとなった場所を宣言し続けるだけ。（ほとんどの場合は先頭になる想定）
5. 上限を超えても昇順にできていなかったら-1を出力する処理を一応付け足しておく。

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

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

        int mx = 200000;
        List<Integer> list = new ArrayList<>();
        while (list.size() <= mx) {
            boolean flg = true;
            for (int i = 0; i < n; i++) {
                if (p[i] != i) {
                    flg = false;
                    list.add(i);
                    int j = (i + p[i]) % n;
                    int t = p[i];
                    p[i] = p[j];
                    p[j] = t;
                    break;
                }
            }
            if (flg) {
                break;
            }
        }
        if (list.size() > mx) {
            System.out.println(-1);
        } else {
            PrintWriter pw = new PrintWriter(System.out);
            pw.println(list.size());
            for (int i : list) {
                pw.println(i);
            }
            pw.flush();
        }
    }
}

ABCFと通した時点で104分48秒＋3ペナ。63位。

残り15分でD問題を少し考えるふりをするが、既に望外の結果なので順位表を眺めていた。

最終結果：ABCFの4完、119分48秒、78位、パフォーマンス2600
レート変動：1766→1882（+116）

まぐれ一発大当たりで、初の橙パフォが出てHighestも62も更新。
最高パフォも300近く更新しているし、本番中に解けたDifficultyの最高も先週2251→2394に上がったばかりなのに今回さらに2719に。
1年に1回あればいい方くらいの大成功だったかと。

まあ実力が伴っているわけではないので、レートはまたすぐ下がると思う。
なんとか1800維持できないものかな・・・。

ここ2ヶ月のレート急落は、まともに新しいことを覚えていない上に、これまでにやってきた問題を徐々に忘れてできなくなってきていることに原因があると見て、最近は可能な限りくじかつをやるようにしている。
これで大失敗を減らした上で、前回や今回のようにたまに大成功を出せたらいいなというところ。