大和証券プログラミングコンテスト2022 Autumn (AtCoder Beginner Contest 277)(Rated範囲外)
- A - ^{-1}
- B - Playing Cards Validation
- C - Ladder Takahashi
- D - Takahashi's Solitaire
- E - Crystal Switches
コンテスト前のレート:2000
(Ratedだとしたら)レート通りのパフォーマンスが得られる順位:341位(1500点、39分39秒)
A - ^{-1}
思考過程
- を全探索し、となった時のを1-indexedに直して出力する。
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(); int[] p = new int[n]; for (int i = 0; i < n; i++) { p[i] = sc.nextInt(); } sc.close(); for (int i = 0; i < n; i++) { if (p[i] == x) { System.out.println(i + 1); return; } } } }
ここまで1分02秒+0ペナ。385位。
B - Playing Cards Validation
思考過程
- 条件つ目とつ目は地道に調べる。
- 条件つ目はを全てSetに入れた結果サイズがとなるかを調べる。
import java.util.HashSet; import java.util.Scanner; import java.util.Set; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); String[] s = new String[n]; for (int i = 0; i < n; i++) { s[i] = sc.next(); } sc.close(); Set<String> set = new HashSet<>(); for (int i = 0; i < n; i++) { set.add(s[i]); char a = s[i].charAt(0); if (a == 'H' || a == 'D' || a == 'C' || a == 'S') { } else { System.out.println("No"); return; } char b = s[i].charAt(1); if (b == 'A' || '2' <= b && b <= '9' || b == 'T' || b == 'J' || b == 'Q' || b == 'K') { } else { System.out.println("No"); return; } } if (set.size() == n) { System.out.println("Yes"); } else { System.out.println("No"); } } }
ここまで5分39秒+0ペナ。703位。
C - Ladder Takahashi
思考過程
- との間に辺があるとみなしてBFSを行う。
- 制約が大きく頂点数分の配列を用意することができないので、隣接リストはMap<階、移動先階リスト>の形で持ち、特定の階を訪れたかどうかの判定にはSetを使う。
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.HashMap; import java.util.HashSet; import java.util.List; import java.util.Map; import java.util.Queue; import java.util.Set; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); Map<Integer, List<Integer>> map = new HashMap<>(); for (int i = 0; i < n; i++) { String[] sa = br.readLine().split(" "); int a = Integer.parseInt(sa[0]); int b = Integer.parseInt(sa[1]); List<Integer> list = map.get(a); if (list == null) { list = new ArrayList<>(); map.put(a, list); } list.add(b); list = map.get(b); if (list == null) { list = new ArrayList<>(); map.put(b, list); } list.add(a); } br.close(); int ans = 1; Set<Integer> set = new HashSet<>(); Queue<Integer> que = new ArrayDeque<>(); set.add(1); que.add(1); while (!que.isEmpty()) { int cur = que.poll(); List<Integer> list = map.get(cur); if (list == null) { continue; } for (int next : list) { if (set.add(next)) { ans = Math.max(ans, next); que.add(next); } } } System.out.println(ans); } }
ここまで11分08秒+0ペナ。449位。
D - Takahashi's Solitaire
問題
例2が通ったことで全部取り除ける場合も問題ないと勘違いして1ペナ。
思考過程
- をソートすると、前後の要素と値が以上離れていない連続した箇所をまとめて取り除けるということになる。
- そのような連続した箇所の和のリストを作る。
- かつの場合は、和のリストの先頭と末尾はまとめることができる。
- 和のリストの中の最大値を、の総和から引く。
- ~が全て含まれている場合に倍にしてしまっていたので、和のリストの要素が個の場合は先頭と末尾を足さないように修正。
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.List; 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]); sa = br.readLine().split(" "); int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = Integer.parseInt(sa[i]); } br.close(); // 1, 2 Arrays.sort(a); List<Long> list = new ArrayList<>(); long val = 0; long sum = 0; for (int i = 0; i < n; i++) { sum += a[i]; val += a[i]; if (i == n - 1 || a[i] + 2 <= a[i + 1]) { list.add(val); val = 0; } } // 3. 5 if (a[0] == 0 && a[n - 1] == m - 1 && list.size() > 1) { list.set(0, list.get(0) + list.get(list.size() - 1)); list.remove(list.size() - 1); } // 4 long max = 0; for (long e : list) { max = Math.max(max, e); } System.out.println(sum - max); } }
ここまで19分39秒+1ペナ。166位。
E - Crystal Switches
思考過程
- 「スイッチを押していない状態と押している状態それぞれで各頂点にいる場合」の個の頂点があるとみなしてダイクストラ法をする。
- 遷移はスイッチの押下状態に応じて使える辺の移動と、スイッチがある頂点について押下状態の変更を行う。
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.HashSet; import java.util.List; import java.util.PriorityQueue; 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 m = Integer.parseInt(sa[1]); int k = Integer.parseInt(sa[2]); List<List<Hen>> list = new ArrayList<>(n); for (int i = 0; i < n; i++) { list.add(new ArrayList<>()); } for (int i = 0; i < m; i++) { sa = br.readLine().split(" "); int a = Integer.parseInt(sa[0]) - 1; int b = Integer.parseInt(sa[1]) - 1; int c = Integer.parseInt(sa[2]); list.get(a).add(new Hen(b, c)); list.get(b).add(new Hen(a, c)); } sa = br.readLine().split(" "); Set<Integer> set = new HashSet<>(); for (int i = 0; i < k; i++) { set.add(Integer.parseInt(sa[i]) - 1); } br.close(); int s = 0; long[][] d = new long[2][list.size()]; Arrays.fill(d[0], Long.MAX_VALUE); Arrays.fill(d[1], Long.MAX_VALUE); d[0][s] = 0; PriorityQueue<Node> que = new PriorityQueue<Node>(); Node first = new Node(s, 0); que.add(first); while (!que.isEmpty()) { Node cur = que.poll(); int cx = cur.v / n; int cy = cur.v % n; if (cur.d > d[cx][cy]) { continue; } // 辺を移動 for (Hen hen : list.get(cy)) { if (cx + hen.c == 1) { long alt = d[cx][cy] + 1; if (alt < d[cx][hen.v]) { d[cx][hen.v] = alt; que.add(new Node(cx * n + hen.v, alt)); } } } // スイッチを押す if (set.contains(cy)) { if (d[1 - cx][cy] > d[cx][cy]) { d[1 - cx][cy] = d[cx][cy]; que.add(new Node((1 - cx) * n + cy, d[cx][cy])); } } } long ans = Math.min(d[0][n - 1], d[1][n - 1]); if (ans == Long.MAX_VALUE) { ans = -1; } System.out.println(ans); } static class Hen { int v, c; public Hen(int v, int c) { this.v = v; this.c = c; } } static class Node implements Comparable<Node> { int v; long d; public Node(int v, long d) { this.v = v; this.d = d; } public int compareTo(Node o) { return Long.compare(d, o.d); } } }
ここまで32分05秒+1ペナ。179位。
Fは行と列を独立に考え、を無視してまずは行について
行目最小行目最大行目最小行目最大
を満たすかどうか調べる。
その後各行内の大小関係を元に必要最小限の辺を張ってトポロジカルソートできるかどうかを調べようとしたが、同じ値が複数存在した場合の辺の張り方が不十分であったらしい。
その後、誤読が原因かと勘違いして問題文を読み直し、を相異なる値に変えなければならないとかえって誤読してさらにハマった。
誤読したおかげで、最後はのような行とのような行のどちらを先にすればよいか決めるのが困難だとか思いながら終わった。
Gはあまり考えていないが、「回目の操作で頂点にいてレベルがの確率」のようなくらいになりそうな方法しか思い浮かばず。
明らかに計算量が駄目なのでこれでできているのかもまともに考えていない。
最終結果:ABCDEの5完1500点、37分05秒、309位、パフォーマンス2054相当
レート変動:2000(Unrated)
できればF解きたかった気もしなくはないが、まあ普通くらいの結果なのでヨシ。
さっさとAHC016に戻る。