キーエンスプログラミングコンテスト2021-Nov. (AtCoder Beginner Contest 227)(Rated範囲外)

コンテスト前のレート：2018
（Ratedだとしたら）レート通りのパフォーマンスが得られる順位：331位（1000点、20分28秒）

A - Last Card

問題

思考過程

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

        System.out.println((a + k - 2) % n + 1);
    }
}

ここまで2分08秒＋0ペナ。267位。

B - KEYENCE building

問題

思考過程

1. のようなややこしい計算の結果が取れる値とかよくわからないので、全探索が可能か制約を見てみる。
2. の範囲を全探索すると、全体でなので問題なさそう。

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

        int ans = 0;
        for (int i = 0; i < n; i++) {
            boolean flg = false;
            label:
            for (int a = 1; a <= s[i]; a++) {
                for (int b = 1; b <= s[i]; b++) {
                    if (4 * a * b + 3 * a + 3 * b == s[i]) {
                        flg = true;
                        break label;
                    }
                }
            }
            if (!flg) {
                ans++;
            }
        }
        System.out.println(ans);
    }
}

ここまで4分55秒＋0ペナ。165位。

C - ABC conjecture

問題

思考過程

1. を全探索し、各の組に対して可能なの個数を計算で求めることを考える。
2. 計算量はよくわからないが、下記3.がより小さいので、適当に下記4.も同じくらいだとしてまあ大丈夫だろう。
3. 可能なの範囲はからの乗根まで。
4. 可能なの範囲はからまで。
5. 可能なの範囲はからまで。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        sc.close();

        long ans = 0;
        int end = root(n, 3);
        for (int a = 1; a <= end; a++) {
            long bc = n / a;
            int end2 = root(bc, 2);
            for (int b = a; b <= end2; b++) {
                long c = bc / b;
                ans += Math.max(c - b + 1, 0);
            }
        }
        System.out.println(ans);
    }

    // 以下ライブラリ

    // xのn乗根
    static int root(long x, int n) {
        int ng = 1000000001;
        int ok = 1;
        while (ng - ok > 1) {
            int mid = (ok + ng) / 2;
            if (Math.pow(mid, n) < Long.MAX_VALUE) {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        ng = ok + 1;
        ok = 1;
        while (ng - ok > 1) {
            int mid = (ok + ng) / 2;
            if (power(mid, n) <= x) {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        return ok;
    }

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

ここまで11分35秒＋0ペナ。201位。

D - Project Planning

問題

思考過程

1. PriorityQueueを使っての大きい方から順に個取ることを繰り返せればよいが、制約が大きすぎて無理。
2. ある程度効率良くシミュレーション回数を減らせたとしても、とかになりそう。
   　
3. 視点を変えて、まず異なる部署という制約を無視すれば、最大個のプロジェクトを作れる。
4. 異なる部署の制約も加味した時に、上記3.が構築可能かどうかを考える。
   　
5. サンプルを眺めると、例３のようにの内個が大きい場合、どのプロジェクトも部署は固定で残りの部署を部署の中から選ぶ形になり、個の合計が答えになる。
6. 全てのが平均に近い場合はなんとでもなりそう。
7. よって、をソートした後、でよいのではないか。　→ケースWA
   　
8. となるようなケースがあり、駄目だった。
9. 各についてに置き換え、上記7.と同様の計算をする。ということを答えが変わらなくなるまで繰り返してみることにする。
10. 最悪何回繰り返すことになるかは定かではないが、だいたい数回で終わるのではないだろうか。　→とりあえず通ったからヨシ

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));
        String[] sa = br.readLine().split(" ");
        int n = Integer.parseInt(sa[0]);
        int k = Integer.parseInt(sa[1]);
        sa = br.readLine().split(" ");
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = Long.parseLong(sa[i]);
        }
        br.close();

        Arrays.sort(a);
        long[] b = new long[n + 1];
        for (int i = 0; i < n; i++) {
            b[i + 1] = b[i] + a[i];
        }
        long ans = Math.min(b[n] / k, b[n - k + 1]);

        while (true) {
            for (int i = 0; i < n; i++) {
                a[i] = Math.min(ans, a[i]);
            }
            long[] c = new long[n + 1];
            for (int i = 0; i < n; i++) {
                c[i + 1] = c[i] + a[i];
            }
            long ans2 = Math.min(c[n] / k, c[n - k + 1]);
            if (ans == ans2) {
                break;
            }
            ans = ans2;
        }
        System.out.println(ans);
    }
}

ここまで33分52秒＋1ペナ。167位。

Eは何もわからず。
Fも似たような正解者数だったのでFも読み、そちらの方がまだ悪あがきできそうな気がしたのでやる。

F - Treasure Hunting

問題

思考過程

1. 履歴を保持しながらDPをしようとするが（詳細略）、結局上手くいかず捨てる。
   　
2. 経路内の大きい方から個目の値がいくつであるかを決め打てば、行目列目までで決め打った値以上のマスを個通っている場合の答え」ができそう。
3. 値の決め打ちといえば二分探索と思い、「経路内に以上の値が個以上あるような最大の」を求めようとするが、例２がになってしまい、は調べられてすらいない。
   　
4. 二分探索するより、に登場する値を調べるのが正しそう。だがこれでもまだになる。
5. デバッグすると、が個入っているせいだったことが判明。
6. 決め打った値とイコールの場合、大きい値の場合と小さい値の場合両方の遷移を行うように修正する。

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int h = sc.nextInt();
        int w = sc.nextInt();
        int k = sc.nextInt();
        List<Integer> list = new ArrayList<>();
        int[][] a = new int[h][w];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                a[i][j] = sc.nextInt();
                list.add(a[i][j]);
            }
        }
        sc.close();

        int hw = h + w;
        long inf = 1000000000000000000L;
        long ans = inf;
        for (int e : list) {
            long[][][] dp = new long[h][w][hw + 1];
            for (int x = 0; x < h; x++) {
                for (int y = 0; y < w; y++) {
                    for (int z = 0; z <= hw; z++) {
                        dp[x][y][z] = inf;
                    }
                }
            }
            if (a[0][0] >= e) {
                dp[0][0][1] = a[0][0];
            } else {
                dp[0][0][0] = 0;
            }
            for (int x = 0; x < h; x++) {
                for (int y = 0; y < w; y++) {
                    if (a[x][y] <= e) {
                        if (x > 0) {
                            for (int z = 0; z <= hw; z++) {
                                dp[x][y][z] = Math.min(dp[x][y][z], dp[x - 1][y][z]);
                            }
                        }
                        if (y > 0) {
                            for (int z = 0; z <= hw; z++) {
                                dp[x][y][z] = Math.min(dp[x][y][z], dp[x][y - 1][z]);
                            }
                        }
                    }
                    if (a[x][y] >= e) {
                        if (x > 0) {
                            for (int z = 1; z <= hw; z++) {
                                dp[x][y][z] = Math.min(dp[x][y][z], dp[x - 1][y][z - 1] + a[x][y]);
                            }
                        }
                        if (y > 0) {
                            for (int z = 1; z <= hw; z++) {
                                dp[x][y][z] = Math.min(dp[x][y][z], dp[x][y - 1][z - 1] + a[x][y]);
                            }
                        }
                    }
                }
            }
            if (dp[h - 1][w - 1][k] < inf) {
                ans = Math.min(ans, dp[h - 1][w - 1][k]);
            }
        }
        System.out.println(ans);
    }
}

ここまで88分27秒＋1ペナ。201位。

順位表を見るとE、FよりGの方が解かれていたが、残り時間が少なく問題見てすぐにわかるなんてこともなく終了。

最終結果：ABCDFの5完1500点、93分27秒、225位、パフォーマンス2187相当
レート変動：2018（Unrated）

ABC5回連続300位以内で、最近はまあまあ安定している感じ。
思考過程がだいぶ怪しかった問題もあるけど。