EDPC解説 U～Z - kyopro_friends’ diary

やー、フェネックだよー。
残りの6問はどれも難しいけど、解説していくよ。
実装例は省略するから自分で考えて書いてみてねー。

U問題 Grouping

$N$ 羽のうさぎをいくつかのグループに分ける。
うさぎのペア $i,j$ について、 $i$ と $j$ が同じグループに属していれば $a[i][j]$ 点を得る。
最高得点を求めよ。
制約： $N\leq 16$

解説

bitDPっぽいねー。
$dp[S]=($ 集合 $S$ に属するウサギのグループ分けの最高得点 $)$
としてみようか。あとはN問題とほぼ同じで、「どこで切るか」を考えると良さそうだね。
$dp[S]=\max(dp[T]+dp[S\setminus T])$
ただし、N問題と違って「切らない」っていう選択肢もありだから注意が必要だよ。
実装はメモ化再帰の方が簡単かなあ。
bitDPは0-indexedの方が都合がいいから、入力は0-indexedで与えられているものとするねー。

#define bit(n,k) ((n>>k)&1) /*nのk bit目*/
long long f(int S){
	if(flag[S])return dp[S];
	flag[S]=1;
	//「切らない」場合を計算
	temp=0;
	rep(i,0,N)rep(j,i+1,N)if(bit(S,i)&&bit(S,j))temp+=a[i][j];
	fans=temp;
	//「どこで切るか」を考える
	for(Sの空でない真部分集合Tについて){
		fans=max(fans,f(T)+f(S^T));
	}
	return dp[S]=fans;
}
//ans=dp[(1<<N)-1];

for文で「部分集合 $T$ 」を動くところが問題なんだけど、すぐに思いつく方法としてはこういうのがあるね。

rep(T,0,S)if((T|S)==S){/* */}

でもこれは状態数 $O(2^N)$ 、遷移 $O(2^N)$ だから全体で $O(4^N)$ になってTLEなんだよねー。
実は「 $S$ の部分集合 $T$ 」だけをちょうどループ出来るようなこういうテクニックが存在するよ。

for(int T=S;T>=0;T--){
	T&=S;
	/* */
}

この演算は「-1」という操作を「1であるような一番下のbitを0に変えて、それより下のbitを全て1にする」という意味だと思うと納得できるんじゃないかな？
今回は、空集合と $S$ 自身を除くからこうだね。

for(int T=S;T>=0;T--){
	T&=S;
	if(T==S || T==0)continue;
	/* */
}

さて、計算量はどうなるかな？
このループは $2^{|S|}$ 回されるから、全ての $S$ について和を考えると
$\sum_S 2^{|S|} \\ =\sum_{i=0}^N \sum_{|S|=i} 2^{|S|} \\ =\sum_{i=0}^N 2^i*\#\{S \ | \ |S|=i\}\\ =\sum_{i=0}^N 2^i* {}_N C_i\\ =\sum_{i=0}^N 2^i*1^{N-i} * {}_N C_i\\ =(2+1)^N=3^N$
となって、つまり全体で $O(3^N)$ だね。これなら間に合うよ。
今回みたいにbitDPとかで役に立つbit演算のテクニックはこの記事が詳しいねー。
ビット列による部分集合表現【ビット演算テクニック Advent Calendar 2016 1日目】 - prime's diary

V問題 Subtree

$N$ 頂点の木がある。頂点をいくつか選んで黒く塗る。このとき黒く塗られた頂点たちは連結であるようにする。
各頂点について、その頂点を黒く塗るような方法は何通りあるか $\mod M$ で答えよ。
制約： $N\leq 10^5$ 、 $M\leq 10^9$

解説

1つの頂点についてだけ答えればいいんだったら、P問題と同じようにして $O(N)$ で求められるけど、これを各頂点でやってたら $O(N^2)$ になって間に合わないんだよねー。
この問題みたいに「木の各頂点について～～であるようなものを求めよ」って問題は全方位木DPっていう方法で解けることが多いよ。
こういう感じのアルゴリズムだね。
１．適当な頂点を根にして木DPで問題を解く
２．根を子に移して問題を解く。このとき、今までに求めた情報を使い回す
３．繰り返す
詳しいアルゴリズムについてはこのブログが詳しいよ。
†全方位木DP†について - ei1333の日記
他にもsnukeさんのツイートも参考になるねー。

全方位木DP、有向辺に関するDPだと思うのが分かりやすい。
1. 青い矢印は普通の木DPで下から順に求まる
2. 根から出る矢印は全部求まっているので、根に入る矢印も求められる（ここの計算量改善に総和とって引き算とか左右からの累積和とかが出てくる）
3. 同様に赤い矢印を上から順に求めていく pic.twitter.com/p4bl6rXzGn
— ꑄ꒖ꐇꌅꏂ🐈 (@snuke_) 2019年1月6日

実はこの問題は、全方位木DPを知ってても"やるだけ"じゃないんだよねー。
まずはこの図を見てもらおうか。
f:id:kyopro_friends:20190112031630p:plain
左側でまず頂点1を根として問題を解いて、次に根を頂点2に移して問題を解くことを考えるよ。
左側の図で頂点1を根として問題を解くときは、頂点1で集める情報は「頂点2、頂点3、頂点4」の部分木に関する情報だね。
だけど右側の図で頂点2を根とするときは、頂点1で集める情報は「頂点3、頂点4」の部分木に関する情報で、頂点2は親だから含まないねー。
同様に頂点3,4を根にすると、頂点1で集める情報は「頂点2,4」「頂点2,3」になるから、毎回情報を集め直してたら、ウニグラフ*1のときに全体で $O(N^2)$ になっちゃうんだよねー。
かといって「頂点2,3,4」に関する情報を集めておいて、そこから「頂点2に関する情報を取り除く」ということも出来ないよ。部分木の答えが $\mod M$ で0のときにゼロ除算になるからね。
どうすればいいかな？ちょっと問題をまとめ直しておこうか。
問題：頂点 $v$ と隣接する頂点の集合を $U$ とする。 $U$ に属する各頂点 $u$ に対し、部分木に関する答え $dp[u]$ が求まっている。このとき、各 $u$ について $\prod_{w\neq u}dp[w]$ を高速に求めよ。
これも「累積和」を使うと解くことが出来るんだよね。今回は掛け算だから「累積積」って言った方がいいかな？
こういう手順で求めるよ
１． $U$ の頂点に順序を付けて $1,2,\ldots,k$ とする。
２．前方 $1$ ～ $i$ の累積積 $cum1[i]$ と、後方 $i$ ～ $k$ の累積積 $cum2[i]$ を計算しておく
３．各 $u\in U$ について求める答えは $cum1[u-1]*cum2[u+1]$
こうすれば前計算 $O(|U|)$ 、本計算 $O(1)$ でできるから、全ての頂点についての答えが $O(|U|)$ で求められるよ。
ここまで工夫すれば全体での計算量は $O(N)$ になって間に合うねー。いやー大変だよー。

…………ちなみに、私は本番ではこれを思いつかなくて、 $O(N\log N)$ で解いたんだよねー。詳しくは解説しないけど、こんな感じの方法だよ。
１． $U$ の頂点に順序を付けて $1,2,\ldots,k$ とする。
２． $f(l,r,s)$ という関数を「区間 $[l,r)$ に属する頂点について答えたい。この部分以外に関する積は $s$ 」とする
３．区間の長さが1なら $s$ が答え。そうじゃないなら $m=(l+r)/2$ として、 $f(l,m,s'),f(m,r,s'')$ を再帰呼び出し
こうすると、二分法の要領で $O(|U|\log|U|)$ 、全体だと $O(N\log N)$ で求められるねー。やー、競技プログラミングの問題は解ければ正義だから、ゴリ押しも大事だよー？

W問題 Intervals

$M$ 個の区間 $[l[i],r[i]]$ と値 $a[i]$ が与えられる。
長さ $N$ の01列に対して次のようにスコアを定めるとき、その最大値を求めよ。
条件：区間 $[l[i],r[i]]$ に1が存在すれば $a[i]$ 点を得る
制約： $N\leq 2*10^5$ 、 $M\leq 2*10^5$

解説

やー、DPの問題としては全部の問題のなかでこれが一番難しいんじゃないかな？
この問題をDPで解くためには
$dp[i][*]=(*$ の条件下で $i$ 文字目まで決めたときの最高スコア $)$
みたいな感じにしようと考えるのが自然だよねー。このとき、スコアは「 $[1,i]$ に完全に含まれる区間のみ」を考えることにするよ。 $i+1$ 以降にはみ出す区間は、 $dp[i+1][*]$ 以降に影響を与えちゃうからね。
DPの状態として持つべき情報は何かを考えてみよう。 $dp[i][*]$ を考える時には、 $dp[i-1][*]$ の時から新たに $[l,i]$ という形の区間に関するスコアを考慮することになるから、この区間に1があるかどうかがわかる必要がありそうだねー。だから
$dp[i][j]=(i$ 文字目まで決めて、最後に1であるのが $j$ 文字目であるようなものの最高スコア $)$
というものを考えてみようか。
$dp[i][j]\\ = \left\{ \begin{array}{ll} dp[i-1][j]+(j\in [l,i]となる区間に関するスコアの和) & (j< i) \\ \max \{ dp[i-1][j] | 0\leq j< i\}+([l,i]となる区間に関するスコアの和) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ & (j=i) \end{array} \right.$
として一応は計算できるけど、これをこの形のまま実装すると $O((N+M)N)$ かかっちゃうねー。
遷移をよく見ると、これは次の3つのステップに分解できるよ。
１． $dp[i][*]$ に $dp[i-1][*]$ をコピーする
２． $dp[i][i]=\max \{ dp[i-1][j] | 0\leq j< i\}$ とする
３． $[l,i]$ の各区間について、 $j\in[l,i]$ なる $j$ の範囲で $dp[i][j]$ にスコアを加える
ステップ１は $dp[i][*]$ と $dp[i-1][*]$ で同じ配列を使い回すことで省略できて、ステップ２は区間maxと1点更新、ステップ３は区間addだから、starry sky treeというものを使うとそれぞれ $O(\log N)$ 、全体で $O((N+M)\log N)$ にできるよ。
starry sky treeに関する説明は省略するけど、区間addと区間maxができるようにちょっと工夫したセグメント木のことだねー。遅延セグメント木が上位互換になってるから、そっちが使えるならそれでも十分だよ。

X問題 Tower

$N$ 個のブロックがあり、 $i$ 番目のブロックは重さ $w[i]$ 、丈夫さ $s[i]$ 、価値 $v[i]$ である。
これらのブロックを1列に積み重ねて、次の条件が満たされるような塔を作る。塔に含まれるブロックの価値の和の最大値を求めよ。
条件：塔を構成するどのブロックの丈夫さも、それより上にあるブロックの重さの合計以上である
制約： $N\leq 10^3、s[i]\leq 10^4$

解説

ナップサックDPみたいに
$dp[i][j]=(i$ 番目までのブロックを使って重さ $j$ 以下で作れる塔の最大価値 $)$
としたいけど、丈夫さに関する条件を考えると、次のブロックが使えるかどうかわからないからうまくいかないねー。
実はこの問題は「ブロックをうまく並び替えることで、塔に使うブロックの順序を決めることができる（＝次に使うブロックは、使うなら一番下）」らしいよ。やー、なんでこんなこと思いつくのかなー？
どういう順序で使えばいいか考えるためにこういうのを考えてみるよ。
f:id:kyopro_friends:20190112002741p:plain
そういうわけで $s[i]+w[i]$ でソートしたら、あとは最初に言ったDPができるね。
ちなみにこれは「 $s[i]+w[i]$ が大きいものの方が上になってたら、入れ替えても影響がない」という方針でも証明ができて、その方が簡単なんだけど、「 $s[i]+w[i]$ が小さいものが上になったほうがよさそう」ってわかってないと思いつけないから、ちょっと難しいかもねー。
計算量は $O(N\max s[i])$ だよ。

Y問題 Grid 2

2次元のマスを移動する。 $(i,j)$ からは $(i+1,j)$ か $(i,j+1)$ に移動できる。
ただし $N$ 個の壁があり、そのマスには移動できない。 $i$ 番目の壁の座標は $(r[i],c[i])$ である。
$(1,1)$ から $(H,W)$ へ移動する場合の数を $\mod 10^9+7$ で求めよ。
制約： $H,W \leq 10^5$ 、 $N\leq 3*10^3$

解説

壁は予め辞書順かマンハッタン距離順にソートしておこうか。それから二項係数もでてきそうだから「壁がない時(0,0)から(x,y)まで移動する場合の数＝ ${}_{x+y}C_x$ 」のことを $f(x,y)$ と書くことにしとくよ。階乗とその逆元を $O(H+W)$ で前計算しておくことで、 $f(x,y)$ は $O(1)$ で答えられるとしていいね。（やらなくても間に合うけどねー）
一瞬座標圧縮にも見えるけど、圧縮して無くなったマスだけを通る経路をうまく数えられないからそれはダメそうだねー。
$N$ が小さければ
$dp[i]=(i$ 番目の壁を通って、スタートからゴールまで移動する場合の数 $)$
として包除原理を使うことでも解けるけど、今回は無理だよ。
求めるものの余事象を考えると、「壁のマスを1回以上通って、ゴールまで行く場合の数」になるわけだけど、「1つ以上あるか？」とくれば、W問題と同じように「最後に/最初に〇〇したもののindex」を状態に持てば良さそうだねー。
そこで
$dp[i]$
$=($ 最初にぶつかる壁が $i$ である場合の数 $)$
$=(1～i-1$ 番目の壁を避けて $i$ 番目の壁の位置にたどり着く場合の数 $)$
というのを考えるよ。
$dp[i]$
$=f(r[i],c[i])-(i-1$ 番目までの壁に1回以上ぶつかって壁 $i$ の位置にたどり着く場合の数 $)$
で、
$(i-1$ 番目までの壁に1回以上ぶつかって壁 $i$ の位置にたどり着く場合の数 $)$
$＝\sum_{j=1}^{i-1}($ 壁 $j$ で初めて壁にぶつかって壁 $i$ の位置にたどりつく場合の数 $)$
$＝\sum_{j=1}^{i-1} (1～j-1$ 番目の壁を避けて $j$ 番目の壁の位置にたどり着く場合の数 $)\times(j$ 番目の壁の位置から $i$ 番目の壁の位置まで壁を無視して移動する場合の数 $)$
$＝\sum_{j=1}^{i-1} dp[j]*f(r[i]-r[j],c[i]-c[j])$
となるから、遷移は $O(N)$ でできるね。
ゴールまでの場合の数も同様にしてできるから、計算量は全体で $O(N^2)$ だね。

Z問題 Frog 3

$N$ 個の足場がある。
足場 $i$ からは足場 $i+1,i+2,\ldots,N$ のいずれかに移動でき、足場 $i$ から足場 $j$ に移動するコストは $(h[i]-h[j])^2+C$ である。
足場 $1$ から足場 $N$ に移動するまでの最小コストを求めよ。
制約： $N\leq 2*10^5$ 、 $C\leq 10^{12}$ 、 $h[i]\leq10^6$

解説

やー、この問題はCHT(Convex Hull Trick)を知ってれば、見た瞬間「CHTだ」ってなる問題だねー。いわゆる「知識ゲー」ってやつかな？
まずはCHTっていうのは、こういうのだねー。

区間 $[L,R]$ と直線群 $S$ が与えられたとき、次の2種類のクエリを高速に処理するアルゴリズムをCHTという。
１．直線追加クエリ： $S$ に直線 $Ax+B$ を加える
２．最小値クエリ： $x\in [L,R]$ に対し $\min\{f(x) \ | \ f\in S\}$ を求める

今回は追加される直線の傾き $A$ と最小値クエリで問われる値 $x$ のどちらもが単調だから、dequeを使って書けるんだけど、せっかくだからLi Chao Segment Treeを実装したよ。これはどちらのクエリについても単調性を問わないものだねー。
実装はこのブログを参考にしたよ。
傾きの単調性が要らない Convex Hull Trick - kazuma8128’s blog

Li Chao Segment Tree
$N$ 点集合 $P=\{x_i\}$ と直線群 $S$ が与えられたとき、次の2種類のクエリを $O(\log N)$ で処理するデータ構造
１．直線追加クエリ： $S$ に直線 $Ax+B$ を加える
２．最小値クエリ： $x\in P$ に対し $\min\{f(x) \ | \ f\in S\}$ を求める

元の問題の解説に戻ろうか。
A問題と同じ素直なDPを考えると
$dp[i]=($ 足場 $i$ にたどり着くまでの最小コスト $)$
$dp[i]=\min\{dp[j]+(h[i]-h[j])^2+C\ |\ 1\leq j< i\}$
となって遷移が $O(N)$ だから全体で $O(N^2)$ になって間に合わないんだけど、遷移式をよく見て変形すると
$dp[j]+(h[i]-h[j])^2+C\\ =-2h[j]*(h[i])+(dp[j]+h[j]^2)+(h[i]^2+C)$
となって、最後の部分をminの外に出して
$dp[i]=\min\{-2h[j]*(h[i])+(dp[j]+h[j]^2)\ |\ 1\leq j< i\}+(h[i]^2+C)$
となるねー。
わかりやすくするために $A_j=-2*h[j]$ 、 $B_j=dp[j]+h[j]^2$ とおくと、minの部分は
$\min\{A_j*(h[i])+B_j\ |\ 1\leq j< i\}$
つまり「 $A_jx+B_j$ という直線群の $x=h[i]$ における最小値を求めよ」という問題になってCHTで解けるというわけさ。
計算量は、単調性を仮定したdequeを使った実装だと $O(N)$ 、単調性を使わないLi Chao Segment Treeだと $O(N\log N)$ だね。

やー、これで26問全部を解説したわけだけど、どうだったかなー？
私たちは本番ではTWXYZの5問を残して21完で、残った5問は主にsnukeさんの解説を参考にして解説ACしたよ。
ꑄ꒖ꐇꌅꏂ🐈 on Twitter: "DPコン、解法全部書いた。 https://t.co/BqSnOQIkbR"
解説AC含めて全問ACすれば黄色くらいの実力になるんじゃないかな？　私たちが黄色になったばっかりだしねー。
それじゃあねー。

EDPC解説目次へ戻る

*1:1つの頂点を中心にして、そこからたくさんの辺が出てるようなグラフ