AtCoder Regular Contest 132
コンテスト前のレート:2051
レート通りのパフォーマンスが得られる順位:324位(1400点、47分26秒)
A - Permutation Grid
思考過程
- 例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)); int n = Integer.parseInt(br.readLine()); String[] sa = br.readLine().split(" "); int[] r = new int[n]; for (int i = 0; i < n; i++) { r[i] = Integer.parseInt(sa[i]); } sa = br.readLine().split(" "); int[] c = new int[n]; for (int i = 0; i < n; i++) { c[i] = Integer.parseInt(sa[i]); } int q = Integer.parseInt(br.readLine()); int[] x = new int[q]; int[] y = new int[q]; for (int i = 0; i < q; i++) { sa = br.readLine().split(" "); x[i] = Integer.parseInt(sa[0]) - 1; y[i] = Integer.parseInt(sa[1]) - 1; } br.close(); StringBuilder sb = new StringBuilder(); for (int i = 0; i < q; i++) { if (r[x[i]] + c[y[i]] > n) { sb.append('#'); } else { sb.append('.'); } } System.out.println(sb.toString()); } }
ここまで5分45秒+0ペナ。227位。
B - Shift and Reverse
思考過程
- 問題の制約を満たした元の~がどういう並び方になっているのかを考えてみると、全体が昇順か降順(ただしの次はとする)になっている円環を任意の箇所で切ったようなものしかなさそう。
- 昇順に並んでいる場合、まずは単純にが先頭に来るまで移動の操作を繰り返す方法が考えられるが、例3を見るとが後ろの方にある場合は反転→移動を何回か→反転とした方が良いケースもあり得る。
- 元が昇順の場合は、上記通りの小さい方が答え。
- 元が降順の場合は、先に移動して最後に反転させる手順と、最初に反転させて後は移動のみとする手順の小さい方を答える。(後者が反転→移動を何回か→反転のように、最後に余計な反転が残っていて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)); int n = Integer.parseInt(br.readLine()); String[] sa = br.readLine().split(" "); int[] p = new int[n]; for (int i = 0; i < n; i++) { p[i] = Integer.parseInt(sa[i]) - 1; } br.close(); // 1の位置 int s = 0; for (int i = 0; i < n; i++) { if (p[i] == 0) { s = i; break; } } // 元が昇順かどうか boolean flg = true; for (int i = 1; i < n; i++) { if (p[i - 1] + 1 != p[i] && p[i - 1] - n + 1 != p[i]) { flg = false; break; } } int ans1 = 0; int ans2 = 0; if (flg) { ans1 = s; // 移動のみ ans2 = 1 + (n - 1 - s + 1) % n + 1; // 反転、移動、反転 } else { ans1 = (s + 1) % n + 1; // 移動の後反転 ans2 = 1 + (n - 1 - s); // 反転の後移動 } System.out.println(Math.min(ans1, ans2)); } }
ここまで23分28秒+1ペナ。357位。
C - Almost Sorted
思考過程
- が小さいので、「番目まで見て、~で使用済みの値の集合がである通り数」みたいなDPができる?
- でも範囲がつずつずれていくのとか、端の方とかを考えると簡単に実装できる気がしない。
- でも他に思い付かないので頑張って実装する。
- 基本的な遷移は、の場合は~の内集合に含まれていない値をつ採用し、の場合はが集合に含まれていなければそれを採用する形。(後から見るとであるかチェックするのを忘れているが、下記7.だけで本当に足りているのだろうか・・・)
- 先頭から番目まではを選べるので、集合を表す値のビットをずらさず処理していく。
- 以降は、初めの最下位ビットをと対応させていたのを、とずらしていく。
- 上記で最下位ビットの対応を→と変える際には、は使用済みでなければならないため、最下位ビットが立っていることをチェックする。
以下のソースで、map.keySet()分ループしているfor文の中身は、のif内とelse内どちらも完全に同じ。
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.HashMap; 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 d = Integer.parseInt(sa[1]); sa = br.readLine().split(" "); int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = Integer.parseInt(sa[i]) - 1; } br.close(); int mod = 998244353; Map<Integer, Long> map = new HashMap<>(); map.put(0, 1L); // 5 for (int i = 0; i <= d; i++) { Map<Integer, Long> wk = new HashMap<>(); if (a[i] == -2) { int start = Math.max(i - d, 0); int end = Math.min(i + d + 1, n); for (int a2 = start; a2 < end; a2++) { for (int k : map.keySet()) { if ((k >> a2 & 1) == 0) { // a2が集合に含まれていない場合 int next = k + (1 << a2); wk.put(next, (wk.getOrDefault(next, 0L) + map.get(k)) % mod); } } } } else { int a2 = a[i]; for (int k : map.keySet()) { if ((k >> a2 & 1) == 0) { int next = k + (1 << a2); wk.put(next, (wk.getOrDefault(next, 0L) + map.get(k)) % mod); } } } map = wk; } // 6 for (int i = d + 1; i < n; i++) { Map<Integer, Long> wk = new HashMap<>(); if (a[i] == -2) { int start = Math.max(i - d, 0); int end = Math.min(i + d + 1, n) - start; start = 0; for (int a2 = start; a2 < end; a2++) { for (int k : map.keySet()) { if (k % 2 == 0) { // 7. i-d-1が未使用の場合NG continue; } int k2 = k >> 1; // 管理する範囲を1ずらす if ((k2 >> a2 & 1) == 0) { // a2が集合に含まれていない場合 int next = k2 + (1 << a2); wk.put(next, (wk.getOrDefault(next, 0L) + map.get(k)) % mod); } } } } else { int a2 = a[i] - i + d; // a2が0~2dの間かどうか調べた方が安全そう for (int k : map.keySet()) { if (k % 2 == 0) { continue; } int k2 = k >> 1; if ((k2 >> a2 & 1) == 0) { int next = k2 + (1 << a2); wk.put(next, (wk.getOrDefault(next, 0L) + map.get(k)) % mod); } } } map = wk; } int n2 = (1 << (d + 1)) - 1; System.out.println(map.getOrDefault(n2, 0L)); } }
ここまで78分38秒+2ペナ。482位。
Dは適当な貪欲くらいはしておきたいと思ったが、それもやり方整理できなくて実装できず。
先頭0と1を試せばよいことにも気付いていなかったからどちらにしても通すのは厳しそう。
最終結果:ABCの3完1400点、88分38秒、544位、パフォーマンス1754
レート変動:2051→2024(-27)
C問題で臆せずすぐにDP書き始めればもっと早く解けたかな・・・。
まあでもデバッグでひたすらハマり続けるまではしなかったのでこんなもんか。
DP実装するのはいつも遅いし仕方ない。