AtCoder Regular Contest 124
コンテスト前のレート:2114
レート通りのパフォーマンスが得られる順位:272位(1900点、125分28秒)
A - LR Constraints
思考過程
- とりあえずとかが通る制約。
- で指定された箇所は通りだが、それ以外の箇所は、最も左、最も右の制限を無視すれば通り自由に決められる。
- 最も左、最も右の制限を取り入れるには、が"R"ならば、カウント配列を用意し、より左に全部、が"L"ならば、より右に全部すればよい。
- このようにして作成できたカウント配列の各要素の積(ただし、で指定された箇所は)を求める。
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 k = sc.nextInt(); int[] c = new int[n]; boolean[] b = new boolean[n]; for (int i = 0; i < k; i++) { String s = sc.next(); int a = sc.nextInt() - 1; if (s.equals("R")) { for (int j = 0; j < a; j++) { c[j]++; } } else { for (int j = a + 1; j < n; j++) { c[j]++; } } b[a] = true; } sc.close(); int mod = 998244353; long ans = 1; for (int i = 0; i < n; i++) { if (!b[i]) { ans *= c[i]; ans %= mod; } } System.out.println(ans); } }
ここまで7分32秒+0ペナ。201位。
B - XOR Matching 2
問題
答えを昇順に出力する必要はないと勘違いして1WA。
思考過程
- これもが通る制約。
- ということで、に~それぞれを対応させた場合のを全部調べる。
- 数列をMap形式<値、登場回数>にしておく。
- そうすると、まずそれぞれのMapのエントリ数が合っていなければ答えはなし。
- 各についてつのMapを突き合せる際は、を構成するの登場回数が全て一致する必要がある。
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Collections; 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)); int n = Integer.parseInt(br.readLine()); // 3 String[] sa = br.readLine().split(" "); Map<Integer, Integer> map1 = new HashMap<>(); for (int i = 0; i < n; i++) { int a = Integer.parseInt(sa[i]); map1.put(a, map1.getOrDefault(a, 0) + 1); } sa = br.readLine().split(" "); Map<Integer, Integer> map2 = new HashMap<>(); for (int i = 0; i < n; i++) { int a = Integer.parseInt(sa[i]); map2.put(a, map2.getOrDefault(a, 0) + 1); } br.close(); // 4 if (map1.size() != map2.size()) { System.out.println(0); return; } List<Integer> list = new ArrayList<>(); Integer[] arr = map1.keySet().toArray(new Integer[0]); int a0 = arr[0]; for (int bi : map2.keySet()) { int x = a0 ^ bi; // 2 if (map1.get(a0) != map2.get(bi)) { continue; } // 5 boolean flg = true; for (int i = 1; i < arr.length; i++) { int a = arr[i]; int b = a ^ x; int cnt = map2.getOrDefault(b, 0); // 登場回数が異なればNG if (cnt != map1.get(a)) { flg = false; break; } } if (flg) { list.add(x); } } PrintWriter pw = new PrintWriter(System.out); pw.println(list.size()); Collections.sort(list); for (int i : list) { pw.println(i); } pw.flush(); } }
ここまで19分51秒+1ペナ。248位。
C問題は解けず。
素因数を上手くばらけさせたいような雰囲気だけ感じるも、単純にで分ける方法しか思いつかず。
D - Yet Another Sorting Problem
問題
C問題が300人に解かれているくらいになっても全然わからなかったので、飛ばしてこれをやることに。
最終的には、もはやC問題を通しても旨味が少ないと思い、こちらに集中することにした。
結果的になんとか通せた。
思考過程はかなりエスパー寄り。
思考過程
- の場合、を境にしてどちらも同じ側の場合は最低回、異なる側の場合は最低回かかる。
- 以下の要素と超の要素で、各要素の最低操作回数の合計が大きい方が答え? →例1での合計がとなり、合わない。
- 手で色々動かしてみると、とをつなげていった連結成分内で移動させることが基本に思えてきたため、とりあえずUnionFindを使ってみる。
- の左側とか右側とかあまり関係なく、連結成分ごとに転倒数を求めてみればなんとなく合っているような? →3/110AC
- の左側⇔右側だけの移動に限らなければ、回ごとにつは確実に合わせることができ、全部ばらばらなら最後の回だけ箇所揃って、回でできる感じ。
- 実験すると、左右にまたがる連結成分ならば、連結成分のサイズ回で揃えられそう。
- 片側だけの連結成分ならば、一時的にもう片方から要素崩して動かすことになるが、連結成分のサイズ回で揃えられそう。 →84/110AC
- 大筋は合っていると信じて、コーナーケースを考える。
- 片側のみの連結成分が左右両方に存在すれば、上記7.の「一時的にもう片方から要素崩して」の部分が、崩すのではなく揃えたい連結成分にとってプラスの操作にでき、結果それぞれの連結成分のサイズの和でよくなりそう。(がつ落ちる)
- 片側のみの連結成分が左右両方につでも存在すれば、全ての片側のみの連結成分についてが落とせる? →88/110AC
- さらに実験を重ねた結果、どうやら片側のみの連結成分は左右からつずつ選んでペアにしないと、を落とせる効果はないようで、ペアにできる分は「連結成分のサイズ」、余りは「連結成分のサイズ」とする。 →AC
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]); int nm = n + m; sa = br.readLine().split(" "); int[] p = new int[nm]; for (int i = 0; i < nm; i++) { p[i] = Integer.parseInt(sa[i]) - 1; } br.close(); // 3 DSU uf = new DSU(nm); for (int i = 0; i < nm; i++) { uf.merge(i, p[i]); } List<List<Integer>> g = uf.groups(); long ans = 0; Queue<Integer> x1 = new ArrayDeque<>(); Queue<Integer> x2 = new ArrayDeque<>(); for (List<Integer> g2 : g) { if (g2.size() > 1) { int min = g2.get(0); int max = g2.get(g2.size() - 1); if (min < n && n <= max) { // 6: 左右にまたがる連結成分 ans += g2.size() - 1; } else if (max < n) { // 左側のみの連結成分 x1.add(g2.size()); } else if (n <= min) { // 右側のみの連結成分 x2.add(g2.size()); } else { // 実装ミス検知用 throw new Exception(); } } } // 11: ペアにできる分 while (!x1.isEmpty() && !x2.isEmpty()) { ans += x1.poll(); ans += x2.poll(); } // 11: 余り while (!x1.isEmpty()) { ans += x1.poll() + 1; } while (!x2.isEmpty()) { ans += x2.poll() + 1; } System.out.println(ans); } } // 以下ACLを移植したDSU
提出
ここまで106分28秒+4ペナ。296位。
Eは一応問題文は読んだが、わけがわからずすぐ閉じた。
Fは開いてもいない。
最終結果:ABDの3完1400点、126分28秒、354位、パフォーマンス1983
レート変動:2114→2101(-13)
2完でパフォ1380ほどになりそうだったことを思えば、十分浅い傷で済んだ。
約数全探索何で出てこなかったかな・・・。
D問題のペナは出す度に前進につながり、必要経費だったと思えるが、B問題のペナはひどすぎる。