ユニークビジョンプログラミングコンテスト2022(AtCoder Beginner Contest 248)(Rated範囲外)

コンテスト前のレート:2000
(Ratedだとしたら)レート通りのパフォーマンスが得られる順位:328位(2000点、77分29秒)

A - Lacked Number

問題
45から合計を引く方法に全く気付かなかった。。
A問題でfor文を2回も回す?と思ったが最初に思い付いた方法でやることに。

思考過程
  1. 各値の登場回数を保持する配列を生成する。
  2. Sの各文字を調べ、該当する値の登場回数を+1する。
  3. 09を調べ、登場回数が0のものを出力する。
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        char[] s = sc.next().toCharArray();
        sc.close();

        // 1
        int[] a = new int[10];
        // 2
        for (int i = 0; i < s.length; i++) {
            a[s[i] - '0']++;
        }
        // 3
        for (int i = 0; i < 10; i++) {
            if (a[i] == 0) {
                System.out.println(i);
                return;
            }
        }
    }
}

ここまで1分32秒+0ペナ。806位。


B - Slimes

問題

思考過程
  1. A \lt Bの間、K倍と回数カウントを繰り返す。
import java.util.Scanner;

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

        int ans = 0;
        while (a < b) {
            a *= k;
            ans++;
        }
        System.out.println(ans);
    }
}

ここまで2分48秒+0ペナ。465位。


C - Dice Sum

問題
C問題の割には大変なDPが来たと思う。

思考過程
  1. DP[i][j]:=長さiで合計がjとなる通り数」を考える。
  2. 初期値は、長さ0で合計も0となるのが1通り。
  3. 遷移は、長さiで合計jの状態から、i+1番目にj2=1Mを選んだ場合のことを表し、DP[i+1][j+j2]DP[i][j]を加算すればよい。
  4. 計算量は50^4くらいなので大丈夫。
  5. 答えはDP[N][0]DP[N][K]の合計。
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 m = sc.nextInt();
        int k = sc.nextInt();
        sc.close();

        int mod = 998244353;
        int x = n * 50; // x = kでよかった
        int[][] dp = new int[n + 1][x + 1];
        dp[0][0] = 1; // 2
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < x; j++) {
                // 3
                for (int j2 = 1; j2 <= m; j2++) {
                    int next = j + j2;
                    if (next > x) {
                        break;
                    }
                    dp[i + 1][next] += dp[i][j];
                    dp[i + 1][next] %= mod;
                }
            }
        }

        // 5
        long ans = 0;
        for (int i = 0; i <= k; i++) {
            ans += dp[n][i];
        }
        ans %= mod;
        System.out.println(ans);
    }
}

ここまで7分03秒+0ペナ。322位。


D - Range Count Query

問題
難しい。すぐTreeSetを使いたくなる思考が仇になった。
あとMoを使いやすいように整備できていなかった。

思考過程
  1. N種類の値ごとに登場indexを格納したTreeSetを作成し、L_iR_iのsubSetを取得したのでは、該当個数分の計算量がかかってしまう。
    (なお解説を見ると、TreeSetに入れるのではなくListに入れて、二分探索2回でindexの差分を取ればよかった)
     
  2. クエリ先読みすることも考えてみると、比較的最近出てきたばかりのMo's Algorithmが使えそう。
  3. D問題でそんなの求められるわけはないが、他に思い付かないのでそれでやることにする。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.PriorityQueue;
import java.util.function.IntConsumer;

public class Main {
    static int[] cnt;

    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[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(sa[i]);
        }
        int q = Integer.parseInt(br.readLine());
        int[] l = new int[q];
        int[] r = new int[q];
        int[] x = new int[q];
        for (int i = 0; i < q; i++) {
            sa = br.readLine().split(" ");
            l[i] = Integer.parseInt(sa[0]) - 1;
            r[i] = Integer.parseInt(sa[1]);
            x[i] = Integer.parseInt(sa[2]);
        }
        br.close();

        cnt = new int[n + 1];
        Mo mo = new Mo(n, l, r, x,
                i -> {
                    cnt[a[i]]++;
                },
                i -> {
                    cnt[a[i]]--;
                });

        PrintWriter pw = new PrintWriter(System.out);
        for (Mo.Query o : mo.arr) {
            pw.println(o.ans);
        }
        pw.flush();
    }

    // 以下ライブラリ と言いたいところだったが、xに関する部分(★)を修正する羽目になった

    static class Mo {
        int q, d;
        Query[] arr;

        /**
         * クエリ処理(l, rは半開区間)
         * 
         * @param n
         * @param l 左側(含む)(0≦l<n)
         * @param r 右側(含まない)(0<r≦n)
         * @param add 該当indexの要素を追加する処理
         * @param del 該当indexの要素を削除する処理
         */
        public Mo(int n, int[] l, int[] r, int[] x, IntConsumer add, IntConsumer del) { // ★
            q = l.length;
            d = Math.max(1, (int) (n / Math.max(1.0, Math.sqrt(q / 1.5))));
            arr = new Query[q];
            for (int i = 0; i < q; i++) {
                Query o = new Query();
                o.l = l[i];
                o.r = r[i];
                o.x = x[i]; // ★
                o.l2 = o.l / d;
                arr[i] = o;
            }

            PriorityQueue<Query> que = new PriorityQueue<>((o1, o2) -> {
                if (o1.l2 != o2.l2) {
                    return o1.l2 - o2.l2;
                }
                if (o1.l2 % 2 == 0) {
                    return o1.r - o2.r;
                } else {
                    return o2.r - o1.r;
                }
            });
            for (Query o : arr) {
                que.add(o);
            }

            int il = 0;
            int ir = 0;
            while (!que.isEmpty()) {
                Query o = que.poll();
                while (il < o.l) {
                    del.accept(il);
                    il++;
                }
                while (il > o.l) {
                    il--;
                    add.accept(il);
                }
                while (ir < o.r) {
                    add.accept(ir);
                    ir++;
                }
                while (ir > o.r) {
                    ir--;
                    del.accept(ir);
                }
                o.ans = cnt[o.x]; // ★
            }
        }

        class Query {
            int l, r, x, l2, ans; // ★
        }
    }
}

ここまで19分44秒+0ペナ。683位。


E - K-colinear Line

問題

思考過程
  1. K=1の場合は"Infinity"。
  2. _NC_2通りの2点の組み合わせについて傾きを求め、Map<傾き、該当数>で管理しておき、X(X-1)/2=該当数となるXK以上かどうかを調べることをやってしまってから、例1が通らず、傾きが同じでも切片が異なれば異なる直線であることに気付く。
     
  3. では切片の情報もMapのキーに含めるようにすればと思ったが、2点を通る直線の公式を調べたら、単純にやると分数が出てきて現実的ではなさそう。
     
  4. O(N^3)が許される制約なので、_NC_2通り調べる中でさらにもう1つループを回して、同一直線上にある点を全部挙げてしまい、その直線上にある点同士の組み合わせを後でスキップすることを考える。
  5. _NC_2通りの内既に調べた各直線上にある点の集合を保持しておき、その中に存在する2点の組み合わせは調べずにスキップさせてみる。 →計算量がO(N^3)と勘違いしたが実際はO(N^4)のためTLE。
     
  6. 初めに_NC_2通り全部を入れた未調査Setを作り、調べた組み合わせを除いていくようにすることで、調査済みチェック部分をO(N^2)からO(1)にした。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

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

        // 1
        if (k == 1) {
            System.out.println("Infinity");
            return;
        }

        // 6. 未調査Set
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                set.add(i * 1000 + j);
            }
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // 調査済みの組み合わせの場合スキップ
                if (!set.remove(i * 1000 + j)) {
                    continue;
                }
                // 同一直線上の点List
                List<Integer> list = new ArrayList<>();
                list.add(i);
                list.add(j);

                int dx = x[j] - x[i];
                int dy = y[j] - y[i];
                if (dx != 0 && dy != 0) {
                    if (dx < 0) {
                        dx = -dx;
                        dy = -dy;
                    }
                    int g = Math.abs(gcd(dx, dy));
                    dx /= g;
                    dy /= g;
                }

                int cnt = 2;
                // 4. i→jと同一直線上にある他の点を探す
                for (int z = j + 1; z < n; z++) {
                    if (dx == 0) {
                        if (x[z] == x[i]) {
                            cnt++;
                            list.add(z);
                        }
                    } else if (dy == 0) {
                        if (y[z] == y[i]) {
                            cnt++;
                            list.add(z);
                        }
                    } else {
                        int dx2 = x[z] - x[i];
                        int dy2 = y[z] - y[i];
                        if (dx2 != 0 && dy2 != 0) {
                            if (dx2 < 0) {
                                dx2 = -dx2;
                                dy2 = -dy2;
                            }
                            int g = Math.abs(gcd(dx2, dy2));
                            dx2 /= g;
                            dy2 /= g;
                        }
                        // i→zとi→jの傾きが同じ
                        if (dx2 == dx && dy2 == dy) {
                            cnt++;
                            list.add(z);
                        }
                    }
                }
                if (cnt >= k) {
                    ans++;
                }
                // 6. 調べた組み合わせを除く
                for (int a = 0; a < list.size(); a++) {
                    for (int b = a + 1; b < list.size(); b++) {
                        set.remove(list.get(a) * 1000 + list.get(b));
                    }
                }
            }
        }
        System.out.println(ans);
    }

    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

ここまで57分50秒+1ペナ。780位。



F問題はDPをやろうとしたが、例2が合わず。



終結果:ABCDEの5完1500点、62分50秒、878位、パフォーマンス1545相当
レート変動:2000(Unrated)


Dで遅れ始めた辺りからまた今日も駄目か・・・と諦め気味になっていた。
最近のABCは300位前後と800位前後が半々という感じだし、やっぱり今の自分はせいぜいレート1800くらいしかない気がする。