デンソークリエイトプログラミングコンテスト2022(AtCoder Beginner Contest 239)(Rated範囲外)
- A - Horizon
- B - Integer Division
- C - Knight Fork
- D - Prime Sum Game
- E - Subtree K-th Max
- G - Builder Takahashi
コンテスト前のレート:2060
(Ratedだとしたら)レート通りのパフォーマンスが得られる順位:295位(2000点、71分42秒)
A - Horizon
思考過程
- 一見ややこしいが基本的には問題文の通りの計算を行うだけ。
- int型ではオーバーフローする可能性があるため、最初からdouble型で計算する。
import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); double h = sc.nextInt(); sc.close(); double ans = Math.sqrt(h * (12800000 + h)); System.out.println(ans); } }
ここまで1分08秒+0ペナ。219位。
B - Integer Division
思考過程
- 単純に「/」で切り捨て除算を行おうとした場合、が負の場合は切り上げになってしまう。
- 負の場合はあらかじめしておくことで帳尻を合わせる。
import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); long x = sc.nextLong(); sc.close(); if (x % 10 != 0 && x < 0) { x -= 9; } System.out.println(x / 10); } }
ここまで2分45秒+0ペナ。300位。
C - Knight Fork
問題
さすがに長さ8の配列dx, dyを作ってfor文で処理するくらいはした方が早かったかもしれない。
思考過程
- 問題の図の通り、該当する点が箇所しかないので、とからの箇所を列挙して比較する。
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 x1 = sc.nextInt(); int y1 = sc.nextInt(); int x2 = sc.nextInt(); int y2 = sc.nextInt(); sc.close(); Set<String> set = new HashSet<>(); set.add((x1 - 2) + "-" + (y1 + 1)); set.add((x1 - 2) + "-" + (y1 - 1)); set.add((x1 - 1) + "-" + (y1 + 2)); set.add((x1 - 1) + "-" + (y1 - 2)); set.add((x1 + 1) + "-" + (y1 + 2)); set.add((x1 + 1) + "-" + (y1 - 2)); set.add((x1 + 2) + "-" + (y1 + 1)); set.add((x1 + 2) + "-" + (y1 - 1)); if (set.contains((x2 - 2) + "-" + (y2 + 1)) || set.contains((x2 - 2) + "-" + (y2 - 1)) || set.contains((x2 - 1) + "-" + (y2 + 2)) || set.contains((x2 - 1) + "-" + (y2 - 2)) || set.contains((x2 + 1) + "-" + (y2 + 2)) || set.contains((x2 + 1) + "-" + (y2 - 2)) || set.contains((x2 + 2) + "-" + (y2 + 1)) || set.contains((x2 + 2) + "-" + (y2 - 1))) { System.out.println("Yes"); } else { System.out.println("No"); } } }
ここまで7分12秒+0ペナ。276位。
D - Prime Sum Game
思考過程
import java.util.HashMap; import java.util.Map; import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); int a = sc.nextInt(); int b = sc.nextInt(); int c = sc.nextInt(); int d = sc.nextInt(); sc.close(); Eratosthenes era = new Eratosthenes(200); for (int i = a; i <= b; i++) { boolean flg = false; for (int j = c; j <= d; j++) { if (era.isSosuu(i + j)) { flg = true; } } if (!flg) { System.out.println("Takahashi"); return; } } System.out.println("Aoki"); } // 以下ライブラリ static class Eratosthenes { int[] div; public Eratosthenes(int n) { div = new int[n + 1]; if (n < 2) return; div[0] = -1; div[1] = -1; int end = (int) Math.sqrt(n) + 1; for (int i = 2; i <= end; i++) { if (div[i] == 0) { div[i] = i; for (int j = i * i; j <= n; j+=i) { if (div[j] == 0) div[j] = i; } } } for (int i = end + 1; i <= n; i++) { if (div[i] == 0) div[i] = i; } } public Map<Integer, Integer> bunkai(int x) { Map<Integer, Integer> soinsu = new HashMap<>(); while (x > 1) { Integer d = div[x]; soinsu.put(d, soinsu.getOrDefault(d, 0) + 1); x /= d; } return soinsu; } public boolean isSosuu(int x) { return div[x] == x; } } }
ここまで10分29秒+0ペナ。190位。
E - Subtree K-th Max
問題
制約をまともに見ておらず時間ロス。
思考過程
- 頂点の情報を葉からまとめ上げながら木DPをし、現在調べている頂点に対するクエリをまとめて処理する。
- 頂点の情報は座標圧縮したBITで持ち、番目は二分探索で求めるとかする? と思ったが、であるため、上位最大個のみMultiSet(Javaにはないので自作)で保持するようにする。
- ケースのみTLEになったので、藁にも縋る思いでマージテクでごまかしてみて通った。
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.ArrayList; import java.util.List; import java.util.TreeMap; public class Main { static int n, q; static int[] x; static List<List<Integer>> list; static List<List<Obj>> qList; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] sa = br.readLine().split(" "); n = Integer.parseInt(sa[0]); q = Integer.parseInt(sa[1]); sa = br.readLine().split(" "); x = new int[n]; for (int i = 0; i < n; i++) { x[i] = Integer.parseInt(sa[i]); } list = new ArrayList<>(n); for (int i = 0; i < n; i++) { list.add(new ArrayList<>()); } for (int i = 0; i < n - 1; i++) { sa = br.readLine().split(" "); int a = Integer.parseInt(sa[0]) - 1; int b = Integer.parseInt(sa[1]) - 1; list.get(a).add(b); list.get(b).add(a); } Obj[] arr = new Obj[q]; qList = new ArrayList<>(n); for (int i = 0; i < n; i++) { qList.add(new ArrayList<>()); } for (int i = 0; i < q; i++) { sa = br.readLine().split(" "); Obj o = new Obj(); o.v = Integer.parseInt(sa[0]) - 1; o.k = Integer.parseInt(sa[1]); arr[i] = o; qList.get(o.v).add(o); } br.close(); dfs(0, -1); PrintWriter pw = new PrintWriter(System.out); for (Obj o : arr) { pw.println(o.ans); } pw.flush(); } static MultiTreeSet<Integer> dfs(int a, int p) { MultiTreeSet<Integer> set = new MultiTreeSet<>(); for (int c : list.get(a)) { if (c != p) { MultiTreeSet<Integer> res = dfs(c, a); // 思考過程3 if (set.size < res.size) { MultiTreeSet<Integer> t = res; res = set; set = t; } for (Object e : res.toArrayAll()) { set.add((Integer) e); if (set.size > 20) { set.pollFirst(); } } } } set.add(x[a]); if (set.size > 20) { set.pollFirst(); } Object[] arr = set.toArrayAll(); // 頂点aに対するクエリの処理 for (Obj o : qList.get(a)) { o.ans = (Integer) arr[arr.length - o.k]; } return set; } static class Obj { int v, k, ans; } // 以下ライブラリ(長いため未使用メソッドを削除している) static class MultiTreeSet<T> { TreeMap<T, Integer> map = new TreeMap<>(); int size = 0; void add(T e) { map.put(e, map.getOrDefault(e, 0) + 1); size++; } void remove(T e) { if (e != null && map.containsKey(e)) { int val = map.get(e); if (val == 1) { map.remove(e); } else { map.put(e, val - 1); } size--; } } T pollFirst() { T e = map.firstKey(); remove(e); return e; } Object[] toArrayAll() { Object[] arr = new Object[size]; int idx = 0; for (T e : map.keySet()) { int num = map.get(e); for (int i = 0; i < num; i++) { arr[idx] = e; idx++; } } return arr; } } }
ここまで42分30秒+3ペナ。929位。
Fは、足りない次数が最も少ない頂点と最も多い頂点を連結していくようなことをやろうとしていたが、実装に多大な時間がかかった上にWA。
G - Builder Takahashi
問題
終了1分16秒後にAC。
思考過程
- 最小カットの雰囲気なので、どうやったら最小カットが使えるかを考える。
- 最小カットは頂点ではなく辺をカットするものであるため、頂点を辺に変えたい。
- 頂点をつにし、からに容量の辺を張ることにする。
- 他の辺は最小カットに影響を与えたくないので、容量infにしておく。
- 答えの金額がになってしまい、上手くいかない。(ここでタイムアップ)
- 頂点をカットするのは駄目なので、をinfにする必要があった。
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.List; 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 n = Integer.parseInt(sa[0]); int m = Integer.parseInt(sa[1]); List<List<Integer>> 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; list.get(a).add(b); list.get(b).add(a); } sa = br.readLine().split(" "); long[] c = new long[n]; for (int i = 0; i < n; i++) { c[i] = Integer.parseInt(sa[i]); } br.close(); long inf = 10000000000000L; // 6 c[0] = inf; c[n - 1] = inf; MaxFlow mf = new MaxFlow(n * 2); for (int i = 0; i < n; i++) { // 4 for (int j : list.get(i)) { mf.addEdge(i + n, j, inf); } // 3 mf.addEdge(i, i + n, c[i]); } long f = mf.flow(0, n * 2 - 1); // ACLのminCutは各頂点に到達可能かどうかが返される boolean[] b = mf.minCut(0); long ans = 0; int k = 0; List<Integer> list2 = new ArrayList<>(); for (int i = 0; i < n; i++) { // 倍加した頂点の一方のみ到達可能であれば、そこで切っている if (b[i] != b[i + n]) { list2.add(i + 1); ans += c[i]; k++; } } System.out.println(ans); System.out.println(k); StringBuilder sb = new StringBuilder(); for (int i : list2) { sb.append(i).append(' '); } sb.deleteCharAt(sb.length() - 1); System.out.println(sb.toString()); } } // 以下ACLを移植したMaxFlow
提出
ここまで101分16秒+3ペナ。
最終結果:ABCDEの5完1500点、57分30秒、1257位、パフォーマンス1355相当
レート変動:2060(Unrated)
結果はまたボロボロだが、Gが間に合っていればパフォ2200くらいだったのでまあ・・・。
それにしてもABCの成績全く安定しない。