HHKB プログラミングコンテスト 2022（AtCoder Beginner Contest 235）(Rated範囲外)
コンテスト前のレート：2024
（Ratedだとしたら）レート通りのパフォーマンスが得られる順位：342位（1500点、27分24秒）
A - Rotate
思考過程
をよく見ると、
は各桁に
回ずつ現れる。
- つまり、
を求めるのと同じなので、
倍を足し合わせればよい。
import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); char[] a = sc.next().toCharArray(); sc.close(); int ans = 0; for (int i = 0; i < a.length; i++) { int c = a[i] - '0'; ans += 111 * c; } System.out.println(ans); } }
ここまで1分23秒＋0ペナ。279位。
B - Climbing Takahashi
思考過程
- 単純に
の最大値を求めるだけ？と勘違いしそうになったが、サンプルをしっかり確認すると、要するに狭義単調増加が最初に途切れる箇所の値を求める問題。
である限り答えを
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[] h = new int[n]; for (int i = 0; i < n; i++) { h[i] = sc.nextInt(); } sc.close(); int ans = h[0]; for (int i = 1; i < n; i++) { if (h[i - 1] < h[i]) { ans = h[i]; } else { break; } } System.out.println(ans); } }
ここまで3分12秒＋0ペナ。285位。
C - The Kth Time Query
思考過程
- どのような形式でデータを保持しておけばクエリに答えやすいかを考える。
- Map＜値、インデックスList＞としておけば、Mapから
に該当するインデックスListの
番目を取得すればよいので、各クエリに
で答えられる。
- なお、Mapのキーに
。
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; 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 q = Integer.parseInt(sa[1]); sa = br.readLine().split(" "); Map<Integer, List<Integer>> map = new HashMap<>(); for (int i = 0; i < n; i++) { int a = Integer.parseInt(sa[i]); List<Integer> list = map.get(a); if (list == null) { list = new ArrayList<>(); map.put(a, list); } list.add(i); } PrintWriter pw = new PrintWriter(System.out); for (int i = 0; i < q; i++) { sa = br.readLine().split(" "); int x = Integer.parseInt(sa[0]); int k = Integer.parseInt(sa[1]) - 1; List<Integer> list = map.get(x); if (list == null) { pw.println(-1); } else { if (k < list.size()) { pw.println(list.get(k) + 1); } else { pw.println(-1); } } } br.close(); pw.flush(); } }
ここまで8分02秒＋0ペナ。568位。
D - Multiply and Rotate
問題
オーバーフローで1ペナ。
思考過程
- 各値を頂点、
倍およびRotateの操作を辺とみなしたグラフでBFSをする。
- これらの操作では、値が減ることはあるが桁数が減ることはないので、頂点は
の最大値
と同じ桁数の
まで用意しておけば十分。（後からよく見たら、制約に等号は付いていなくて、1桁余計だった）
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Arrays; import java.util.Queue; 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 a = Integer.parseInt(sa[0]); int n = Integer.parseInt(sa[1]); br.close(); Queue<Integer> que = new ArrayDeque<>(); que.add(1); int[] d = new int[10000000]; Arrays.fill(d, -1); d[1] = 0; while (!que.isEmpty()) { int cur = que.poll(); // a倍 long v = (long) cur * a; int next = cur * a; if (v < d.length && d[next] == -1) { que.add(next); d[next] = d[cur] + 1; } // Rotate if (cur >= 10 && cur % 10 != 0) { String s = String.valueOf(cur); s = s.substring(s.length() - 1) + s.substring(0, s.length() - 1); next = Integer.parseInt(s); if (next < d.length && d[next] == -1) { que.add(next); d[next] = d[cur] + 1; } } } System.out.println(d[n]); } }
ここまで16分13秒＋1ペナ。193位。
E - MST + 1
思考過程
- 元の辺とクエリの辺を一緒にしてクラスカル法をすれば、クエリの辺を見た時に
が既に連結かどうかで答えがわかる。
- ただし、クエリの順序が消失しないように別途配列に残したり、クラスカル法の際に元の辺のみ結合させるようにしたりする。
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.PrintWriter; 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 m = Integer.parseInt(sa[1]); int q = Integer.parseInt(sa[2]); PriorityQueue<Hen> que = new PriorityQueue<>((o1, o2) -> o1.c - o2.c); for (int i = 0; i < m; i++) { sa = br.readLine().split(" "); Hen h = new Hen(); h.a = Integer.parseInt(sa[0]) - 1; h.b = Integer.parseInt(sa[1]) - 1; h.c = Integer.parseInt(sa[2]); h.base = true; que.add(h); } Hen[] arr = new Hen[q]; for (int i = 0; i < q; i++) { sa = br.readLine().split(" "); Hen h = new Hen(); h.a = Integer.parseInt(sa[0]) - 1; h.b = Integer.parseInt(sa[1]) - 1; h.c = Integer.parseInt(sa[2]); que.add(h); arr[i] = h; } br.close(); UnionFind uf = new UnionFind(n); while (!que.isEmpty()) { Hen h = que.poll(); if (!uf.same(h.a, h.b)) { if (h.base) { // 元の辺の場合は結合 uf.union(h.a, h.b); } else { // クエリの辺の場合は答えを設定 h.ans = "Yes"; } } } PrintWriter pw = new PrintWriter(System.out); for (Hen h : arr) { pw.println(h.ans); } pw.flush(); } static class Hen { int a, b, c; boolean base; String ans = "No"; } // 以下ライブラリ static class UnionFind { int[] parent, size; int num = 0; // 連結成分の数 UnionFind(int n) { parent = new int[n]; size = new int[n]; num = n; for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; } } void union(int x, int y) { int px = find(x); int py = find(y); if (px != py) { parent[px] = py; size[py] += size[px]; num--; } } int find(int x) { if (parent[x] == x) { return x; } parent[x] = find(parent[x]); return parent[x]; } /** * xとyが同一連結成分か */ boolean same(int x, int y) { return find(x) == find(y); } /** * xを含む連結成分のサイズ */ int size(int x) { return size[find(x)]; } } }
ここまで22分24秒＋1ペナ。75位。
残り3問は一応全部問題は読んだが、残り時間のほとんどはFに使った。
Fは公式解説と比べて個数ではなく個以上存在するかになっていた（最初総和だけでやろうとして上手くいかず、遷移元として使っていいかという情報だけ追加していた）だけで、全く同様のDPをやろうとはしていたのだが、延々と例３が合わないまま時間切れ。
Gは包除っぽさだけは感じていた。
最終結果：ABCDEの5完1500点、27分24秒、342位、パフォーマンス2024相当
レート変動：2024（Unrated）
ぴったりレート通りのパフォ。
最近序盤から出遅れることが多かったので、Eまですんなり解けたのはよかった。Cはちょっと遅いけど。
UnionFindをちょっと工夫して使えばいいような問題は、割とハマること少ない気がする。
それに対してやっぱりDPを取りこぼすことが多すぎる・・・。
