トヨタシステムズプログラミングコンテスト2021(AtCoder Beginner Contest 228)(Rated範囲外)

コンテスト前のレート:2018
(Ratedだとしたら)レート通りのパフォーマンスが得られる順位:342位(1500点、66分02秒)

A - On and Off

問題
実際は、下記思考過程2の方は少し迷走していた。

思考過程
  1. S \lt Tの場合、S \leq X \lt Tなら"Yes"。
  2. S \gt Tの場合、T \leq X \lt Sなら"No"。
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int s = sc.nextInt();
        int t = sc.nextInt();
        int x = sc.nextInt();
        sc.close();

        if (s < t) {
            if (s <= x && x < t) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        } else {
            if (t <= x && x < s) {
                System.out.println("No");
            } else {
                System.out.println("Yes");
            }
        }
    }
}

ここまで2分11秒+0ペナ。90位。


B - Takahashi's Secret

問題

思考過程
  1. Xから初めて既に知っている人に当たるまで、カウントしながら辿っていく。
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 x = sc.nextInt() - 1;
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt() - 1;
        }
        sc.close();

        int ans = 1;
        boolean[] b = new boolean[n];
        b[x] = true;
        while (true) {
            x = a[x];
            if (b[x]) {
                break;
            }
            b[x] = true;
            ans++;
        }
        System.out.println(ans);
    }
}

ここまで4分38秒+0ペナ。97位。


C - Final Day

問題

思考過程
  1. ある生徒については、自分は4日目に300点を取って他全員0点を取った場合が最高順位となる。
  2. よって、3日目までの合計+300が、3日目時点でのK位の点数以上となれば"Yes"。同率を考慮しても同様。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Collections;
import java.util.PriorityQueue;

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]);
        // 3日目までの合計点
        int[] a = new int[n];
        PriorityQueue<Integer> que = new PriorityQueue<>(Collections.reverseOrder());
        for (int i = 0; i < n; i++) {
            sa = br.readLine().split(" ");
            for (int j = 0; j < 3; j++) {
                int p = Integer.parseInt(sa[j]);
                a[i] += p;
            }
            que.add(a[i]);
        }
        br.close();

        for (int i = 0; i < k - 1; i++) {
            que.poll();
        }
        int b = que.poll(); // 3日目時点でのK位の点数

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < n; i++) {
            if (a[i] + 300 >= b) {
                pw.println("Yes");
            } else {
                pw.println("No");
            }
        }
        pw.flush();
    }
}

ここまで10分03秒+0ペナ。105位。


D - Linear Probing

問題
問題の理解に時間がかかった。
でも公式解説よりも簡単な解法で解けていそう。

思考過程
  1. インデックス0(N-1)の内まだ値を設定していない箇所に値を設定できる。
  2. 値を設定する箇所は、基本的にx \% Nだが、既に設定されている場合は設定されていない箇所が見つかるまで1つ右を探し続ける。
  3. 一瞬無限ループするのではと思ったが、Q \lt Nなので全部埋まることはない。
     
  4. 愚直に探していくとO(Q^2)となってしまう。
  5. x \% N以上で最小の未設定箇所が高速にわかればよい。
  6. 0(N-1)を全部TreeSetに入れておいて、使ったところを消していくようにすれば、ceilingを使うだけで求まる。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int q = Integer.parseInt(br.readLine());
        int n = 1 << 20;
        TreeSet<Integer> set = new TreeSet<>();
        for (int i = 0; i < n; i++) {
            set.add(i);
        }
        long[] a = new long[n];
        Arrays.fill(a, -1);

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < q; i++) {
            String[] sa = br.readLine().split(" ");
            int t = Integer.parseInt(sa[0]);
            long x = Long.parseLong(sa[1]);
            int idx = (int) (x % n);
            if (t == 1) {
                Integer e = set.ceiling(idx);
                if (e == null) {
                    e = set.ceiling(0);
                }
                set.remove(e);
                a[e] = x;
            } else {
                pw.println(a[idx]);
            }
        }
        pw.flush();
        br.close();
    }
}

ここまで20分01秒+0ペナ。89位。



Eは滅茶苦茶簡単では?と初回提出まで3分だったが、半分ほど通らず。 その後制約がmodよりも大きいことが本質か?と思い、途中までmodを4乗した値で計算してみたりといった見当違いのことをしていた。

40分ほどでEを捨てて、あとはFに30分、Gに10分くらい使ったがいずれも解けず。



終結果:ABCDの4完1000点、20分01秒、861位、パフォーマンス1525相当
レート変動:2018(Unrated)


逆元をP-2乗で求めるなんて意識を持ったことがないせいで、A^{P-1} \equiv 1 (mod P)という考えが全然出てこないことに気付かされた。
これができなかったのはさすがに反省。

F以降は今ある知識的にできなくて当然の内容だったのでよしとする。