AtCoder Beginner Contest 272
コンテスト前のレート:1977
レート通りのパフォーマンスが得られる順位:337位(1500点、34分38秒)
A - Integer Sum
思考過程
- そのまんまfor文回して合計を求めるだけ。
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[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = sc.nextInt(); } sc.close(); int ans = 0; for (int i = 0; i < n; i++) { ans += a[i]; } System.out.println(ans); } }
ここまで0分45秒+0ペナ。661位。
B - Everyone is Friends
思考過程
- 通りの組み合わせを全て調べ、同じ舞踏会に参加した組を人の総当たり戦の表に記録していくイメージ。
- 表の右上半分が全て埋まっているかどうかを調べる。
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 m = sc.nextInt(); int[] k = new int[m]; int[][] x = new int[m][]; for (int i = 0; i < m; i++) { k[i] = sc.nextInt(); x[i] = new int[k[i]]; for (int j = 0; j < k[i]; j++) { x[i][j] = sc.nextInt() - 1; } } sc.close(); boolean[][] b = new boolean[n][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < k[i]; j++) { for (int j2 = 0; j2 < j; j2++) { b[x[i][j2]][x[i][j]] = true; } } } for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { if (!b[j][i]) { System.out.println("No"); return; } } } System.out.println("Yes"); } }
ここまで3分31秒+0ペナ。172位。
C - Max Even
思考過程
- を奇数の集合と偶数の集合に分ける。降順に取り出せるPriorityQueueを使うのがよさそう。
- それぞれの集合について、要素数が個以上の場合に大きい要素から順につ取り出して和を求め、大きい方が答え。
import java.util.Collections; import java.util.PriorityQueue; 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[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = sc.nextInt(); } sc.close(); PriorityQueue<Integer> odd = new PriorityQueue<>(Collections.reverseOrder()); PriorityQueue<Integer> even = new PriorityQueue<>(Collections.reverseOrder()); for (int i = 0; i < n; i++) { if (a[i] % 2 == 0) { even.add(a[i]); } else { odd.add(a[i]); } } int ans = -1; if (odd.size() >= 2) { int v1 = odd.poll(); int v2 = odd.poll(); ans = v1 + v2; } if (even.size() >= 2) { int v1 = even.poll(); int v2 = even.poll(); ans = Math.max(ans, v1 + v2); } System.out.println(ans); } }
ここまで6分30秒+0ペナ。218位。
D - Root M Leaper
思考過程
- やることはただのBFS。だが遷移部分が大変。
- となるの組をあらかじめ求めておき、各組についての遷移を行う。
- あらかじめ求める部分は、をから単調増加、をから単調減少させながら条件を満たす値を探せば。
だが後から思えばではなくまでで十分だったし、なんならでも問題なかった。
import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Queue; 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 m = sc.nextInt(); sc.close(); List<Integer> listX = new ArrayList<>(); List<Integer> listY = new ArrayList<>(); int y = 1000; for (int x = 0; x <= 1000; x++) { int xx = x * x; if (xx > m) { break; } while (xx + y * y > m) { y--; } if (xx + y * y == m) { listX.add(x); listY.add(y); } } int[] sx = {1, 1, -1, -1}; int[] sy = {1, -1, 1, -1}; int[][] a = new int[n][n]; for (int i = 0; i < n; i++) { Arrays.fill(a[i], -1); } Queue<Integer> que = new ArrayDeque<>(); que.add(0); a[0][0] = 0; while (!que.isEmpty()) { int cur = que.poll(); int cx = cur / n; int cy = cur % n; for (int i = 0; i < listX.size(); i++) { int dx = listX.get(i); int dy = listY.get(i); for (int k = 0; k < 4; k++) { int nx = cx + dx * sx[k]; int ny = cy + dy * sy[k]; if (nx < 0 || n <= nx || ny < 0 || n <= ny) { continue; } if (a[nx][ny] == -1) { a[nx][ny] = a[cx][cy] + 1; que.add(nx * n + ny); } } } } for (int i = 0; i < n; i++) { StringBuilder sb = new StringBuilder(); for (int j = 0; j < n; j++) { sb.append(a[i][j]).append(' '); } sb.deleteCharAt(sb.length() - 1); System.out.println(sb.toString()); } } }
ここまで16分29秒+0ペナ。170位。
E - Add and Mex
問題
しばらく何もわからず、先にFも問題だけは読んでいた。(Fもわからずすぐ戻ってきた)
思考過程
- 各要素について、「何回かの操作でにできるか調べ、回でできるならをにする」ということをから順に更新がなくなるまでやってみたらどうか?
- 答えの最大値をとしてかかるが、はそんなに大きくならないのでは? →TLE
- 各要素が操作の過程で~になる部分だけに注目することができれば、調和級数でになる。
- それらを全部Setに突っ込んでしまえば、後は普通にから調べていってMexを求めることができそう。 →1579ms、261MBでなんとか通る
import java.io.PrintWriter; import java.util.ArrayList; import java.util.HashSet; import java.util.List; 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(); int m = sc.nextInt(); int[] a = new int[n + 1]; for (int i = 1; i <= n; i++) { a[i] = sc.nextInt(); } sc.close(); List<Set<Integer>> list = new ArrayList<>(m + 1); for (int i = 0; i <= m; i++) { list.add(new HashSet<>()); } for (int i = 1; i <= n; i++) { int d = 0; if (a[i] < 0) { d -= a[i] / i; } if (d == 0) { d = 1; } for (int j = d; j <= m; j++) { int v = a[i] + i * j; if (v < 0) { continue; } if (v > n) { break; } list.get(j).add(v); } } PrintWriter pw = new PrintWriter(System.out); for (int i = 1; i <= m; i++) { Set<Integer> set = list.get(i); for (int j = 0; ; j++) { if (!set.contains(j)) { pw.println(j); break; } } } pw.flush(); } }
ここまで46分26秒+1ペナ。344位。
以降はFとGを両方見てG重視で解こうとしていたが、どちらも解けず。
Gは要素の全組み合わせについて差に含まれる素因数を全探索していたら間に合いそうにないなで止まっていた。
FはにSuffixArrayを使うことまで思い付いていたが、それだけだと半分くらいWA。(だと8割近く通った)
の場合などに由来のindexが先に来てしまってカウントできておらず、小細工を試みるもAC数変わらず。
同率部分を上手くカウントすることばかり考えており、間にダミーを挟めば上手くいくとは全く考えられなかった。
最終結果:ABCDEの5完1500点、51分26秒、464位、パフォーマンス1823
レート変動:1977→1962(-15)
Eが18分で解ければノルマ通り。
TLE解法とAC解法に15分ずつかかっていたので、最初からAC解法に行けていればぎりぎりなんとかなったかどうか。
問題の見た目と配点でFよりGを優先してしまったが、Fに集中していればなんとかできた可能性がもう少しあったかも?