ABC 429

状態 $x \in [0, 8)$ である列に対して $i$ 行目から $j$ 行目への遷移にかかる最小コストを $C^x_{i,j}$ と定義する。ここで、$i$ 行目が # で塞がっている場合、任意の $j$ について $C^x_{i,j} = \infty$ とするし、$j$ 行目が # で塞がっている場合、任意の $i$ について $C^x_{i,j} = \infty$ とする。すべてを8通り全ての状態について列挙すると以下のようになる

\begin{align*} C^0 &= \begin{pmatrix}0 & 1 & 2 \\ 1 & 0 & 1 \\ 2 & 1 & 0\end{pmatrix}, & C^1 &= \begin{pmatrix}\infty & \infty & \infty \\ \infty & 0 & 1 \\ \infty & 1 & 0\end{pmatrix}, & \\ C^2 &= \begin{pmatrix}0 & \infty & \infty \\ \infty & \infty & \infty \\ \infty & \infty & 0\end{pmatrix}, & C^3 &= \begin{pmatrix}\infty & \infty & \infty \\ \infty & \infty & \infty \\ \infty & \infty & 0\end{pmatrix}, & \\ C^4 &= \begin{pmatrix}0 & 1 & \infty \\ 1 & 0 & \infty \\ \infty & \infty & \infty\end{pmatrix}, & C^5 &= \begin{pmatrix}\infty & \infty & \infty \\ \infty & 0 & \infty \\ \infty & \infty & \infty\end{pmatrix}, & \\ C^6 &= \begin{pmatrix}0 & \infty & \infty \\ \infty & \infty & \infty \\ \infty & \infty & \infty\end{pmatrix}, & C^7 &= \begin{pmatrix}\infty & \infty & \infty \\ \infty & \infty & \infty \\ \infty & \infty & \infty\end{pmatrix}. \end{align*}

ここで状態 $x$ の $i$ 行目から状態 $y$ の $j$ 行目への遷移コストを $C_{i, j}^{x, y}$ と定義すると

\begin{align*} C_{i,j}^{xy} = \min_{k} \left(C^x_{i,k} + C^y_{k,j} \right)+1 \end{align*}

となる。これは状態 $x$ の $i$ 行目から状態 $y$ の $j$ 行目へ遷移する際、状態 $x$ の $i$ 行目から状態 $x$ の $k$ 行目へ遷移し、列を跨いで状態 $y$ の $k$ 行目へ遷移し、状態 $y$ の $k$ 行目から状態 $y$ の $j$ 行目へ遷移することを意味している。

$C^{xy} = C^x \star C^y$ となる演算子 $\star$ を定義すると、$\star$ は結合法則を満たす。

また

\begin{align*} E = \begin{pmatrix}0 & \infty & \infty \\ \infty & 0 & \infty \\ \infty & \infty & 0\end{pmatrix} \end{align*}

となる単位元 $E$ も存在する。

よって $(\star, E)$ がモノイドなので segment tree に乗せることができる。

各クエリで状態を更新した後、全区間の積を求め、$C_{0,2}$ を答えればよい。

struct S {
    vvll mat;

    S() {
        mat = vvll(3, vll(3, INF));
    }

    S operator*(const S& other) {
        S v;

        rep(i, 3) rep(j, 3) {
            ll t = INF;
            rep(k, 3) {
                // 列を跨ぐ回数分 +1 するのは外でまとめてやる
                chmin(t, mat[i][k] + other.mat[k][j]);
            }
            v.mat[i][j] = t;
        }

        return v;
    }
};

S op(S a, S b) {
    return a * b;
}

S e() {
    S ret;
    ret.mat = {{0, INF, INF}, {INF, 0, INF}, {INF, INF, 0}};
    return ret;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;
    cin >> N;
    vint state(N);

    {
        vector<string> grid(3);
        rep(i, 3) cin >> grid[i];

        rep(j, N) {
            int t = 0;
            rep(i, 3) {
                if (grid[i][j] == '#') t += 1 << i;
            }
            state[j] = t;
        }
    }

    // 状態の行列を事前計算
    vector<S> V(8);
    rep(st, 1 << 3) {
        S tmp;
        rep(i, 3) {
            vll v(3, INF);
            if (st >> i & 1) continue;

            // index, cost
            using P = pair<ll, ll>;
            queue<P> que;
            v[i] = 0;
            que.push({i, 0});

            while (que.size()) {
                auto [id, cost] = que.front();
                que.pop();

                for (auto d : {-1, 1}) {
                    ll nid = id + d;
                    if (clamp(nid, 0ll, 2ll) != nid) continue;
                    if (!(st >> nid & 1) && v[nid] > cost + 1) {
                        v[nid] = cost + 1;
                        que.push({nid, cost + 1});
                    }
                }
            }

            rep(j, 3) tmp.mat[i][j] = v[j];
        }

        V[st] = tmp;
    }

    segtree<S, op, e> seg(N);
    rep(i, N) {
        seg.set(i, V[state[i]]);
    }

    ll Q;
    cin >> Q;
    while (Q--) {
        ll x, y;
        cin >> x >> y;
        x--, y--;

        state[y] ^= 1 << x;
        seg.set(y, V[state[y]]);

        S ret = seg.prod(0, N);

        ll ans = INF;
        chmin(ans, N - 1 + ret.mat[0][2]); // 列を跨ぐ回数は N - 1 回
        if (ans == INF) ans = -1;
        cout << ans << '\n';
    }
}

G. Sum of Pow of Mod of Linear

https://atcoder.jp/contests/abc429/tasks/abc429_g

ABC 429

Table of Contents

A. Too Many Requests

B. N - 1

C. Odd One Subsequence

D. On AtCoder Conference

E. Hit and Away

F. Shortest Path Query

G. Sum of Pow of Mod of Linear