AtCoder Regular Contest 151

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

A - Equal Hamming Distances

問題

思考過程

1. を全てとしてみると、それぞれとのハミング距離はの数となる。
2. が異なる桁についての該当桁をに変えると、一方が距離減ってもう一方が増える。
3. つまりハミング距離の差はずつ縮まるので、偶奇が一致していない場合は。
4. あとはのが多い方がで少ない方がになっている桁を後ろから必要な個数だけにしていく。

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

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

思考過程

1. とを連結したグラフの連結成分に分けて考える。
2. 全ての連結成分がであり、なおかつ最低つの連結成分がである必要がある？
3. とすれば、「各連結成分についてである通り数を求めた総積」から「各連結成分についてである通り数を求めた総積」を引けばよさそう。と思ったりするが例３が合わない。
4. 既に経過時間30分を過ぎているが、どう駄目なのか全然わからないので愚直を書いて比較してみる。
   　
5. 初めの方の連結成分でが確定したら、それより後ろの連結成分は通り全てOKだった。
6. 連結成分に含まれている最小indexの小さい順に調べていく必要がありそう？（何故かは確認できていないが、後から試した限りだと順番は関係ないらしい）
7. 結局桁DPに近いような雰囲気で、番目の連結成分まで見た時点でのの通り数との通り数を持ちながら計算していくことができそう。
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

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

思考過程

1. のSuffix ArrayとLCP Arrayを求めておく。
2. MP法でにやが出てくるindexを求めておく。
3. SAとSAの一方が内でもう一方が内の場合のLCPAや、SAが両方内の場合の末尾までの長さを候補として、それらの最大値を求める？　→WA
   　
4. を繋げた数列に対してSuffix ArrayとLCP Arrayを求める。
5. SAとSAの一方が内でもう一方が内の場合のLCPAの最大値を求める。　→最大値が以外の場合はAC
   　
6. 最大値がの場合は、の中でのような構造をしているとしたら、全ての部分を始点としたBFS（遷移は左右につ動く）をしてを何個経由してにたどり着くかを求めればよい？
7. と思ったが、遷移は左右に動くだけではなく、同じ値同士はコストでワープできるような構造をしている。
   例えば、の場合、→→のようなことができる。
8. 結局、indexベースではなく値ベースでBFSを行うことになる。で隣同士である値の間に辺を張ったグラフでに含まれる値からに含まれる値までの最短距離を求める。

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