Codeforces Round #641 (Div. 1 C / Div 2. E) Kamil and Making a Stream

問題: Problem - E - Codeforces

公式解説: Codeforces Round #641 Editorial - Codeforces

問題概要

$n \times m (1 \leq n, \mathit{m} \leq 1000)$ の行列 $A$ が与えられる。$i$ 行 $j$ 列の要素は $a_{i, j}$ であり，0 なら白，1 なら黒である。

この行列のすべての要素に対して，以下の操作を行う。

• 上下左右に同じ色が存在しない要素の色はそのままにする
• 上下左右のいずれかに同じ色が存在する要素の色を反転する

この操作について，次の $t (\leq 10^5)$ 個のクエリに答えよ。

• すべての要素に対して操作を$p$ 回繰り返した後の $i$ 行 $j$ 列の要素の色を答えよ。

解法概要

今回の問題では，色がそのままになる条件が厳しく，色が変わる条件は緩い。条件に従って Sample 3 なんかを手でやってみると，操作を行っても色が変わらないエリアと操作ごとに色が変わるエリアがあると考えたときに，色が変わるエリアが徐々に広がる。

操作前	1回目の操作後	2回目の操作後
01011 10110 01101 11010 10101	01000 10000 00001 00010 00101	11111 11111 11111 11110 11101

3回目の操作後	4回目の操作後	5回目の操作後
00000 00000 00000 00000 00001	11111 11111 11111 11111 11111	00000 00000 00000 00000 00000

もう少し詳しく見てみると，「隣に同じ色の要素がある (= 次の操作で色が変わる)」要素との最短距離に応じて，色が変わらない状態→色が毎回変化する状態へと変化するタイミングが決まることがわかる。

数学的帰納法っぽく証明してみる。

隣に同じ色がある要素との最短距離が 0 ，つまり自分の隣に自分と同じ色があるような要素の場合はあと 0 回で 毎回色が変化する状態」になる。つまりもうすでに色が毎回変化する状態になっている。

また，隣に同じ色がある要素との最短距離が $d$ の要素 $a_{i, j}$があり，$d$ 回の操作後に毎回色が変化するようになると仮定する。さらに，その要素の隣の要素に，隣に同じ色がある要素との最短距離が $d+1$ の要素 $a_{i', j'}$があったとする。

$d$ 回の操作後，$a_{i, j}$ はまだ色は変化していないが， $d+1$ 回目の操作後から毎回色が変化する，つまり4近傍に色が同じ色要素が存在する状態になっている。一方，$a_{i', j'}$ はまだ色が変化しておらず，まだ4近傍に同じ色の要素がないので $d+1$ 回目の操作後も色が変化しない。 (仮定より，$a_{i, j} \neq a_{i', j'}$ が必ず成り立っている)

したがって，「隣に同じ色の要素がある」要素との最短距離が「その要素が後何回の操作で色が毎回変化する状態になるか」である。

クエリの数より，クエリの度に「隣に同じ色の要素がある」要素からの距離を求めていては間に合わない。また，「隣に同じ色の要素がある」要素は最大 $10^6$ 個あるので，BFS を $10^6$ 回やって距離の最小値を取るわけにもいかない。

しかしこの場合は，「隣に同じ色の要素がある」要素すべてからの距離がわかる必要はない。最短距離さえ分かっていれば良い。そのため，BFS を始めるときに「隣に同じ色の要素がある」要素をすべて queue に突っ込み，最短距離がわかった要素は二度訪れないようにすれば良い (多点 BFS や多始点 BFS などと言われている) 。

ソースコード

#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>

using namespace std;

using ll =  long long;
using Pii = pair<int, int>;

constexpr ll LINF = 1LL << 60;
constexpr int dyx[4][2] = {
    { 0, 1}, {-1, 0}, {0,-1}, {1, 0}
};

int n, m; ll t;

bool check(int y, int x) {
    return (0 <= y) && (y < n) && (0 <= x) && (x < m);
}

int main() {
    cin >> n >> m >> t;
    vector<vector<ll>> a(n, vector<ll>(m));
    for(int i=0;i<n;++i) {
        string s;
        cin >> s;
        for(int j=0;j<m;++j) {
            a[i][j] = (s[j] - '0');
        }
    }

    vector<vector<ll>> dist(n, vector<ll>(m, LINF));
    queue<Pii> que;
    for(int i=0;i<n;++i) {
        for(int j=0;j<m;++j) {
            for(int k=0;k<4;++k) {
                int y = i + dyx[k][0], x = j + dyx[k][1];
                if(check(y, x) && a[i][j] == a[y][x]) {
                    dist[i][j] = 0;
                    que.emplace(i, j);
                    break;
                }
            }
        }
    }

    while(!que.empty()) {
        Pii p = que.front(); que.pop();
        for(int k=0;k<4;++k) {
            int y = p.first + dyx[k][0], x = p.second + dyx[k][1];
            if(check(y, x) && dist[y][x] == LINF) {
                dist[y][x] = dist[p.first][p.second] + 1;
                que.emplace(y, x);
            }
        }
    }

    int y, x; ll p;
    for(int i=0;i<t;++i) {
        cin >> y >> x >> p;
        --y; --x;
        cout << (a[y][x] + max(0LL, p-dist[y][x])) % 2 << "\n";
    }

}

所感

コンテスト中に解けなかった問題をコンテスト後に自力 AC すると悔しいことが知られている。

それはそれとして，問題自体は好きです。

第二回アルゴリズム実技検定 (PAST) O - 可変全域木

問題: O - Variable Spanning Trees

問題概要

$N ( \leq 10^5)$ 頂点 $M (\leq 10^5)$ 辺の無向グラフが与えられる。$i$ 番目の辺は頂点 $a_i, b_i$ を結び，$c_i$ の重みを持つ。

各辺について，その辺を含む最小の重みの全域木を求め，その重みを出力せよ。

解法概要

「各辺について，その辺を含む最小の重みの全域木」の太字の部分さえなければ，ただの最小全域木問題となる。その場合，UnionFind を使ったクラスカル法などをただ適用するだけで良い。今回の問題でも，注目する辺が最小全域木に初めから含まれる場合はクラスカル法を適用するだけだ。

考えなければならないのは，注目する辺が最小全域木に含まれない場合である。注目する辺を最初に使うようにクラスカル法をアレンジしようとしても，時間計算量 $\mathcal{O}(M^2 \log M)$ (クラスカル法は $\mathcal{O}(M \log M)$ なので) となり TLE してしまう。なんとかして1辺あたり対数時間や定数時間で求めたい。

そこで，最小全域木と「注目する辺を含む最小の重みの全域木」の差分を考えてみる。以下のような全域木があった場合に，辺 (2, 4) を追加で使うことを考えるとしよう。

(画像: GRAPH × GRAPH：競技プログラミングにおけるグラフ可視化サイト のスクショ)

もともと木なので，当然辺 (2, 4) を追加したら閉路ができる。辺 (2, 4) は必ず使うことにすると，他を1辺削除しないといけない。重みを最小にしたいので， (2, 4) を含む閉路 2-1-3-4 の中で，辺 (4, 5) 以外でもっとも重みの大きい辺を取り除くことになる。同様に，辺 (4, 5) を追加することを考える場合には，閉路 4-3-5 の中で (4, 5) 以外でもっとも重みの大きい辺を取り除くことになる。

閉路についてもう少し考えてみると，辺 (a, b) を加えてできる閉路は a - ... - (根からもっとも遠い，a と b の共通祖先 (LCA)) - ... - b のようになっていることがわかる。したがって，この閉路に含まれる辺 (a, b) 以外の辺でもっとも重みの大きい辺の重みは，a と b の LCA を l とすると「a から l までのパスに含まれる辺の最大の重み」と「b から l までのパスに含まれる辺の最大の重み」のうちより大きいほうである。

これは LCA をダブリングで求めるのと同じ要領で求めることができる。つまり，ダブリングによって LCA を求めるときに各頂点の $2^j$ 個上の頂点を持っておくように，頂点 $i$ から頂点 $i$ の $2^j$ 個上の頂点に移動するまでに通る辺の中での最大の重みを持っておけば良い。

ダブリングによって LCA と LCA からその頂点までのパス中の最大重みを求めるのは，前処理 $\mathcal{O}(N \log N)$，LCA・最大重み計算 $\mathcal{O}(\log N)$ でできる。

よって全体での時間計算量が $\mathcal{O}(M \log M + M \log N)$ となり，間に合う。

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>

using namespace std;

using ll =  long long;
using Pll = pair<ll, ll>;
using Pii = pair<int, int>;

constexpr int N_MAX = 100000;

struct Edge {
    int i, from, to;
    ll cost;
    Edge(int i, int from, int to, ll cost): i(i), from(from), to(to), cost(cost) {};
    bool operator < (const Edge& e) const {
        return cost < e.cost;
    }
};

vector<tuple<int, ll>> graph[N_MAX];
vector<Edge> edges;

class UnionFind {
    public:
    int n;
    vector<int> par, rank;

    UnionFind(int n) {
        for(int i=0;i<n;++i) {
            par.push_back(i);
            rank.push_back(0);
        }
    }

    int find(int x) {
        return ((par[x] == x) ? x : par[x] = find(par[x]));
    }

    void unite(int x, int y) {
        x = find(x);
        y = find(y);

        if(x == y) return;

        if(rank[x] < rank[y]){
            par[x] = y;
        }else{
            par[y] = x;
            if(rank[x] == rank[y]) rank[x]++;
        }
        return;
    }

    bool is_same(int x, int y) {
        return find(x) == find(y);
    }
};

class LowestCommonAncestor {
    public:
    int root, n, LOG_V_MAX = 30;
    vector<int> depth;
    vector<vector<int>> parent;
    vector<vector<ll>> max_cost;    // 頂点 i から 2^j 個上のノードまでの辺のうちコストが最大のもののコスト

    LowestCommonAncestor(int root=0, int n=N_MAX): root(root), n(n) {
        depth.assign(n, -1);
        parent.assign(n, vector<int>(LOG_V_MAX, -1));
        max_cost.assign(n, vector<ll>(LOG_V_MAX, 0));
        dfs(root, -1, 0);
        for(int j=1;j<LOG_V_MAX;++j) {
            for(int i=0;i<n;++i) {
                if(parent[i][j-1] == -1) continue;
                parent[i][j] = parent[parent[i][j-1]][j-1];
                max_cost[i][j] = max(max_cost[i][j-1], max_cost[parent[i][j-1]][j-1]);
            }
        }
    }

    void dfs(int node, int par, int d) {
        depth[node] = d;
        parent[node][0] = par;
        for(auto child: graph[node]) {
            int c = get<0>(child);
            if(c == par) continue;
            max_cost[c][0] = get<1>(child);
            cerr << max_cost[c][0] << endl;
            dfs(c, node, d+1);
        }
    }

    ll get_max_cost(int u, int v) {
        if(depth[u] > depth[v]) swap(u, v);
        ll ret = 0LL;
        int depth_diff = depth[v] - depth[u];
        for(int j=0;j<LOG_V_MAX;++j) {
            if(depth_diff & (1 << j)) {
                ret = max(ret, max_cost[v][j]);
                v = parent[v][j];
            }
        }
        if(u == v) return ret;
        for(int j=LOG_V_MAX-1;j>=0;--j) {
            if(parent[u][j] != parent[v][j]) {
                ret = max({ret, max_cost[u][j], max_cost[v][j]});
                u = parent[u][j];
                v = parent[v][j];
            }
        }
        ret = max({ret, max_cost[u][0], max_cost[v][0]});
        return ret;
    }
    
};


int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m, a, b; ll c;
    cin >> n >> m;
    for(int i=0;i<m;++i) {
        cin >> a >> b >> c;
        --a; --b;
        edges.emplace_back(i, a, b, c);
    }
    sort(edges.begin(), edges.end());

    UnionFind uf = UnionFind(n);
    ll mst_cost = 0LL;
    vector<bool> used(m, false);
    for(int i=0;i<m;++i) {
        if(uf.is_same(edges[i].from, edges[i].to)) continue;
        uf.unite(edges[i].from, edges[i].to);
        mst_cost += edges[i].cost;
        graph[edges[i].from].emplace_back(edges[i].to, edges[i].cost);
        graph[edges[i].to].emplace_back(edges[i].from, edges[i].cost);
        used[i] = true;
    }

    vector<ll> ans(m);
    LowestCommonAncestor lca = LowestCommonAncestor(0, n);
    for(int i=0;i<m;++i) {
        if(used[i]) {
            ans[edges[i].i] = mst_cost;
        } else {
            ans[edges[i].i] = mst_cost + edges[i].cost - lca.get_max_cost(edges[i].from, edges[i].to);
        }
    }

    for(int i=0;i<m;++i) cout << ans[i] << endl;
}

所感

えびちゃんの日記 を見る限り，こどふぉで既出らしい。それと，HL 分解を持っていると貼るだけになるらしい。HL 分解は HL 分解でないと解けない問題になかなか出くわさないため勉強モチベが上がらないなぁ……。

公式解説 曰く，第一の想定解はダブリングでもなく HL 分解でもなくオイラーツアー でもなく，並列二分探索のようだけど。せめて並列二分探索解は理解するか。

第二回アルゴリズム実技検定 (PAST) 受検記

4/18 に AtCoder 社主催のアルゴリズム実技検定 (通称 PAST) に参加しました。

リアルタイム受験だったので検定終了直後から早く解法や感想を語りたくてうずうずしていたのですが，通常受験期間が終わるまでぐっとこらえました。

総得点は94点 (O 問題以外の 14 完) で，エキスパートを取得することができました。明らかに問題との相性が良く，上振れを引いた感があります。暖色やそれに準ずる実力の方々はやすやすと満点を取ってしまうでしょうし，非満点エキスパート勢って少ないんじゃないかなと勝手に思っています。

せっかくなので 1 問ずつ感想を書いていきたいと思います。ただし，すでに記憶がほとんどないので受験直後のメモに書いていなかった部分は内容が無になります。各問題のタイトルの後ろにある括弧はリアルタイム受験で私が AC するまでにかかった時間です。

A (0:04:02)

エレベーターを題材にしているだけあって問題文はすっと頭に入ってくるのですが，ソースコードに起こすとこれが意外と短くならない。

地上階が 1F 2F ……でアルファベットが2文字目なのに対して，地下階は B1 B2 ……でアルファベットが1文字目なのは最初間違えそうになりました。

B (0:06:27)

こちらも問題文はすっと入ってきます。A問題と違ってやるべきことも明らか。

一見 A 問題より簡単なようにも見えますが，こちらが B 問題なのは A 問題で必要とされない for ぶんが必要とされるからでしょう。

C (0:12:34)

これもやるべきことが問題文に直接書いてあるタイプの問題。二重ループでシミュレーションできます。

最初 . のところも X で塗りつぶしてしまったのは内緒。

D (0:18:09)

ここから少しだけ複雑になっていきます。

この問題で考慮すべき部分文字列の長さは最大 3 なので，(ありうるすべての部分文字列の開始箇所) × (部分文字列の長さ 1, 2, 3) × (. への置き換えの全パターン (長さ k に対して 2^k 通り)) をすべて試して set に突っ込めば最終的な set の要素数が答えになります。. の置き換えを全パターン試すときは bit 全探索っぽく bit 演算を使うと便利です。1 文字目を 2⁰ の位，2 文字目を 2¹ の位，3文字目を 2² のくらいに対応させればよいです。

E (0:22:27)

言われていることをシミュレーションすればよいのですが， C までのシミュレーションに比べると読解が少し複雑です。

F (0:29:30)

priority_queue を使ったシミュレーション。i日目になったらi日目以降に実施できるタスクを priority_queue に突っ込んで，得られるポイントが大きい順に毎日取り出していけばいいです。

G (0:39:32)

文字列に関するシミュレーション。ありうる最大の文字数が約 ${10}^{10}$ 文字と非常に大きいので，1 文字 1 文字もつ or 文字列をそのままもつと時間もメモリも間に合いません。

$i$ 文字目を一度クエリの計算に使うと $i$ 文字目はお役御免になるので， (文字，文字数) のペアを管理するとよいです。文字を後ろから追加して前から消していくので，queue で管理できます。

H (0:58:34)

なかなかにひどいソースコードですが，dijkstra でぶん殴りました。事前にグラフを作ったりはせず，$n$ が書いてある頂点からは $n+1$ が書いてある頂点のみに遷移する，S は $0$ として，G は $1$ として扱うということをしています。

I (1:09:35)

queue や deque に「次の試合に進出する人」を突っ込んでいって管理します。決勝戦に出た2人は勝っても負けても「最後の試合」は同じになることに注意です。

J (1:17:09)

これ好き。 stack を使っていい感じにシミュレーションする問題です。基本的には 1 文字ずつ stack に突っ込んでいって，) の番になったら ( が出てくるまで stack の上に積まれているものを取り出していけばよいです。

K (1:43:36)

これは最初に $O(N^3)$ のメモ化再帰を書いて詰まってしまいました。

しかし冷静に考えてみると，valid な括弧列というのは

• ( を +1，) を -1 と考えて先頭から足していったとき，途中で負にならない
• 同様に，最後には 0 になる

なので，前から順番に見ていく DP をすればよいです。

許可されている操作が1文字削除と1文字反転であることから，$\mathit{dp}_{i, j}$ ($i$ 文字目まで見ており，上のような考え方で足していったときの和が j) から遷移できるのは $\mathit{dp}_{i, j}, \mathit{dp}_{i, j+1}, \mathit{dp}_{i, j-1}$ の 3 つだけなので，時間計算量 $O(N^2)$ でいけます。

L (2:14:49)

多分セグ木なんてなくても解けるのでしょうけど， ($i$, $A_i$) を乗せたセグ木でぶん殴りました。$K$ 個の値を選びたいので，$i$ (1-indexed) 番目の値の index は ($i-1$ 番目の値の index) + 1 以上 $N - D \times (K-i)$ 以下のはずです。

M (3:09:47)

ゴリゴリと実装をした記憶しかありません。こういう問題はどちらかというと得意な方ですが，解説を書くのは苦手です。

特に好きな料理が提供されない場合に次に何日後に食堂に行くのかはどの社員でも同じ ($L$日後) なので，「ある料理を食べた人は，次に同じ料理を食べるまでに何回食堂に行くことになるのか？」およびそれを 1 週 ( $D$ 日) 分合計したものを事前に計算しておきます。あとはこれを使って (1) 最初に好きな料理を食べる日まで何回食堂に行くか (2) 食堂に行く回数の上限未満の範囲で D 日 1 週の流れを何週繰り替えすか (3) (1) と (2) のあと残った回数で好きな料理が何回食べられるかを計算します。この実装でかなり悩みました。

N (4:28:31)

これもゴリゴリと実装をした記憶しかありません。自分のソースコードを見たところ，どうやら座標圧縮 + セグ木で解いたようですが，何をしているのかいまいちわかりません……。

解いた直後の私のメモ曰く，「登場する座標を軸ごとに全部まとめて座標圧縮！ まではよかったのですが，そのあとは迷走してしまいました。」とのこと。

問題の内容とは全く関係ないですが，これを解ければエキスパート！　というところだったのでドキドキしつつ自分を信じてがむしゃらに実装した問題でした。

O (-:--:--)

解けませんでした。ある頂点からある頂点までのパスに含まれる辺の重みのうち最大のものがわかれば，辺の追加と消していい辺のうち重みが最も大きいものの削除でいける気がしたのですが，肝心のある頂点からある頂点のパスに含まれる辺の重みの最大値の求め方がわかりませんでした。オイラーツアーを使って LCA ちっくにできるかもしれないと思いましたが，まだ実装していません。暖色の方からは結構典型だという意見も見られましたし，復習したら記事にします。 -> 記事にしました 第二回アルゴリズム実技検定 (PAST) O - 可変全域木 - NoiminのNoise