AtCoder Regular Contest 149

コンテスト前のレート：2023
レート通りのパフォーマンスが得られる順位：364位（1300点、62分49秒）

まさかのA問題が解けず。
1～9それぞれについて、longに収まる1～18桁の値を作ってで割れたらあとは以下で最大の桁数を計算するとかをしていた。
WAだったのでBigIntegerを使って桁まで全部調べたりしていたが、がくらいまでしか間に合いそうにない。

20分ほどで一旦諦めてとりあえずBへ。

B - Two LIS Sum

問題
着手した頃にはこの問題も既に解かれまくっていた。

思考過程

1. でソートしてみたらどうだろうか。　→例１も合わない。
2. とりあえずでソートしてから、側をより良くする方法を考えてみる。
3. ソート後のを適切な位置に動かすことを考えると、側のLISが減って、側のLISを高々しか増やせないので、動かす意味がない。
4. 結局でソートした後側のLISを求めればよさそう。正解者数的にもこんなもんだろう。

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

        Arrays.sort(arr, (o1, o2) -> o1.a - o2.a);

        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE;
        }

        for (int i = 0; i < n; i++) {
            int idx = Arrays.binarySearch(dp, arr[i].b);
            if (idx < 0) idx = ~idx;
            dp[idx] = arr[i].b;
        }

        int lis = Arrays.binarySearch(dp, Integer.MAX_VALUE - 1);
        if (lis < 0) {
            lis = ~lis;
            lis--;
        }

        System.out.println(n + lis);
    }

    static class Obj {
        int a, b;
    }
}

Bを解いた時点で35分33秒＋0ペナ。891位。

C - Avoid Prime Sum

問題

思考過程

1. 偶数同士、奇数同士であればの倍数になるため、上半分を偶数、下半分を奇数で埋めることを基本形とする。
2. 境界部分だけ偶数奇数で素数にならない組み合わせを置く必要がある。
3. これは（奇数の場合）からずつ引いていって、を足して合成数になる最初の値を見つけると、あとはのように合計が同じ値になるペアを作れることになる。
   　
4. が偶数の時はきれいに半分ずつに分けられ、境界も一直線なのでここまでの方法だけでいけそう。
5. 奇数の時は中央の行が個と個に分かれることになり、偶数と奇数それぞれ個ずつはつの値と接することになる。
   　
6. 下図のように、とペアにできる偶数をの他にもうつも探し、を元に奇数を求める。
7. あとは以外で残りの境界を埋める。
8. が最悪どれくらい小さくなるかはきちんと検証していないが、の時はのペアがつ存在せず駄目なので埋め込み、～を出力してみて問題なさそうで、がそれより大きくて問題あることはないだろうと判断する。

.....
..x..
.y1..
.z...
.....

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());
        br.close();

        if (n == 3) {
            System.out.println("4 2 6");
            System.out.println("8 7 3");
            System.out.println("1 5 9");
            return;
        }

        int nn = n * n;
        int[][] a = new int[n][n];
        int start = nn;
        if (start % 2 == 1) {
            start--;
        }
        int x = 0;
        for (int i = start; i > 0; i -= 2) {
            if (!isSosuu(i + 1)) {
                x = i;
                break;
            }
        }

        int n2 = n / 2;
        int a1 = 1;
        int a2 = x;
        if (n % 2 == 0) {
            // 下半分を奇数
            for (int i = n2; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    a[i][j] = a1;
                    a1 += 2;
                }
            }
            // 境界部分の偶数
            for (int j = 0; j < n; j++) {
                a[n2 - 1][j] = a2;
                a2 -= 2;
                if (a2 < 2) {
                    a2 = start;
                }
            }
            // 上半分の残りを偶数
            for (int i = 0; i < n2 - 1; i++) {
                for (int j = 0; j < n; j++) {
                    a[i][j] = a2;
                    a2 -= 2;
                    if (a2 < 2) {
                        a2 = start;
                    }
                }
            }
        } else {
            int y = 0;
            for (int i = x - 2; i > 0; i -= 2) {
                if (!isSosuu(i + 1)) {
                    y = i;
                    break;
                }
            }
            int z = x + 1 - y;

            a[n2][n2] = 1;
            a[n2 - 1][n2] = x;
            a[n2][n2 - 1] = y;
            a[n2 + 1][n2 - 1] = z;
            a1 = nexta1(a1, z);
            a2 = nexta2(a2, y, start);
            // 1, xより右の境界部分
            for (int i = n2 + 1; i < n; i++) {
                a[n2 - 1][i] = a2;
                a[n2][i] = a1;
                a1 = nexta1(a1, z);
                a2 = nexta2(a2, y, start);
            }
            // z, yより左の境界部分
            for (int i = 0; i < n2 - 1; i++) {
                a[n2][i] = a2;
                a[n2 + 1][i] = a1;
                a1 = nexta1(a1, z);
                a2 = nexta2(a2, y, start);
            }

            // zより右の部分を奇数
            for (int i = n2; i < n; i++) {
                a[n2 + 1][i] = a1;
                a1 = nexta1(a1, z);
            }
            // 下半分の残りを奇数
            for (int i = n2 + 2; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    a[i][j] = a1;
                    a1 = nexta1(a1, z);
                }
            }

            // xより左の部分を偶数
            for (int i = 0; i < n2; i++) {
                a[n2 - 1][i] = a2;
                a2 = nexta2(a2, y, start);
            }
            // 上半分の残りを偶数
            for (int i = 0; i < n2 - 1; i++) {
                for (int j = 0; j < n; j++) {
                    a[i][j] = a2;
                    a2 = nexta2(a2, y, start);
                }
            }
        }

        for (int i = 0; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; j++) {
                sb.append(a[i][j]).append(' ');
            }
            sb.deleteCharAt(sb.length() - 1);
            System.out.println(sb.toString());
        }
    }

    static int nexta1(int a1, int z) {
        a1 += 2;
        if (a1 == z) {
            a1 += 2;
        }
        return a1;
    }

    static int nexta2(int a2, int y, int start) {
        a2 -= 2;
        if (a2 < 2) {
            a2 = start;
        }
        if (a2 == y) {
            a2 -= 2;
            if (a2 < 2) {
                a2 = start;
            }
        }
        return a2;
    }

    // 以下ライブラリ

    static boolean isSosuu(long n) {
        if (n < 2) return false;
        if (n == 2) return true;
        long end = (int) Math.sqrt(n) + 1;
        for (int i = 2; i <= end; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
}

BCと解いた時点で69分25秒＋0ペナ。508位。

Aを解いても青パフォに届くかどうかくらいで爆死に変わりなさそうだったので、DとEを両方見てDを頑張ることにする。
がやっぱり解けず。

怪しげなBFSっぽい方法で答えがYesになる位置であれば求められた気がしたが（合っているかは知らん）、それだと答えがNoのところがNoとしかわからなかった。

最終結果：BCの2完1000点、69分25秒、911位、パフォーマンス1442
レート変動：2023→1977（-46）

ここのところレートが乱高下している。
一気に2038まで回復してしばらくは大丈夫だと思っていたのに、たった2回でまた青とは。

Aは何で全桁揃ってからじゃないとmod取れないと思ってしまったのか・・・。
ノルマと照らし合わせると、Aは15分以内には解けないと駄目そう。