AtCoder Regular Contest 151

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

A - Equal Hamming Distances

問題

思考過程
  1. Uを全て0としてみると、S, Tそれぞれとのハミング距離は1の数となる。
  2. S, Tが異なる桁についてUの該当桁を1に変えると、一方が距離1減ってもう一方が1増える。
  3. つまりハミング距離の差は2ずつ縮まるので、偶奇が一致していない場合は-1
  4. あとはS, T1が多い方が1で少ない方が0になっている桁を後ろから必要な個数だけ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));
        int n = Integer.parseInt(br.readLine());
        char[] s = br.readLine().toCharArray();
        char[] t = br.readLine().toCharArray();
        br.close();

        int cs = 0;
        int ct = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == '1') cs++;
            if (t[i] == '1') ct++;
        }

        if (cs % 2 != ct % 2) {
            System.out.println(-1);
            return;
        }
        int d = ct - cs;

        char[] u = new char[n];
        Arrays.fill(u, '0');
        for (int i = n - 1; i >= 0; i--) {
            if (d == 0) {
                break;
            }
            if (d < 0 && s[i] == '1' && t[i] == '0') {
                u[i] = '1';
                d += 2;
            }
            if (d > 0 && s[i] == '0' && t[i] == '1') {
                u[i] = '1';
                d -= 2;
            }
        }
        System.out.println(u);
    }
}

ここまで5分18秒+0ペナ。125位。


B - A < AP

問題
以下、条件を満たすことを問題名を元にA \lt APであると言うことにする。

思考過程
  1. iP_iを連結したグラフの連結成分に分けて考える。
  2. 全ての連結成分がA \leq APであり、なおかつ最低1つの連結成分がA \lt APである必要がある?
  3. とすれば、「各連結成分についてA \leq APである通り数を求めた総積」から「各連結成分についてA = APである通り数(=M)を求めた総積」を引けばよさそう。と思ったりするが例3が合わない。
  4. 既に経過時間30分を過ぎているが、どう駄目なのか全然わからないので愚直を書いて比較してみる。
     
  5. 初めの方の連結成分でA \lt APが確定したら、それより後ろの連結成分はM^{size}通り全てOKだった。
  6. 連結成分に含まれている最小indexの小さい順に調べていく必要がありそう?(何故かは確認できていないが、後から試した限りだと順番は関係ないらしい)
  7. 結局桁DPに近いような雰囲気で、i番目の連結成分まで見た時点でのA \lt APの通り数とA = APの通り数を持ちながら計算していくことができそう。
  8. 1時間を過ぎてもまだ合わず飛ばしかけたが、もう一度見直したら実装ミスを発見することができ、なんとかAC。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

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]);
        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();

        System.out.println(solve(n, m, p));
    }

    static long solve(int n, int m, int[] p) {
        int mod = 998244353;
        DSU uf = new DSU(n);
        for (int i = 0; i < n; i++) {
            uf.merge(i, p[i]);
        }

        long gt = 0; // A < APの通り数
        long eq = 1; // A = APの通り数
        List<List<Integer>> grps = uf.groups();
        // 6. 最小index順にしようとしたが、不要だった
        PriorityQueue<Obj> que = new PriorityQueue<>((o1, o2) -> o1.a - o2.a);
        for (int i = 0; i < grps.size(); i++) {
            Obj o = new Obj();
            o.i = i;
            o.a = grps.get(i).get(0);
            que.add(o);
        }
        while (!que.isEmpty()) {
            Obj o = que.poll();
            List<Integer> g = grps.get(o.i);
            int size = g.size();
            // 総数
            long v1 = power(m, size, mod);
            // 総数からA = AP分を引く
            long v2 = (v1 - m + mod) % mod;
            if (v2 % 2 == 1) {
                v2 += mod;
            }
            // さらにその半分がA < APを満たす
            long v3 = v2 / 2;

            gt *= v1;
            gt %= mod;
            gt += eq * v3 % mod;
            gt %= mod;
            eq *= m;
            eq %= mod;
        }
        return gt;
    }

    static class Obj {
        int i, a;
    }

    // 以下ライブラリ

    static long power(long x, long n, int m) {
        if (n == 0) {
            return 1;
        }
        long val = power(x, n / 2, m);
        val = val * val % m;
        if (n % 2 == 1) {
            x %= m;
            val = val * x % m;
        }
        return val;
    }
}

// 以下ACLを移植したDSU

提出
ここまで65分06秒+ペナ。846位。



とりあえずC~Eの問題を見る。

CはGrundy数を求めることになりそうだが、どうやって求めるのかぱっと見では見当が付かない。
Dは問題が頭に入ってこない。
Eは割とシンプルな見た目。最長共通部分の長さを求めるだけでは?

配点も考慮してEを頑張ることにする。


E - Keep Being Substring

問題
X, Yに共通部分がない場合が問題であることに気付けず。
共通部分がある場合だけなら時間内にできていたが、ない場合について終了後に簡単に解説を見て、さらに30~40分ほどかけてやっとAC。

思考過程
  1. ASuffix ArrayとLCP Arrayを求めておく。
  2. MP法でAXYが出てくるindexを求めておく。
  3. SA[i]とSA[i+1]の一方がX内でもう一方がY内の場合のLCPA[i]や、SA[i]X, Y両方内の場合の末尾までの長さを候補として、それらの最大値を求める? →WA
     
  4. X, -1, Yを繋げた数列に対してSuffix ArrayとLCP Arrayを求める。
  5. SA[i]とSA[i+1]の一方がX内でもう一方がY内の場合のLCPA[i]の最大値を求める。 →最大値が0以外の場合はAC
     
  6. 最大値が0の場合は、Aの中でX, ?, ?, ?, Yのような構造をしているとしたら、全てのX部分を始点としたBFS(遷移は左右に1つ動く)をして?を何個経由してYにたどり着くかを求めればよい?
  7. と思ったが、遷移は左右に動くだけではなく、同じ値同士はコスト0でワープできるような構造をしている。
    例えばA=\{3, 1, 4, 1, 5, 7, 2\}X=\{3, 1\}の場合、\{3, 1\}\{1\}\{1, 5\}のようなことができる。
  8. 結局、indexベースではなく値ベースでBFSを行うことになる。Aで隣同士である値の間に辺を張ったグラフでXに含まれる値からYに含まれる値までの最短距離を求める。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Queue;
import java.util.Set;
import java.util.function.Consumer;
import java.util.function.IntBinaryOperator;

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[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(sa[i]) - 1;
        }

        int p = Integer.parseInt(br.readLine());
        sa = br.readLine().split(" ");
        int[] x = new int[p];
        for (int i = 0; i < p; i++) {
            x[i] = Integer.parseInt(sa[i]) - 1;
        }

        int q = Integer.parseInt(br.readLine());
        sa = br.readLine().split(" ");
        int[] y = new int[q];
        for (int i = 0; i < q; i++) {
            y[i] = Integer.parseInt(sa[i]) - 1;
        }
        br.close();

        // 4. {x, -1, y}を繋げた配列
        int[] xy = new int[p + q + 1];
        for (int i = 0; i < p; i++) {
            xy[i] = x[i];
        }
        xy[p] = -1;
        for (int i = 0; i < q; i++) {
            xy[p + 1 + i] = y[i];
        }
        int[] arr = StringAC.suffixArray(xy);
        int[] la = StringAC.lcpArray(xy, arr);

        // 5. LCPの最大値
        int max = 0;
        for (int i = 0; i < p + q; i++) {
            if (arr[i] < p && arr[i + 1] > p) {
                max = Math.max(max, la[i]);
            }
            if (arr[i] > p && arr[i + 1] < p) {
                max = Math.max(max, la[i]);
            }
        }

        if (max == 0) {
            // xに含まれる値
            Set<Integer> setx = new HashSet<>();
            for (int i = 0; i < p; i++) {
                setx.add(x[i]);
            }
            // yに含まれる値
            Set<Integer> sety = new HashSet<>();
            for (int i = 0; i < q; i++) {
                sety.add(y[i]);
            }

            // a[i - 1]とa[i]に辺を張る
            List<Set<Integer>> list = new ArrayList<>(n);
            for (int i = 0; i < n; i++) {
                list.add(new HashSet<>());
            }
            for (int i = 1; i < n; i++) {
                list.get(a[i - 1]).add(a[i]);
                list.get(a[i]).add(a[i - 1]);
            }

            int[] d = new int[n];
            Arrays.fill(d, -1);
            // xに含まれる値が始点
            Queue<Integer> que = new ArrayDeque<>();
            for (int i = 0; i < n; i++) {
                if (setx.contains(a[i])) {
                    que.add(a[i]);
                    d[a[i]] = 0;
                }
            }
            // BFS
            while (!que.isEmpty()) {
                int cur = que.poll();
                for (int next : list.get(cur)) {
                    if (d[next] == -1) {
                        que.add(next);
                        d[next] = d[cur] + 1;
                        // yに含まれる値にたどり着いた
                        if (sety.contains(next)) {
                            int min = d[next] - 1;
                            System.out.println(p + q + 2 * min);
                            return;
                        }
                    }
                }
            }
        } else {
            int ans = (p - max) + (q - max);
            System.out.println(ans);
        }
    }
}

// 以下ACLを移植した文字列アルゴリズム詰め合わせのやつ

提出



終結果:ABの2完800点、65分06秒、891位、パフォーマンス1455
レート変動:1971→1929(-41)


今回はA問題で全然詰まらなかったのにBとCが・・・。
まあ絶対解かなければというプレッシャーさえなければE問題は十分楽しめたんだけど。

1900台にいる時間が長くなってきた。
まだ黄色に戻るの絶対無理だとまでは思っていないけど、惰性で参加するのもほんといつまで続けていられるんだろう・・・。