AtCoder Beginner Contest 224(Rated範囲外)
- A - Tires
- B - Mongeness
- C - Triangle?
- D - 8 Puzzle on Graph
- E - Integers on Grid
- F - Problem where +s Separate Digits
コンテスト前のレート:2038
(Ratedだとしたら)レート通りのパフォーマンスが得られる順位:273位(2000点、96分17秒)
A - Tires
思考過程
- endsWithメソッドを使うことで末尾の判定ができるので、それで末尾が"er"かどうかを判定する。
import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); String s = sc.next(); sc.close(); if (s.endsWith("er")) { System.out.println("er"); } else { System.out.println("ist"); } } }
ここまで0分50秒+0ペナ。119位。
B - Mongeness
思考過程
- が間に合う制約なので、四重ループを回し、全ての組について条件を満たすか判定する。
- 満たさない組がつでもあった時点で"No"を出力して終了。途中で終了しなければ"Yes"。
import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); int h = sc.nextInt(); int w = sc.nextInt(); int[][] a = new int[h][w]; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { a[i][j] = sc.nextInt(); } } sc.close(); for (int i1 = 0; i1 < h; i1++) { for (int i2 = i1 + 1; i2 < h; i2++) { for (int j1 = 0; j1 < w; j1++) { for (int j2 = j1 + 1; j2 < w; j2++) { if (a[i1][j1] + a[i2][j2] > a[i1][j2] + a[i2][j1]) { System.out.println("No"); return; } } } } } System.out.println("Yes"); } }
ここまで3分13秒+0ペナ。103位。
C - Triangle?
思考過程
- が間に合う制約なので、通りの組み合わせを全て調べる。
- 三角形の面積がになるのは点が一直線上にある場合なので、それ以外の場合をカウントしたい。
- を通る直線とを通る直線の傾きが同じならば、点は一直線上にある。
- は正確に判定しづらいので、移項してを判定する。
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 = new int[n]; int[] y = new int[n]; for (int i = 0; i < n; i++) { x[i] = sc.nextInt(); y[i] = sc.nextInt(); } sc.close(); int ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { for (int k = 0; k < j; k++) { long dx1 = x[j] - x[i]; long dx2 = x[k] - x[i]; long dy1 = y[j] - y[i]; long dy2 = y[k] - y[i]; if (dx2 * dy1 != dx1 * dy2) { ans++; } } } } System.out.println(ans); } }
ここまで6分40秒+0ペナ。87位。
D - 8 Puzzle on Graph
思考過程
- あり得るコマの配置(以下盤面)が通り程度に収まるため、それらの盤面を頂点、コマの移動を辺に見立てたグラフでBFSを行う。
- 盤面を表す情報は、各コマが置かれている頂点番号を連結した数値か文字列としたい。初期盤面であれば入力のをそのまま連結したもの。
- 数値か文字列かは、実装が楽な方にしたいが、文字列の方が桁入れ替える処理を実装しやすいと判断した。
- コマの移動に合わせて盤面情報を作り直すことができれば、あとは普通にBFSを行うだけ。
import java.util.ArrayDeque; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; 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 = 9; List<List<Integer>> list = new ArrayList<>(); for (int i = 0; i < n; i++) { list.add(new ArrayList<>()); } int m = sc.nextInt(); for (int i = 0; i < m; i++) { int u = sc.nextInt() - 1; int v = sc.nextInt() - 1; list.get(u).add(v); list.get(v).add(u); } StringBuilder sb = new StringBuilder(); for (int i = 0; i < 8; i++) { int p = sc.nextInt() - 1; sb.append(p); } sc.close(); String s = sb.toString(); Queue<String> que = new ArrayDeque<>(); que.add(s); Map<String, Integer> map = new HashMap<>(); map.put(s, 0); while (!que.isEmpty()) { String cur = que.poll(); int x = 36; // 0~8の合計 // 合計から各桁の値を引くことで、curに含まれていない値を得る for (int i = 0; i < 8; i++) { x -= cur.charAt(i) - '0'; } for (int y : list.get(x)) { // コマを頂点y→xに移動 String next = cur.replace((char) ('0' + y), (char) ('0' + x)); if (!map.containsKey(next)) { que.add(next); map.put(next, map.get(cur) + 1); } } } if (map.containsKey("01234567")) { System.out.println(map.get("01234567")); } else { System.out.println(-1); } } }
ここまで17分55秒+0ペナ。52位。
E - Integers on Grid
思考過程
- が大きいマスから順に処理し、既に処理済みのマスへのみ移動させられるとすることで、「真に大きい」の条件を満たせる。が同じである処理済みマスを見てしまわないようにする必要はあるが。
- 各マスは、「他のマスへ移動できるならば「移動先マスの答え」の最大値が答え」といった形でが大きいマスから埋めていくDPができる。
- 移動先の候補として処理済みマスを全て調べてしまったら各マスごとにかかり、全体でとなりTLE。
- 各行、各列ごとの最大値だけ保持しておくようにすれば、各マスごとにで済む。
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.ArrayDeque; import java.util.Arrays; import java.util.PriorityQueue; 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 h = Integer.parseInt(sa[0]); int w = Integer.parseInt(sa[1]); int n = Integer.parseInt(sa[2]); PriorityQueue<Obj> que = new PriorityQueue<>((o1, o2) -> o2.a - o1.a); Obj[] arr = new Obj[n]; for (int i = 0; i < n; i++) { sa = br.readLine().split(" "); Obj o = new Obj(); o.i = i; o.x = Integer.parseInt(sa[0]) - 1; o.y = Integer.parseInt(sa[1]) - 1; o.a = Integer.parseInt(sa[2]); que.add(o); arr[i] = o; } br.close(); int[] mx = new int[h]; // 各行の最大値 int[] my = new int[w]; // 各列の最大値 Arrays.fill(mx, -1); Arrays.fill(my, -1); Queue<Obj> que2 = new ArrayDeque<>(); // aが同じものを溜めておく while (!que.isEmpty()) { Obj o = que.poll(); while (!que2.isEmpty() && que2.peek().a > o.a) { Obj o2 = que2.poll(); mx[o2.x] = Math.max(mx[o2.x], o2.ans); my[o2.y] = Math.max(my[o2.y], o2.ans); } o.ans = Math.max(mx[o.x], my[o.y]) + 1; que2.add(o); } PrintWriter pw = new PrintWriter(System.out); for (Obj o : arr) { pw.println(o.ans); } pw.flush(); } static class Obj { int i, x, y, a, ans; } }
ここまで28分25秒+0ペナ。43位。
F - Problem where +s Separate Digits
問題
下記の「文字目」は0-indexedとする。
思考過程
- 特定の数が何回現れるかという方向性で考えてみる。
- の文字目がどれくらい最終的な答えに寄与するかを考えてみる。
- の文字目がの位で何回、の位で何回、、の位で何回現れるかを、例1を書き出して調べてみる。
- まずの位で何回現れるかは、文字目の直後で切られることが前提で、
- 文字目より左側は、箇所を切る切らないを自由に選択可能なので、通り。
- 文字目より右側は、箇所を切る切らないを自由に選択可能なので、通り。
- の位、の位、と調べていくと、上記点目は変わらず、点目は選択可能箇所がつずつ減っていき、通り数としては半分ずつになっていく。ただし、最後は通りが回。
- 以上をまとめると、を求めたい。
- に関する総和の部分について高速化する必要があるので、累乗や累積和等の前計算をしておき、頑張って帳尻合わせをする。
import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); char[] s = br.readLine().toCharArray(); br.close(); int n = s.length; int mod = 998244353; int m2 = (mod + 1) / 2; long[] b = new long[n + 5]; // b[i] = 2^i +5は適当に予備 long[] bm = new long[n + 5]; // bm[i] = 2^iの逆元 long[] t = new long[n + 5]; // t[i] = 10^i long[] tot = new long[n + 6]; // tの累積和 b[0] = 1; bm[0] = 1; t[0] = 1; tot[1] = 1; for (int i = 1; i < t.length; i++) { b[i] = b[i - 1] * 2 % mod; bm[i] = bm[i - 1] * m2 % mod; t[i] = t[i - 1] * 10 % mod; tot[i + 1] = (tot[i] + t[i]) % mod; } long[] t2 = new long[n + 5]; // t[i]に2^(n+4-i)の重みを付けたもの long[] tot2 = new long[n + 6]; // t2の累積和 int n4 = n + 4; for (int i = 0; i < t2.length; i++) { t2[i] = t[i] * b[n4 - i] % mod; tot2[i + 1] = (tot2[i] + t2[i]) % mod; } long ans = 0; for (int i = 0; i < n; i++) { int c = s[i] - '0'; int ni = n - i; long v1 = c; // s[i]の値 long v2 = b[i]; // 左側 long v3 = 0; // 右側 int x1 = ni - 2; if (x1 > 0) { int x2 = n4 - x1; long x3 = bm[x2]; // t2の重みの帳尻合わせ long v31 = tot2[x1] * x3 % mod; long v32 = (tot[ni] - tot[x1] + mod) % mod; v3 = (v31 + v32) % mod; } else { v3 = tot[ni]; } long val = v1 * v2 % mod * v3 % mod; ans += val; } ans %= mod; System.out.println(ans); } }
ここまで90分44秒+0ペナ。238位。
Gは10分では無理。
最終結果:ABCDEFの6完2000点、90分44秒、246位、パフォーマンス2092相当
レート変動:2038(Unrated)
結果がまずまずなのはEが上手いことすぐ解けただけで、Fももっとすんなり解けないと駄目なんだろうなという感じ。