- A - Signed Difficulty
- B - Same Name
- C - Many Balls
- D - Pair of Balls
- E - Amusement Park
- F - Max Sum Counting
- G - 01Sequence
コンテスト前のレート:2034
(Ratedだとしたら)レート通りのパフォーマンスが得られる順位:309位(2600点、100分19秒)
A - Signed Difficulty
思考過程
- 入力を文字列で受け取って、普通は" "(半角スペース)で分割することがほとんどだが、この問題では"."(半角ピリオド)で
に分割する。
- あとは問題文の通り条件分岐を行う。
- としたかったが、何故か分割後の文字列配列が要素数
ではなく
になってしまう。
- splitメソッドの引数は正規表現であり、"."は任意の
文字を表してしまうため、エスケープする必要があった。
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)); String[] sa = br.readLine().split("\\."); // 4 int x = Integer.parseInt(sa[0]); int y = Integer.parseInt(sa[1]); br.close(); if (y <= 2) { System.out.println(x + "-"); } else if (y <= 6) { System.out.println(x); } else { System.out.println(x + "+"); } } }
ここまで3分35秒+0ペナ。1720位。
B - Same Name
思考過程
- 苗字と名前を英小文字以外の適当な文字で連結した文字列を、Setに追加していく。
- 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(); Set<String> set = new HashSet<>(); for (int i = 0; i < n; i++) { set.add(sc.next() + "-" + sc.next()); } sc.close(); if (set.size() == n) { System.out.println("No"); } else { System.out.println("Yes"); } } }
ここまで4分57秒+0ペナ。645位。
C - Many Balls
思考過程
- ABC188-Fなどのように、
を
にする方向で手順を求め、最後に逆順にして出力する。
- 現在の数
が
で割れるなら割り、そうでなければ
を引くのが最短手順。
import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); long n = sc.nextLong(); sc.close(); StringBuilder sb = new StringBuilder(); while (n > 0) { if (n % 2 == 0) { sb.append('B'); n /= 2; } else { sb.append('A'); n--; } } sb.reverse(); System.out.println(sb.toString()); } }
ここまで6分50秒+0ペナ。177位。
D - Pair of Balls
問題
ABC139-Eを思い浮べていた。これを探し出して一部コピペできないか検討するのと、普通に一から実装するのとどちらが早いかと一瞬思ったが、普通に一から実装した。
思考過程
- 操作可能な箇所があれば、特に順番は気にせず貪欲に操作してよい。
- 上記の類題では、操作を行えた箇所のみを次のループでの処理対象候補とすることで、計算量を抑えていた記憶があったので、そのような流れをベースにして進めていくことを考える。
- 各筒の次の要素のインデックス(これはListではなくQueueにしておけば不要だった)や、相方となるボールの情報(色と筒の場所)を適切に更新しながら処理していく。
- 最終的に
回処理できたかどうかを判定する。
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; 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 = new int[m]; List<List<Integer>> list = new ArrayList<>(); for (int i = 0; i < m; i++) { List<Integer> l2 = new ArrayList<>(); k[i] = Integer.parseInt(br.readLine()); sa = br.readLine().split(" "); for (int j = 0; j < k[i]; j++) { int a = Integer.parseInt(sa[j]); l2.add(a); } list.add(l2); } br.close(); // キー:色、値:筒index Map<Integer, Integer> map = new HashMap<>(); // 処理対象筒index List<Integer> target = new ArrayList<>(); for (int i = 0; i < m; i++) { target.add(i); } // 各筒の次の要素のindex int[] idx = new int[m]; // 操作回数 int cnt = 0; while (!target.isEmpty()) { List<Integer> next = new ArrayList<>(); // 次回ループの処理対象 for (int i : target) { int e = list.get(i).get(idx[i]); if (map.containsKey(e)) { // 相方がどこかの筒の先頭にある場合 cnt++; int j = map.get(e); idx[j]++; if (idx[j] < k[j]) { next.add(j); } map.remove(e); idx[i]++; if (idx[i] < k[i]) { next.add(i); } } else { // 相方がまだ見つかっていない場合 map.put(e, i); } } target = next; } // 4 if (cnt == n) { System.out.println("Yes"); } else { System.out.println("No"); } } }
ここまで22分29秒+0ペナ。330位。
E - Amusement Park
問題
オーバーフローで1ペナ。
思考過程
- PriorityQueueを使うだけでは・・・と思ったが、
では駄目な制約だった。
を降順にソートし、例1であれば、
~
が
個ずつ、
~
が
個ずつ、
~
が
個ずつあると捉えて、大きい値を使えるだけ使うようにする。
- 例えば
で
より大きい値を合計
回使用済みの場合、次は
~
の値を
回ずつ使っていきたい。
ならば、上記の範囲の値を全部使い切って、次の
~
の範囲の処理に移る。
- そうでなければ、残数を
として、
~
までは
個ずつ、余った
~
個は
となる。
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; 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 k = Integer.parseInt(sa[1]); sa = br.readLine().split(" "); long[] a = new long[n + 1]; for (int i = 0; i < n; i++) { a[i] = Integer.parseInt(sa[i]); } br.close(); Arrays.sort(a); reverse(a); long ans = 0; int sum = 0; for (int i = 1; i <= n; i++) { long d = a[i - 1] - a[i]; long d2 = d * i; if (sum + d2 <= k) { // 4 long val = (a[i - 1] + a[i] + 1) * d2 / 2; ans += val; sum += d2; } else { // 5 int rem = k - sum; int t = rem / i; long val = (a[i - 1] * 2 - t + 1) * t * i / 2; ans += val; rem %= i; val = (a[i - 1] - t) * rem; ans += val; break; } } System.out.println(ans); } // 以下ライブラリ static void reverse(long[] a) { for (int i = 0; i < a.length / 2; i++) { long tmp = a[i]; a[i] = a[a.length - 1 - i]; a[a.length - 1 - i] = tmp; } } }
ここまで35分37秒+1ペナ。280位。
F - Max Sum Counting
問題
の方も
と同じインデックスの集合内の最大値だと勘違いして30分近く溶かした。。。
正しい問題を認識してからACするまでは10分くらい。
思考過程
- 何らかの順でソートして、前から順に見ていける形にできないか考える。
の方は、合計として現れる値を数え上げるならやっぱりナップサックDPのようなことはするのではないかと思う。
の昇順にペアソートした上で、
についてナップサックDPを行い、「
番目までで合計が
の通り数」とした内の
~
のみを答えに足していけばよさそう。
- なお、
番目について答えに足す値は、
を使う場合(つまり
を使う場合)の通り数のみとすることで、重複を排除する。
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; 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]); sa = br.readLine().split(" "); Obj[] arr = new Obj[n]; for (int i = 0; i < n; i++) { Obj o = new Obj(); o.a = Integer.parseInt(sa[i]); arr[i] = o; } sa = br.readLine().split(" "); for (int i = 0; i < n; i++) { arr[i].b = Integer.parseInt(sa[i]); } br.close(); int mod = 998244353; Arrays.sort(arr, (o1, o2) -> o1.a - o2.a); long ans = 0; long[] dp = new long[5001]; dp[0] = 1; for (int i = 0; i < n; i++) { Obj o = arr[i]; long[] wk = new long[5001]; for (int j = 5000 - o.b; j >= 0; j--) { wk[j + o.b] += dp[j]; dp[j + o.b] += dp[j]; dp[j + o.b] %= mod; } for (int j = 1; j <= o.a; j++) { ans += wk[j]; } ans %= mod; } System.out.println(ans); } static class Obj { int i, a, b; } }
ここまで74分27秒+1ペナ。515位。
G - 01Sequence
問題
実装ミスにより、無限ループが発生するケースがあって1ペナ。
思考過程
- 区間スケジューリング問題のような要領で、
の降順でソートして
に満たない分を右から順に
で埋めるようにすれば条件は満たせそう。
- ただし、単純にやれば
なので、右から順に埋める際に既に
にしたところは見ない工夫をしたい。
~
の範囲に既にある
の数は、BITを使って取得する。
- 二度見ないためには、次に調べるべきindexを管理する配列を用意し(
を
で初期化)、例えば
~
の範囲を
に変えたら、
を
にする更新を行う。
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; 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]); Obj[] arr = new Obj[m]; for (int i = 0; i < m; i++) { sa = br.readLine().split(" "); Obj o = new Obj(); o.l = Integer.parseInt(sa[0]) - 1; o.r = Integer.parseInt(sa[1]); o.x = Integer.parseInt(sa[2]); arr[i] = o; } br.close(); // rの降順、xの降順 Arrays.sort(arr, (o1, o2) -> { if (o1.r != o2.r) { return o1.r - o2.r; } return o2.x - o1.x; }); FenwickTree ft = new FenwickTree(n); int[] ans = new int[n]; int[] next = new int[n + 1]; for (int i = 1; i < n; i++) { next[i] = i - 1; } for (Obj o : arr) { long sum = ft.sum(o.l, o.r); // 3 if (sum < o.x) { long rem = o.x - sum; int idx = o.r - 1; while (rem > 0) { if (ans[idx] == 0) { ans[idx] = 1; ft.add(idx, 1); rem--; } idx = next[idx]; } next[o.r] = idx; // 4 } } StringBuilder sb = new StringBuilder(); for (int i = 0; i < n; i++) { sb.append(ans[i]).append(' '); } sb.deleteCharAt(sb.length() - 1); System.out.println(sb.toString()); } static class Obj { int l, r, x; } } // 以下ACLを移植したFenwickTree
提出
ここまで93分57秒+2ペナ。312位。
ACを見届けていたら残り5分もなく、正解者数からして解ける気は全くしなかったので、H問題は開くこともせず。
最終結果:ABCDEFGの7完、103分57秒、330位、パフォーマンス2008相当
レート変動:2034(Unrated)
誤読とペナさえなければほぼ2400出ていたくらいのスピードで解けたので、まあ上出来だったかなと思う。
でもAとDはもっと早く解きたかった。