エイシングプログラミングコンテスト(AtCoder Beginner Contest 202)(Rated範囲外)
コンテスト前のレート:2013
(Ratedだとしたら)レート通りのパフォーマンスが得られる順位:300位(1500点、54分30秒)
A - Three Dice
思考過程
- 裏面はそれぞれなので、合計は。
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(); sc.close(); System.out.println(21 - a - b - c); } }
ここまで0分32秒+0ペナ。88位。
B - 180°
思考過程
- 問題文の通り実装する。
- 実際に変換する必要があるのは、'6'と'9'のみ。
import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); char[] s = sc.next().toCharArray(); sc.close(); reverse(s); for (int i = 0; i < s.length; i++) { if (s[i] == '6') { s[i] = '9'; } else if (s[i] == '9') { s[i] = '6'; } } System.out.println(s); } // 以下ライブラリ static void reverse(char[] a) { for (int i = 0; i < a.length / 2; i++) { char tmp = a[i]; a[i] = a[a.length - 1 - i]; a[a.length - 1 - i] = tmp; } } }
ここまで2分22秒+0ペナ。242位。
C - Made Up
思考過程
- の数、の数、、の数を数え、についても同様に~の出現数を数える。
- (の数)(の数)を求める。
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(); } int[] b = new int[n]; for (int i = 0; i < n; i++) { b[i] = sc.nextInt(); } int[] c = new int[n]; for (int i = 0; i < n; i++) { c[i] = sc.nextInt() - 1; } sc.close(); int[] ac = new int[n + 1]; int[] bc = new int[n + 1]; for (int i = 0; i < n; i++) { ac[a[i]]++; bc[b[c[i]]]++; } long ans = 0; for (int i = 0; i < bc.length; i++) { ans += (long) ac[i] * bc[i]; } System.out.println(ans); } }
ここまで4分40秒+0ペナ。112位。
D - aab aba baa
問題
最初しばらくわからず、また3完で終わってしまうかと思った。
思考過程
- DPかDFSかできそうな方法を考える。
- 前から文字目までが決まっていて残りの'a'が個、'b'が個とすると、作れる文字列は通り。
- 先頭から順に、次の文字を'a'とした場合の通り数が以上である場合は'a'、未満である場合は'b'と決め打ちしていける。 ただし後者の場合は、'a'とした場合の通り数をこれまでの合計に足す必要がある。
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(); long k = sc.nextLong(); sc.close(); int n = a + b; int ra = a; // aの残り int rb = b; // bの残り long base = 0; // これまでの合計 StringBuilder sb = new StringBuilder(); for (int i = 0; i < n; i++) { if (ra == 0) { sb.append('b'); rb--; continue; } if (rb == 0) { sb.append('a'); ra--; continue; } long va = nCr(n - i - 1, ra - 1); // 次をaとした場合の通り数 if (base + va < k) { base += va; sb.append('b'); rb--; } else { sb.append('a'); ra--; } } System.out.println(sb.toString()); } // 以下ライブラリ static long nCr(int n, int r) { long val = 1; for (int i = 1; i <= r; i++) { val = val * (n - i + 1) / i; } return val; } }
ここまで17分31秒+0ペナ。211位。
E - Count Descendants
問題
どうやってもとかになりそうで、Unratedだからと諦めかけたが、なんとか解けた。
思考過程
- 深さごとの頂点のリストを用意したりしても、毎回深さがの頂点を全て調べたのでははかかってしまう。
- 問題文は逆に言えば、の配下の内、深さがである頂点の数を求めろと言っている。
- 各頂点に深さごとの配下の頂点リストを事前に用意しておくことを考えるが、それだとクエリにはで答えられるが、用意する部分が時間、空間共にになってしまう。
- クエリを前から順に処理していくのではなく、DFSをしながら同じに対するクエリを処理していくことを考える。
- 配下の頂点全部の個数を得るだけだったら最も基本的な木DPだが、それを深さごとに分けて個数を取得するにはどうしたらいいか。
- 深さごとの個数をカウントしていくための配列を用意する。
- 頂点に入ってきた時の状態を退避しておき、配下を調べて親に戻っていく際に、カウントの差分を元にクエリに答えられる。
- なお、入ってきた状態を退避しておくのにカウント配列全体をコピーしたのでは、各頂点ごとにコピー処理だけでかかり、全体でとなるため、クエリで使う深さの情報だけを退避する。
- これで退避がならしとなり、全体でにできる。
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.ArrayList; import java.util.List; public class Main { static List<List<Integer>> child, qr; static int[] u, d, ans; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); child = new ArrayList<>(n); qr = new ArrayList<>(n); for (int i = 0; i < n; i++) { child.add(new ArrayList<>()); qr.add(new ArrayList<>()); } String[] sa = br.readLine().split(" "); for (int i = 1; i < n; i++) { int p = Integer.parseInt(sa[i - 1]) - 1; child.get(p).add(i); } int q = Integer.parseInt(br.readLine()); u = new int[q]; d = new int[q]; for (int i = 0; i < q; i++) { sa = br.readLine().split(" "); u[i] = Integer.parseInt(sa[0]) - 1; d[i] = Integer.parseInt(sa[1]); qr.get(u[i]).add(i); // クエリを頂点ごとに分ける } br.close(); ans = new int[q]; dfs(0, 0, new int[n]); // 深さは最大n-1 PrintWriter pw = new PrintWriter(System.out); for (int i = 0; i < q; i++) { pw.println(ans[i]); } pw.flush(); } static void dfs(int x, int dep, int[] cnt) { List<Integer> qx = qr.get(x); // 入ってきた時点の状態を退避 List<Integer> pre = new ArrayList<>(qx.size()); for (int i : qx) { pre.add(cnt[d[i]]); } for (int i : child.get(x)) { dfs(i, dep + 1, cnt); } cnt[dep]++; // クエリの処理 for (int i = 0; i < qx.size(); i++) { int j = qx.get(i); ans[j] = cnt[d[j]] - pre.get(i); } } }
ここまで62分39秒+0ペナ。372位。
F問題は正解者数からしてもどうせ無理だろうと思い、あまりやる気はなかったが、一応少しは考えてみてやっぱり全くわからず。
残り10分くらいでもう諦めてこれを書き始めていた。
最終結果:ABCDEの5完、62分39秒、378位、パフォーマンス1916相当
レート変動:2013(Unrated)
黄パフォとはいかなかったが久しぶりにABCでまともな結果だったと思う。
ABCがUnratedになって10回ほどになったが、大半が800位以下、下手すると2000位近くとかで、レート通り300位前後だったのが3回しかない状態。
ほんと、ARCが毎週のようにある中でいつまでしぶとく黄色でいられるのやら。