AtCoder Regular Contest 132

コンテスト前のレート:2051
レート通りのパフォーマンスが得られる順位:324位(1400点、47分26秒)

A - Permutation Grid

問題

思考過程
  1. 例1で、5マス塗る行は全列塗られるが、4マス塗る行はどの4列が塗られる?、3マス塗る行は?、\cdotsと調べていくと、4マス塗る行はC_i=1の列以外、3マス塗る行はC_i \leq 2の列以外、\cdotsとなっている。
  2. これを総合すると、R_{r_i} + C_{c_i} \gt Nの場合に黒だと推測できる。
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

問題

思考過程
  1. 問題の制約を満たした元のp_1p_nがどういう並び方になっているのかを考えてみると、全体が昇順か降順(ただしnの次は1とする)になっている円環を任意の1箇所で切ったようなものしかなさそう。
     
  2. 昇順に並んでいる場合、まずは単純に1が先頭に来るまで移動の操作を繰り返す方法が考えられるが、例3を見ると1が後ろの方にある場合は反転→移動を何回か→反転とした方が良いケースもあり得る。
  3. 元が昇順の場合は、上記2通りの小さい方が答え。
     
  4. 元が降順の場合は、先に移動して最後に反転させる手順と、最初に反転させて後は移動のみとする手順の小さい方を答える。(後者が反転→移動を何回か→反転のように、最後に余計な反転が残っていて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

問題

思考過程
  1. dが小さいので、「dp[i][k]:=i番目まで見て、(i-d)(i+d)で使用済みの値の集合がkである通り数」みたいなDPができる?
  2. でも範囲が1つずつずれていくのとか、端の方とかを考えると簡単に実装できる気がしない。
  3. でも他に思い付かないので頑張って実装する。
     
  4. 基本的な遷移は、a_i=-1の場合は(i-d)(i+d)の内集合に含まれていない値を1つ採用し、a_i \neq -1の場合はa_iが集合に含まれていなければそれを採用する形。(後から見るとi-d \leq a_i \leq i+dであるかチェックするのを忘れているが、下記7.だけで本当に足りているのだろうか・・・)
     
  5. 先頭からd+1番目までは1を選べるので、集合を表す値kのビットをずらさず処理していく。
  6. 以降は、初めkの最下位ビットを1と対応させていたのを、2, 3, \cdotsとずらしていく。
  7. 上記で最下位ビットの対応を12と変える際には、1は使用済みでなければならないため、最下位ビットが立っていることをチェックする。

以下のソースで、map.keySet()分ループしているfor文の中身は、a[i]=-2の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実装するのはいつも遅いし仕方ない。