競プロ参戦記 #35 Decayed Bridges | ABC 120

AtCoder のプログラミングコンテスト ABC 120 に参加しました。3週連続の ABC-only 回です。

競プロ参戦記

この連載記事では、着手した問題の考察を自分なりに書いていきます。

• 問題文はリンク先を参照してください。
• 筆者の回答は Rust (1.15.1) で書いています。
• 前回: 競プロ参戦記 #34 Lazy Faith | ABC 119 - Qiita

AtCoder Beginner Contest 120

問題一覧: https://atcoder.jp/contests/abc120/tasks

A - Favorite Sound

問題概要: A 円支払うと1回、音を聞ける。いま B 円持っていて、最大 C 回まで、可能なかぎり音を聞く。音を聞く回数を求めよ。

考察:

B 円をすべて使うと (B / A) 回音を聞くことができます (端数切り捨て)。この値と C の小さいほうが答えです。

筆者の回答 (AC): https://atcoder.jp/contests/abc120/submissions/4448209

B - K-th Common Divisor

問題概要: 正の整数 A と B を両方とも割り切る正の整数のうち、K 番目に大きいものを求めよ。

考察:

数学的に見える問題ですが、A, B ≤ 100 なので全探索できます。

A, B を両方とも割り切る数、つまり公約数は A, B 以下です。なので調べる範囲は 1 以上 max(A, B) 以下 (最大100個) で十分です。

1 以上 max(A, B) 以下の整数 d を大きい順に列挙し、「d が A と B を両方割り切るか」を判定し、K 番目に true になった d を答えとすればよいです。

筆者の回答 (AC): https://atcoder.jp/contests/abc120/submissions/4447938

C - Unification

問題概要: 0, 1 からなる長さ N の文字列 S が与えられる。S の部分文字列で "01" または "10" となっているものを1つ選んで取り除く、という操作を可能なかぎり繰り返す。取り除かれる文字数を求めよ。

考察:

0 の個数を A、1 の個数を B として、A ≥ B と仮定します。(A < B の場合も同様。)

取り除く操作を1回行うごとに A, B は 1 ずつ減っていきます。そのため、取り除ける文字数は、最大で (2 * B) です。これはあくまで答えの候補の最大値であって、実際に答えになるかは分かりません。実際、どういう操作をしても「1 が余ってしまう」ような文字列を与えられたら、(2 * B) より小さくなります。

例を触っていると、「1 が余る」ということはないことが分かります。A ≥ B かつ B > 0 (文字列中に 1 が含まれる) なら、どこかに取り除ける部分 (1 と 0 が隣接している部分) があります。それを取り除くと、取り除いた後の文字列も A ≥ B という条件を維持しています。これを繰り返せばすべての 1 を取り除けます。

結局、答えは (2 * min(A, B)) です。

筆者の回答 (AC): https://atcoder.jp/contests/abc120/submissions/4445544

D - Decayed Bridges

問題概要: N 個の点と M 本の辺からなる連結グラフがある。連結していない点のペアの個数を不便さと呼ぶ。すべての m (1 ≤ m ≤ M) につき、1 番目から m 番目までの辺を削除したグラフを考え、そのグラフの不便さを求めよ。

考察:

以前、AtCoder の問題を解いていたとき、辺を削除したときに連結成分が増えるかどうかを高速に判定できれば解けそう、でもやり方が分からない、と思って解けなかったことがあります。

そのときの正解は、辺を1つずつ削除していくのではありませんでした。いったんすべての辺を削除してから、一定の性質を持つ点の間に辺を追加していく、という流れになっていました。新しく追加する辺が連結成分を減らすかどうかは簡単に判定できます。

この問題も同様で、「辺を削除したら不便さがどのくらい増えるか」を考える方法は思いつきませんが、「辺を追加したら不便さがどのくらい減るか」は分かります。

新しい辺が同じ連結成分の点同士をつなぐなら、不便さは減りません。異なる連結成分 A, B の点を繋ぐなら、A の点と B の点のペアはすべて、連結でなかった状態から連結な状態に変化します。したがって点のペアの個数 (|A| * |B|) だけ不便さが減ります。

まとめるとこういう手順です。はじめにすべての辺を削除します。この時点での不便さは (N * (N - 1) / 2) です。そこに最後の辺を追加して、不便さがどのくらい減るかを上述の手順で計算します。これをすべての辺について逆順に繰り返して、得られた不便さのリストを逆順に出力すればOKです。

残る課題は「新しい辺を追加するとき、辺の両側の点が同じ連結成分に含まれているか」を高速に判定する手段です。これはユニオンファインドというデータ構造を使えばできます。

参考: Union find(素集合データ構造)

筆者の回答 (AC): https://atcoder.jp/contests/abc120/submissions/4451763