Codeforces Round #622 (Div. 2) D. Happy New Year

お題箱より。

Problem - D - Codeforces

問題概要

$m$ 人の子供がいて $1, ..., m$ の番号を持っている。以下の $n$ 個の操作についてそれぞれ、実行するかしないかを選ぶことができる。

区間 $\lbrack L_{j}, R_{j}\rbrack$ に属する子供に1個ずつキャンディを与える。

ここで整数 $k$ が与えられ、 $k$ 個を超える操作区間に属する子供は存在しないことが保証される。

子供は奇数個のキャンディをもらうと嬉しくなる。操作を上手く選ぶことで嬉しい子供の人数を最大化したい。その最大人数を求めよ。

制約

$1 \le n \le 10^{5}$
$1 \le m \le 10^{9}$
$1 \le k \le 8$

解法

まず $m$ が大きいので、座標圧縮をします。このとき各区間を半開区間にして、その $L_{j}, R_{j}$ および全体の左端・右端を集めて座標圧縮をすると良いです。圧縮後の各座標は、扱いが必ず同じになるような子供の区間に対応します。

f:id:betrue12:20200328153421p:plain

$k$ が小さいことがポイントです。圧縮後の座標において、各操作区間を以下のように $k$ 個のレーンに分類します。

f:id:betrue12:20200328144035p:plain

制約より、同じレーンの中では区間が重ならないように分類することができます。具体的には子供（の圧縮後座標）を左から見ていきながら「空きレーン」を集合などで管理しておき、その子供を左端とする操作区間に空きレーンの番号を割り当てるようにすれば良いです。

このようにレーンに分類すると、以下のようなDPを組むことができます。

$dp\lbrack i \rbrack\lbrack j \rbrack =$ 子供を（圧縮後の座標で） $1, ..., i-1$ まで見て、子供 $i-1$ がキャンディをもらったレーンの番号を表現したビット列が $j$ であるときの、子供 $i-1$ までのうち嬉しくなった人数の最大値

$dp\lbrack i \rbrack\lbrack j \rbrack$ から $dp\lbrack i+1 \rbrack\lbrack j_{2} \rbrack$ の遷移を考えます。まず遷移先の $j_{2}$ の値として最小のものは、遷移前の $j$ から「 $i$ が半開区間での右端となっている区間」に相当するレーン番号を除いたものです。これに対して $i$ から始まる区間のうち任意個を新しく操作できるので、それらのレーン番号のビットを立てたパターン全てが $j_{2}$ としてあり得ます。そして $j_{2}$ の立っているビットの数が偶数個ならそのまま遷移し、奇数個なら圧縮後の座標 $i$ に相当する圧縮前の子供の人数を足して遷移します。

ですがこの方法だと、遷移前の $j$ と新しく操作する区間の選び方で $O(2^{k})$ が2回掛かり計算時間が厳しいです。これに対応する方法は2つあります。

操作区間の集合を同値変形する

操作区間の集合を全体として同値なものに変形して、全ての座標において「その座標から始まる区間」が高々1個となるようにできます。

具体的には、左端もしくは右端を共有している操作区間をUnion-Findで連結させます。そして同じ連結成分に属している座標点を左から順番に繋ぐような区間を取ると、これらの区間の操作で実現できる状態は元の操作区間たちで実現できる状態と等しくなります。

f:id:betrue12:20200328153912p:plain

このようにすると全ての座標において「その座標から始まる区間」が高々1個になり、遷移回数が減って間に合います。

ACコード

Submission #71688679 - Codeforces

高速ゼータ変換のように $dp\lbrack i+1 \rbrack\lbrack j_{2} \rbrack$ 同士で遷移する

まず1度、全ての $j$ について「終わった区間を除いた」だけの $j_{2}$ を求め、 $dp\lbrack i+1 \rbrack\lbrack j_{2} \rbrack$ に遷移します。そのうえで高速ゼータ変換のように、区間が $i$ から始まるレーン番号 $k$ について $dp\lbrack i+1 \rbrack\lbrack j_{2} \rbrack$ から $dp\lbrack i+1 \rbrack\lbrack j_{2}+2^{k} \rbrack$ に遷移するようなDPを考えることができます。