2019年9月29日日曜日

ABC 142 E - Get Everything

ABC 142 E - Get Everything

NNが小さいので、dp[S]=dp[S] = 集合SSに含まれる宝箱を全部開けられるような鍵の選び方をした時の最小コスト、を目指したくなる。(不可能な場合は\infty。)

O(2NM){\mathcal O}(2^NM)のDP

iiで開けられる宝箱の集合をCiC_iとするとき、dp[]:=0dp[\empty] := 0と初期化して

dp[SCi]:=min(dp[SCi],dp[S]+Ci)dp[S \cup C_i] := \min (dp[S \cup C_i], dp[S]+C_i)

をすべての鍵と集合について更新して求まるなら話は早い……が、これは集合の包含関係について全部処理しているわけではない。つまり、この方法で最終的に求まるのはdp[S]=dp[S] = 集合SSに含まれる宝箱を全部開けられて、SSに含まれない宝箱を一つも開けられないような鍵の選び方をした時の最小コスト、である。しかし、もう少し考えると、求めるのは全体集合に対する最小コストだったので、それでも問題ないことがわかる。1

コンテスト中はこの辺の理解にぱっと至らなくて、しばらく逡巡してしまった。

O(3N+M){\mathcal O}(3^N + M)のDP

最初に目指したdpdpを直接求める方法を考えてみる。dpdpをすべて\inftyに初期化して、

dp[]:=0dp[\emptyset] := 0

dp[Ci]:=aidp[C_i] := a_i

とする。(重複する場合は小さい方を選ぶ。つまり、正確にはdp[Ci]:=min(dp[Ci],ai)dp[C_i] := \min (dp[C_i], a_i)。)dpdpを上位集合に関してゼータ変換すると、dp[S]=dp[S] = 宝箱の集合SSを一つの鍵で開ける場合の最小コスト、になっている。あとは、

dp[S]:=minTS(dp[T]+dp[ST])dp[S] := \min_{T \subseteq S}(dp[T]+dp[S \setminus T])

を使って順次最小値を確定していけばよい。部分集合の効率的な列挙のやり方は https://topcoder.g.hatena.ne.jp/jackpersel/20100804/1281196966 に書いてある。


  1. 何個か宝箱の集合クエリを受け取ってそれに対する最小コストを返す問題の場合は、最後にdpdpをゼータ変換すればよい。 ↩︎

2019年9月26日木曜日

ARC 100 E - Or Plus Max

ARC 100 E - Or Plus Max

以下、ビット列とそれが表す集合を同一視する。インデックスの集合S,T{0,1,...,2N1},S,T2S, T \subseteq \{0, 1, ..., 2^N-1\}, |S|, |T| \le 2が与えられたとき、STS \oplus Tを、インデックスiSTi \in S \cup Tの中からAiA_iが大きいもの2つを残した集合とする。\oplusは結合的で可換なのでゼータ変換が適用できる。つまり、

F(S):=TSf(T)F(S) := \oplus_{T \subseteq S} f(T)

という変換ができる。fff(S):={S}f(S) := \{S\}でよい。

これでijKi \lor j \subseteq Kを満たすi,ji, jに対するAi+AjA_i + A_jの最大値が求まるが、実際にはijKi \lor j \le Kを満たすi,ji, jについて考えなくてはならない。ijKk{0,1,...,K}i \lor j \le K \Leftrightarrow k \in \{0, 1, ..., K\}が存在してij=kk{0,1,...,K}i \lor j = k \Leftrightarrow k \in \{0, 1, ..., K\}が存在してijki \lor j \subseteq kだから、ijKi \lor j \le Kを満たすi,ji, jに関する最大値はmaxkK(F(k)+F(k))\max_{k \le K} (F(k)の片方 + F(k)のもう片方)として累積的に求まる。


高速ゼータ変換に関するメモ。高速ゼータ変換は各部分集合SUS \subseteq Uの各要素をちょうど一回ずつ重複なく処理するので、集合の合併を取る場合はそのままくっつけて良い。つまり、例えばg(S):=Sg(S) := Sという関数を和集合についてゼータ変換したいとするとき、つまり

G(S):=TSg(T)G(S) := \bigcup_{T \subseteq S} g(T)

を求めるとき、和集合S1S2S_1 \cup S_2を得る操作で重複を除く必要はない。


Common Lispに関するメモ。扱う集合が小さいので珍しくunionを使う気になったら初歩的な失敗をした。非破壊的な合併を書いているつもりでなんとなく(sort (union list1 list2) ...)としたのだけど、unionはリストをコピーするとは限らないのでsortで元のリストが破壊される。(sort (nunion (copy-list list1) (copy-list2 list2)) ...)とするか、あるいはunionしてからcopy-listするのが正しかった。

非破壊的操作はコピーするとは限らないというポイント、わかっているつもりで普段は忘れている。(sort (mapcar ...) ...)みたいなのも(mapcar #'identity list)listをそのまま返すような最適化は許されているので、元のリストが保たれるとは限らない。(SBCLでは大丈夫だけど。)本質的には危険なコードをけっこう書いてしまっている気がする。


SBCLに関するメモ。SBCLのmergeはいちいちsb-kernel:specifier-typeを呼ぶので1回の呼び出しが重い。使う時には注意する必要がある。

2019年9月22日日曜日

AGC 038 C - LCMs

AGC 038 C - LCMs

ゼータ変換について勉強する機会になった。

ゼータ変換とメビウス変換

  • 下位集合に関するゼータ変換: F(S)=TSf(T)F(S) = \sum_{T \subseteq S} f(T)
  • 上位集合に関するゼータ変換: F(S)=TSf(T)F(S) = \sum_{T \supseteq S} f(T)

これをO(2NN){\mathcal O}(2^N N)でやるのが高速ゼータ変換。普通の総和以外にも、×,max,min\times, \max, \minとかでもまったく同じ方法が使える。結合法則と交換法則が成り立っていればよいので、可換半群なら大丈夫なはず1

  • 下位集合に関するメビウス変換: f(S)=TS(1)STF(T)f(S) = \sum_{T \subseteq S} (-1)^{|S\setminus T|}F(T)
  • 上位集合に関するメビウス変換: f(S)=TS(1)TSF(T)f(S) = \sum_{T \supseteq S} (-1)^{|T \setminus S|}F(T)

ゼータ変換の逆変換。つまり、上のFFからffを導出する変換。

ゼータ変換と違って引き算を使うので、アーベル群でないといけない。演算がmin\minとかだとそもそもffを一意に復元できないので、当然ではある。

(用語法はよくわからないけど、競プロ界ではだいたいみんなnaoya_tさんの記事にある使いわけをしているっぽいのでそれに従っている。文献(これとか)によっては、ここでいう下位集合に対するゼータ変換がMöbius transform、その逆変換がMöbius inversionと呼ばれていたりする。)

\cup畳み込みと\cap畳み込み

ff, gg
F(S):=TSf(T)F(S) := \sum_{T \subseteq S} f(T)

G(S):=TSg(T)G(S) := \sum_{T \subseteq S} g(T)

と下位集合に関してゼータ変換して、点毎に掛け算したものをHHとする:

H(S):=F(S)×G(S)=T1Sf(T1)×T2Sg(T2)=TST1T2=Tf(T1)×g(T2)\begin{aligned} H(S) & := F(S) \times G(S) \\ & =\sum_{T_1 \subseteq S} f(T_1) \times \sum_{T_2 \subseteq S} g(T_2) \\ & = \sum_{T \subseteq S} \sum_{T_1 \cup T_2 = T}f(T_1) \times g(T_2) \end{aligned}

HHをメビウス変換すると

h(S):=T1T2=Sf(T1)×g(T2)h(S) := \sum_{T_1 \cup T_2 = S} f(T_1) \times g(T_2)

という関数が得られて、\cupに関する畳み込みができたことになる。

同様に、上位集合に関してゼータ変換して掛け合わせて逆変換すると、\capに関する畳み込みができる。

分配法則を使っているので、この掛け算は足し算と合わせて環になっていないといけない。

約数、倍数に関するゼータ変換とメビウス変換

上と同じ話を約数、倍数について繰り返す。

  • 約数に関するゼータ変換: F(x)=dxf(d)F(x) = \sum_{d | x} f(d)
  • 倍数に関するゼータ変換: F(x)=xmf(m)F(x) = \sum_{x | m} f(m)

ただし、定義域は{0,1,...,N}\{0, 1, ..., N\}とかに決まっているとして、その中だけで計算する。この変換はO(NloglogN){\mathcal O}(N \log\log N)でできる。2

上のFFからffを導出する変換。同じオーダーでできる。歴史的には約数・倍数に関するもののほうが最初に考えられたらしい。

LCM畳み込みとGCD畳み込み

やはり上と同じ話をLCMとGCDについて書き下してみる。

ff, gg
F(x):=dxf(d)F(x) := \sum_{d | x} f(d)

G(x):=dxg(d)G(x) := \sum_{d | x} g(d)

と約数に関してゼータ変換して、掛け合わせたものをHHとする:

H(x):=F(x)×G(x)=d1xf(d1)×d2xg(d2)=dxlcm(d1,d2)=df(d1)×g(d2)\begin{aligned} H(x) & := F(x) \times G(x) \\ & =\sum_{d_1|x} f(d_1) \times \sum_{d_2|x} g(d_2) \\ & = \sum_{d | x} \sum_{\operatorname{lcm}(d_1, d_2) = d}f(d_1) \times g(d_2) \end{aligned}

HHを逆変換すると

h(x):=lcm(d1,d2)=xf(d1)×g(d2)h(x) := \sum_{\operatorname{lcm}(d_1, d_2) = x} f(d_1) \times g(d_2)

という関数が得られて、lcm\operatorname{lcm}に関する畳み込みができたことになる。

同様に、倍数に関してゼータ変換して掛け合わせて逆変換すると、gcd\gcdに関する畳み込みができる。

問題

lcm(Ai,Aj)=AiAj/gcd(Ai,Aj)\operatorname{lcm}(A_i, A_j) = A_iA_j/\gcd(A_i, A_j)で、gcd(Ai,Aj)\gcd(A_i, A_j)は高々10000001000000なので、同じgcd\gcd毎にまとめて和を計算できれば良さそう。

最終的には、dp[x]dp[x]gcd(Ai,Aj)=x\gcd(A_i, A_j) = xとなるような組み合わせについてのAiAjA_i A_jの総和になってほしいので、とりあえずdpdpを次のように初期化していく。

dp[Ai]:=dp[Ai]+Aidp[A_i] := dp[A_i] + A_i

dpdpを倍数に関してゼータ変換してdp[x]:=dp[x]dp[x]dp[x] := dp[x] \cdot dp[x]と掛け合わせて逆変換すると、

dp[x]=gcd(Ai,Aj)=xAiAjdp[x] = \sum_{\gcd(A_i, A_j) = x}A_iA_j

になっている。このままでは不必要な組み合わせについても加算されているので、

dp[Ai]:=dp[Ai]Ai2dp[A_i] := dp[A_i] - A_i^2

として添え字が同じ組み合わせを除いたあと、AiAjA_iA_jAjAiA_jA_iのダブルカウントを除くためにすべて半分にする: dp[x]:=dp[x]/2dp[x] := dp[x]/2。(ここではなくて一番最後に半分にしてもよい。)

これでdp[x]dp[x]gcd(Ai,Aj)=x\gcd(A_i, A_j) = xとなるような組み合わせについてのAiAj(i<j)A_i A_j (i < j)の総和になったので、あとはgcd\gcdで割りながら総和を取れば答えになる: x=11000000dp[x]/x\sum_{x = 1}^{1000000} dp[x]/x


  1. ググってもそれっぽい言明が見つからなかったけど、かならいさんがそう言ってるのを発見した。 ↩︎

  2. noshi91さんの記事に書いてある。 ↩︎