トヨタシステムズプログラミングコンテスト2021(AtCoder Beginner Contest 228)(Rated範囲外)
コンテスト前のレート:2018
(Ratedだとしたら)レート通りのパフォーマンスが得られる順位:342位(1500点、66分02秒)
A - On and Off
問題
実際は、下記思考過程2の方は少し迷走していた。
思考過程
- の場合、なら"Yes"。
- の場合、なら"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
思考過程
- から初めて既に知っている人に当たるまで、カウントしながら辿っていく。
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
思考過程
- ある生徒については、自分は日目に点を取って他全員点を取った場合が最高順位となる。
- よって、日目までの合計が、日目時点での位の点数以上となれば"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
問題
問題の理解に時間がかかった。
でも公式解説よりも簡単な解法で解けていそう。
思考過程
- インデックス~の内まだ値を設定していない箇所に値を設定できる。
- 値を設定する箇所は、基本的にだが、既に設定されている場合は設定されていない箇所が見つかるまでつ右を探し続ける。
- 一瞬無限ループするのではと思ったが、なので全部埋まることはない。
- 愚直に探していくととなってしまう。
- 以上で最小の未設定箇所が高速にわかればよい。
- ~を全部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)
逆元を乗で求めるなんて意識を持ったことがないせいで、という考えが全然出てこないことに気付かされた。
これができなかったのはさすがに反省。
F以降は今ある知識的にできなくて当然の内容だったのでよしとする。