Codeforces Round #616 C. Prefix Enlightenment

Problem - C - Codeforces

コンテスト本番は闇実装に突っ込んだので、ながたかなさんの解法をベースに書き直しました…

問題概要

※解説・コードと合わせるため0-indexedで記述します。

番号 $0, 1, ..., n-1$ の電球が並んでいて、それぞれ初期状態でON/OFFどちらになっているのかが与えられる。また電球の部分集合が $A_{0}, ..., A_{k-1}$ の $k$ 個与えられる。

1回の操作では部分集合を1つ選び、含まれる電球全ての状態を反転させる。

$i = 0, ..., n-1$ それぞれについて以下の問題を解け。

電球 $0, ..., i$ を同時にONにするために必要な操作回数の最小値を求めよ。このとき $i+1$ 以降の電球の状態はどうなっていても構わない。

ここで、どの電球も3つ以上の部分集合に属することはない。また、全ての電球を同時にONにするための操作手順が必ず存在することが保証される。

制約

$1 \le n, k \le 3\times 10^{5}$
あとは上記問題概要参照

解法

満たすべき条件の整理

$i$ を1つずつ増やしていきながら順番に答えを求めていくことを考えましょう。

各電球ごとに、その電球を含む部分集合の個数は $0, 1, 2$ 個のいずれかです。同時にONにするべき電球の集合に新しく電球 $i$ が加わったとき、どのような条件が課されるようになるか考えましょう。

電球を含む部分集合が個
- この場合は電球 $i$ に対して何も干渉できません。しかし「全ての電球を同時にONにするための操作手順が必ず存在することが保証され」ているので、この場合電球 $i$ は必ず初期状態でONになっているはずです。つまり追加条件は何もありません。
電球を含む部分集合が個
- 電球 $i$ が初期状態でONである場合、この部分集合は「操作しない」とする必要があります。逆に初期状態がOFFであれば「操作する」とする必要があります。これを条件タイプ1と呼ぶことにします。
電球を含む部分集合が個
- 電球 $i$ が初期状態でONである場合、この2つの部分集合は「操作する/しない」の選択が同じである必要があります。逆に初期状態がOFFであれば異なる選択とする必要があります。これを条件タイプ2と呼ぶことにします。

このような条件が増えていく各ステップで、 $k$ 個の各部分集合について操作する/しないの選択を決め、操作するものの個数を最小化することになります。

頂点の彩色と連結成分を用いた条件の処理

$k$ 個の部分集合をグラフの頂点のように考え、各頂点を赤と青の2色に塗り分けることを考えます。この色のどちらかが部分集合を「操作する」という選択に対応します。

そして2つの部分集合間にまたがる条件タイプ2が課されたとき、その頂点間に「同色でなければならない」または「異色でなければならない」という辺を張ることにします。

このグラフの連結成分は、ある1頂点の色を決めれば他の全ての色が決まる、という関係です。この関係が守られるように各頂点の色を維持しておきます。

f:id:betrue12:20200204220138p:plain

このグラフにおいては連結成分ごとに独立に、赤と青のどちらを「操作する」に対応させるかを決めることができます。

その連結成分の中に条件タイプ1が課されているものが含まれている場合、その条件を守るように色と操作の有無を対応させる必要がある。
そうでない場合、どちらをどちらに対応させても良いので、その連結成分内で少ないほうの色を「操作する」に対応させるのが良い。

ここで制約から、同じ連結成分内で条件が矛盾することはないことが保証されます。各連結成分ごとに求めた「操作する」頂点の個数の合計が答えになります。

実装方針（つらい方法）

では徐々に条件が増えていく中で、連結成分の管理・条件タイプ2に矛盾しない色の塗り分け・条件タイプ1の存在状況を維持し、各ステップにおける答えを求められるような処理を実現しましょう。

連結成分の管理はUnion-Findを用いれば良いです。色の塗り分けについては、条件が何もない最初の状態では全ての頂点を「赤に塗る」と決めてしまいます。辺が追加されたときに、両端の頂点の色関係がその辺の要求に合っていればそのまま繋げますが、そうでない場合は併合される2つの連結成分のうち片方の色をまるっと反転させなければいけません。

f:id:betrue12:20200204220733p:plain

このような場合に適当に反転させるとトータルで $O(k^{2})$ 回の反転が必要になります。しかし必ずサイズの小さいほうの集合を反転させることで、「データ構造をマージする一般的なテク」により反転回数の合計が全体で $O(k\log k)$ に抑えられます。

また条件タイプ1についても、Union-Findの中に情報として持たせておきます。根の色を基準にして、「根の色が"操作する"と対応する必要がある」「根の色が"操作しない"と対応する必要がある」「条件タイプ1が存在しない」のいずれかであるかを各連結成分に持たせておきます。連結成分同士を併合するときにここも上手くマージします。

あとは各連結成分について赤頂点の数/青頂点の数も管理しておけば、各連結成分から答えに足すべき値が求められるようになるので、条件が増えるごとに影響を受ける連結成分の答えを差分管理することで各ステップにおける答えを求めることができます。

ACコード（つらかった）

Submission #70072102 - Codeforces

実装方針（よい方法）

途中で頂点の色を反転するとか、根の色に合わせて条件タイプ1の状態をごちゃごちゃ反転させるとか、つらいですね。よい実装も紹介します。

まず最初に、全ての条件（タイプ1・タイプ2）が追加されてしまった状態を考えます。このグラフにおいて、条件タイプ2に矛盾しないように各頂点の彩色を決めてしまいます。こうすれば途中で頂点の色を変える必要がなくなります。

また条件タイプ1については、仮想的に頂点を1つ増やすことで扱いが楽になります。この頂点を $k$ とすると、頂点 $k$ は常に赤色で、頂点 $k$ の赤は必ず「操作しない」に割り当てることにすると決めてしまいます。こうすると条件タイプ1は頂点 $k$ と繋ぐ辺として、条件タイプ2と同様に扱うことができます。

f:id:betrue12:20200204221753p:plain