第18回アルゴリズム実技検定 (PAST 018)

Wed, Apr 16, 2025

G - 二回の交換

$A = B$ のとき、$A_1, A_2$ を交換する操作を2回行えば良い。

$A \neq B$ のときを考える。交換操作を行うする左端の index として $i < j$ なる $i,j$ を選ぶ。このとき $(A_i, A_{i+1})$ の交換と $(A_j, A_{j+1})$ の交換操作は一般に非可換である。一方で今回の問題では交換回数が2回なので次の2通りの置換のみ考えれば十分である。

\begin{eqnarray*} \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix} \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} \end{eqnarray*}

題意を満たすような操作方法は以下の3通りである

(1) $i$ が小さい方から処理していき $A_i \neq B_i$ なる部分があれば $(A_i, A_{i+1})$ を交換する操作を繰り返し操作回数が2回かつ、最終的に $A = B$ となる
(2) $i$ が大きい方から処理しておき $A_i \neq B_i$ なる部分があれば $(A_{i-1}, A_{i})$ を交換する操作を繰り返し操作回数が2回かつ、最終的に $A = B$ となる
(3) 一度の交換で $A = B$ となり、かつ、操作前または操作後の数列において同じ数字が連続している部分が存在している

(2) に関しては数列を反転させて (1) と同じ操作を行えば良い。

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

    int n;
    cin >> n;
    vint a(n), b(n);
    rep(i, n) cin >> a[i];
    rep(i, n) cin >> b[i];

    auto check = [](vint x, vint y) -> bool {
        int m = x.size();
        int cont = 0;
        int cnt = 0;

        if (x == y)
            return true;
        rep(i, m) {
            if (i + 1 < m)
                cont += x[i] == x[i + 1];
            if (x[i] == y[i])
                continue;
            if (i + 1 < m) {
                cnt++;
                swap(x[i], x[i + 1]);
            }
        }
        if (x != y)
            return false;
        if (cnt > 2)
            return false;
        if (cnt == 2)
            return true;
        if (cnt == 1 && cont > 0) {
            // 連続している部分を先んじて swap しておく or 操作が終わった後に連続している部分があったらその部分を swap する
            return true;
        }
        return false;
    };

    bool ok = false;
    ok = ok || check(a, b);
    reverse(all(a));
    reverse(all(b));
    ok = ok || check(a, b);
    yesno(ok);
}

H - Cを探せ

$(i, j)$ を左上、$(i+L, j+L)$ の正方形の中に C があるか判定する。 $(i,j) \in [i,i+L+1) \times [j,j+L+1)$ の領域に含まれる # の個数を $O$ 、$(i,j) \in [i+1,i+L) \times [j+1,j+L)$ に含まれる # の個数を $I$ とする。 $I = 0$ かつ $O = 3L-2$ のとき、レベル $L-2$ の C が存在する。

個数の判定は二次元累積和を用いて判定する。

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

    int N;
    cin >> N;
    vector<string> grid(N);
    rep(i, N) cin >> grid[i];

    vvint cumsum(N + 1, vint(N + 1));
    rep(i, N) rep(j, N) cumsum[i + 1][j + 1] = grid[i][j] == '#';
    rep(i, N + 1) rep(j, N) cumsum[i][j + 1] += cumsum[i][j];
    rep(i, N) rep(j, N + 1) cumsum[i + 1][j] += cumsum[i][j];

    auto num_sharp = [&](int si, int sj, int ti, int tj) -> ll {
        ll ret = 0;
        ret = cumsum[ti][tj];
        ret -= cumsum[si][tj];
        ret -= cumsum[ti][sj];
        ret += cumsum[si][sj];
        return ret;
    };

    ll ans = 0;
    rep2(sz, 3, N + 1) {
        rep(i, N) {
            rep(j, N) {
                if (i + sz > N || j + sz > N)
                    continue;

                ll outside = num_sharp(i, j, i + sz, j + sz);
                ll inside = num_sharp(i + 1, j + 1, i + sz - 1, j + sz);

                if (inside)
                    continue;

                if (outside == sz * 3 - 2)
                    chmax(ans, sz - 2);
            }
        }
    }

    cout << ans << endl;
}

I - 改行コード

カーソルが右に動くのは type 1 のときだけで、その他のときは左に動く。

空文字列から始めて以下の操作を行う

type 1 のとき
- $c$ を文字列に追加
type 2 のとき
- 文字列を deque の先頭に追加して、新たな空文字列を作る
type 3 のとき
- 文字列を deque の先頭に追加して deque を queue に追加
- 新たな空文字列を作る

カーソルが上に移動することはないから、$H = \text{deque の数}$, $W = (\text{現在見ている文字列の長さ}) + 1$ である。

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

    int Q;
    cin >> Q;

    vector<deque<string>> editor(1);
    editor[0].push_back("");
    rep(_, Q) {
        int t;
        cin >> t;
        if (t == 1) {
            char c;
            cin >> c;
            editor.back()[0].push_back(c);
        } else if (t == 2) {
            editor.back().push_front("");
        } else {
            editor.push_back(deque<string>({""}));
        }
    }

    int H = editor.size(), W = editor.back().front().size() + 1;
    cout << H << ' ' << W << endl;
    rep(i, H) {
        cout << "# ";
        for (string s : editor[i])
            cout << s;
        cout << endl;
    }
}

J - 反転ゲーム

盤面の構成、どのマスにいるかということを合わせて一つの状態として見たとき、マスを移動すると別の状態に遷移しているとみなすことができる。よってこれは初期状態からマス目が全て白の状態への最短経路問題に帰着できる。盤面の構成が $2^{HW}$ 通り、どのマスにいるかで $HW$ 通りで、合計 $2^{HW} HW$ 通りの状態がある。$H, W$ \leq 4$ なので多くとも状態数は $2^{16} \cdot 16 = 1048576$ 通りである。またある状態から次の状態への遷移方法はせいぜい4通りであるため辺の数もノード数と同じオーダーである。移動のたびにコスト1 であるダイクストラ、または単に BFS で解くことができる。

盤面の状態は bit 列として持っておいて、移動先のマスに相当する bit 列と XOR を取ることで遷移先の状態を求めることができる。

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

    ll H, W;
    cin >> H >> W;
    vector<string> grid(H);
    rep(i, H) cin >> grid[i];

    ll start = 0;
    rep(i, H) rep(j, W) {
        ll x = i * W + j;
        if (grid[i][j] == '#')
            start |= 1ll << x;
    }

    vector<vvll> dist(1ll << (H * W), vvll(H, vll(W, INF)));
    dist[start][0][0] = 0;

    vint di = {0, 1, 0, -1};
    vint dj = {1, 0, -1, 0};

    using P = tuple<ll, ll, ll, ll>;
    queue<P> pq;
    pq.push({0, start, 0, 0});
    while (pq.size()) {
        auto [cost, now, i, j] = pq.front();
        pq.pop();

        if (dist[now][i][j] < cost)
            continue;

        rep(d, 4) {
            ll ni = i + di[d], nj = j + dj[d];
            if (clamp(ni, 0ll, H - 1) != ni || clamp(nj, 0ll, W - 1) != nj)
                continue;

            ll nx = now ^ (1ll << (ni * W + nj));
            if (dist[nx][ni][nj] <= cost + 1)
                continue;

            dist[nx][ni][nj] = cost + 1;
            pq.push({dist[nx][ni][nj], nx, ni, nj});
        }
    }

    ll ans = INF;
    rep(i, H) rep(j, W) chmin(ans, dist[0][i][j]);

    cout << ans << endl;
}

K - 2で割り切れる回数

L - 書き換え

遅延セグメント木を使う問題かと思ったが解説読んだらそうではなかったらしい

using S = long long;
using F = long long;

const S INF = 8e18;
const F ID = 8e18;

S op(S a, S b) {
    return std::max(a, b);
}
S e() {
    return -INF;
}
S mapping(F f, S x) {
    return (f == ID ? x : f);
}
F composition(F f, F g) {
    return (f == ID ? g : f);
}
F id() {
    return ID;
}

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

    int N, Q;
    cin >> N >> Q;

    vector<pair<string, ll>> sp(N);
    rep(i, N) {
        string s;
        ll p;
        cin >> s >> p;
        sp[i] = {s, p};
    }

    vector<pair<ll, int>> qsort;
    rep(i, Q) {
        ll t;
        cin >> t;
        qsort.push_back({t, i});
    }
    sort(all(qsort));

    vll q(Q);
    rep(i, Q) {
        q[i] = qsort[i].first;
    }

    lazy_segtree<S, op, e, F, mapping, composition, id> seg(q);

    int neg = 0;
    for (auto [s, p] : sp) {
        if (s == "NEGATE") {
            neg = 1 - neg;
            continue;
        }
        if (neg)
            p *= -1;
        int t = seg.max_right(0, [&](S x) -> ll {
            return x <= p;
        });
        if (s == "CHMIN" && neg || s == "CHMAX" && !neg) {
            seg.apply(0, t, p);
        } else {
            seg.apply(t, Q, p);
        }
    }

    vll ans(Q);
    rep(i, Q) {
        ll x = seg.get(i);
        ll sign = 1;
        if (neg)
            sign = -1;
        ans[qsort[i].second] = x * sign;
    }
    for (ll x : ans)
        cout << x << '\n';
}

M - グループ分け

解説読んで convolution の問題だと知りその時点で理解を諦めた

第18回 アルゴリズム実技検定 (PAST 018)

Table of Contents