Codeforces Round #626 (Div. 1) C. Instant Noodles

Problem - C - Codeforces

問題概要

左側、右側それぞれに $n$ 個の頂点があり、その間に合計 $m$ 本の辺が存在する二部グラフが与えられる。右側の頂点にはそれぞれ正整数 $c_{i}$ が書かれている。

左側の頂点の部分集合 $S$ について、 $f(S)$ を「右側の頂点のうち $S$ の要素のいずれかと辺を結んでいるものについて $c_{i}$ を合計した値」と定義する。

空でない全ての $S$ に対する $f(S)$ の最大公約数を求めよ。

制約

※マルチテストケースですが、記載省略します

$1 \le n, m \le 500000$
$1 \le c_{i} \le 10^{12}$
辺は全て左側の頂点と右側の頂点の間に存在し、多重辺はない

解法

まず右側の頂点それぞれについて、「どの左側の頂点と隣接しているか」を隣接リストなどの形式で求めます。これが集合として等しい右側の頂点たちは、 $S$ をどのように選んでも $f(S)$ に算入されるかされないかの扱いが同じになるので、 $c_{i}$ の和を取ってまとめてしまって良いです。

そして実は、このように右側の頂点を隣接頂点集合で分類して $c_{i}$ の和を取り、孤立している（隣接頂点集合が空である）もの以外全てのGCDを取ると、それが答えになります。びっくりですね。証明しましょう。

証明

GCDに関する性質として、 $\gcd(a, b) = \gcd(a, b-a) = \gcd(a, b+a)$ であること、またこれは3要素以上のGCDを考える時にも適用できることを使っていきます。

説明を簡単にするため $n=3$ とし、左側の頂点の集合を $3$ 桁のビット列で表現します。右側の頂点を隣接頂点集合で分類して和を取り、ビット列 $B$ に分類される右側の頂点について $c_{i}$ の和を取ったものを $C(B)$ と書くことにします。

f:id:betrue12:20200308154935p:plain

これから左側の集合 $S$ として取りうるものを1つずつ考え、各時点までに登場した $f(S)$ のGCDの値を $G$ として順次計算していきます。アイデアとしては、まず最大の $S$ を考え、そこからちょっとずつ小さい $S$ を順番に見ていきます。

まず $S$ として全ての左側頂点（ビット列で $111$ ）を考えると、これに対する $f(111)$ は

$\displaystyle f(111) = \sum_{B \ne 000} C(B)$

と計算できます。孤立点以外の全ての右側頂点が算入対象です。この値を $F$ と書くことにすると、この時点で $G=F$ です。

ここで $S = 011$ というものを考えると、 $F$ から「頂点 $1$ にしか隣接していない右側頂点」のぶんが除かれるので、

$\displaystyle f(011) = F - C(100)$

です。ここで $\lbrace f(111), f(011) \rbrace$ のGCDを考えると、

$G = \gcd(F, F - C(100)) = \gcd(C(100), F - C(100)) = \gcd(C(100), F)$

となって、 $C(100)$ が単独で出てきます。このように左側頂点を1つだけ外した集合それぞれについて同様のことを考えると、 $\lbrace f(111), f(011), f(101), f(110) \rbrace$ のGCDは

$G = \gcd(F, C(100), C(010), C(001))$

と計算できます。

次は左側頂点を2つ外した集合、例えば $S = 001$ を考えるとこれは

$\displaystyle f(001) = F - C(100) - C(010) - C(110)$

となります。これを $G$ の $\gcd$ の中に入れると、既に $C(100), C(010)$ が存在しているので、同様の計算で

$G = \gcd(F, C(100), C(010), C(001), C(110))$

になります。これを繰り返すと、空でないビット列 $B$ に対する $C(B)$ の値が全て登場し、 $F$ はそれらの和なので最後に取り除いても問題ありません。

これは $n$ が一般の正整数の場合でも同様に成り立つので、証明が完了します。

ACコード、実装、計算量

Submission #72644787 - Codeforces

全ての隣接リストをソートした状態にすることで、集合として等しいものは列としても等しくなります。そしてこのコードではこれをそのまま map<vector<int>, int64_t> のキーに突っ込んでいます。計算量的に危険な感じがしますが、大丈夫です。

この map の要素数は高々 $n$ であり、長さ $l$ の vector<int> をキーとするときの操作計算量は1回のキー比較が $O(l)$ になるので $O(l\log n)$ です。全ての隣接リストの長さ合計が $m$ であることから、このソート＆集計操作の計算量は全体で $O(n + m(\log m + \log n))$ と評価できます。