Educational DP Contest / DP まとめコンテスト〈EDPC〉補習篇（T,U,V,W,X,Y,Z）

コンテスト後に読んだ問題たち。ここで出てくるテクニックもこの機会にぜひ身につけておきたい。

参考：
www.hamayanhamayan.com
kyopro-friends.hatenablog.com
↑競プロフレンズさんてチームで戦ってるの？それって規約的にどうなの？*1

〜

T - Permutation (100)

<><

かわいい
それはさておき

dp[n][k] = n番目(n≧1)まで来たときに長さnで最後がその中で小さい方からk番目(1≦k≦n)であるパターン数
dp[1][1] = 1
n番目が < のとき:
- dp[n][1] = 0
- dp[n][k] = dp[n][k-1] + dp[n-1][k-1] for k>1
n番目が > のとき:
- dp[n][n] = 0
- dp[n][k] = dp[n][k+1] + dp[n-1][k+1] for k<n
答えはΣ dp[n][1..n]

$O(N^2)$ ですね
→AC
https://atcoder.jp/contests/dp/submissions/3962656

U - Grouping (100)

U - Grouping
うさぎ16匹の相性を加味したグループ編成

all[集合]: その集合に含まれるうさぎを全て同じグループに入れた場合のスコア
- bitDPっぽく求められる。 $O(N\cdot 2^N)$
dp[集合]: その集合に含まれるうさぎを同じグループに入れたり入れなかったりでの最高スコア
- dp[集合]=all[集合] から始めて、区間DPっぽい感じで max(dp[部分集合] + dp[補集合]) みたいに更新していく (その + の部分は同じグループにならない境目と考えられる）
- っぽくない？
  - dp[集合]の計算は集合のサイズをkとすると通りで、で21523360
    - O(3^N)ってやつね ( $3^{16}\times\frac{1}{2}=21523360$ )
  - それにビット集合の演算が加わるが高々16ビットなので間に合う

こんなの書いたけど

inline int make_pq(int p, int q, int n) {
    // pの立っているビット (n箇所あるはず）にq (下位nビット)をあてはめる
    int x = 0;
    for (int i=0,b=1,m=1; i<n; ++i,m<<=1) {
        while (!(p & b)) b <<= 1;
        if (q & m) x |= b;
        b <<= 1;
    }
    return x;
}

→AC
https://atcoder.jp/contests/dp/submissions/3962870 659ms

V - Subtree

V - Subtree
（先にX,Yを解いてから）
あるノードが黒で、そこと繋がる範囲だけが黒な場合の数。
全方位DPなんだろうけどどうしたらいいか分からない
いや、メモ化再帰で答えが合うやつは書けるんだけどTLE出るし
https://atcoder.jp/contests/dp/submissions/3963654

何を計算すべきかは分かるんだけど、MODが素数じゃないせいで「全ての積から１つ割る」作戦が使えず計算量が減らせない…

すぬけ先生のヒントを見る

後編書きました。全方位木DPの復習と、"zerokugi法"なるものの計算量解析についてです。https://t.co/ZcVvhp7SDO
— ꑄ꒖ꐇꌅꏂ (@snuke_) 2019年1月16日

というかzerokugi法をなぞってみる。

degreeの大きい順にノードを巡回
dfs(v) = ノードvについての答え（ノードvへの全ての入力を掛け合わせた値）
- 各入力に+1したものを掛け合わせる。（この1はそのノードがoffな場合の数）
dfs(v, u) = ノードuの隣りのノードvへの、ノードu以外からの全ての入力を掛け合わせた値
- これを dp[u][i] とする。iはvがuの隣接ノードの中で何番目かを表す。
- iが連続していることは（メモリ効率だけでなく）後で子からの入力を累積する時に役に立つ。
あるノードについてdfs(v)が定まったということは、vに隣接している各ノードuについて dfs(v,u)の値を計算できるチャンス
- 「u側からの入力」以外の入力を掛け合わせたもの
- あるいはdfs(v)の値を「u側からの入力」で割った値
  - 気の利かないMODのせいで割り算では辛い
- 左からi番目までの入力の積、右からj番目までの入力の積、みたいなのを用意してまとめてやることででvに隣接するすべてのノードの分が計算できる
  - これは全体でも $O(N)$

→AC
https://atcoder.jp/contests/dp/submissions/4069199

追記

記事を見に来て下さったにも関わらず、なぜかこっちの方法を採用されてた方がいたので追記します。
僕のオススメはあくまでも上に書いた方法です。（定数倍、実装量、ロジックの簡潔さなどの点から）
名前が付いてなかったのがいけなかったんでしょうか。。。
とりあえず上の章で説明したものを「snuke法」と名付けておきます...
あと、zerokugiさんの方法っぽくやる場合でも次数の降順より行きがけ順の方が定数倍が良いです。
木と計算量後編〜全方位木DP〜 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ

ごめんなさいごめんなさい
（zerokugi法のほうがその時自分の頭の中にあったイメージに近かったので飛びついた気が）

snuke法で書き直してみた
snuke法では

どこか1つのノードを根として、そこからすべての部分木について「下側（葉側）だけ」計算する (dfs)
全ての隣接ノードからの情報の積が求まったから順に（＝最初に根としたノードからbfsで）「上からの情報」を送り、欠けていた情報を埋めてさらに「下側（葉側）」に伝播する。この過程で各ノードについての答えは求まるので記録しておく。
記録しておいた答えを表示しておしまい。

なるほど。
→AC*2
https://atcoder.jp/contests/dp/submissions/4087582

W - Intervals

W - Intervals
区間に対してボーナス/ペナルティがあってというやつ

左から１つずつ決めていく系？
- 1にする場合はそこに掛かっている区間を全部消去してしまえるけど
- 0にする場合はそれらを後で踏む可能性があるので消去できない
合計が正の値で大きいところから貪欲にとか？
- 同じ区間は１度しか数えられないし駄目だろ

攻めあぐねた

ferinさんのブログ

EDPC W - Intervals - ferinの競プロ帳
遅延セグ木（merge=max, op=+) を使ってた

左側が確定しているとして、次を1にした場合どうなるかを見ていけばいいということか。
（次を0にした場合は1つ前と同じスコアなはずなので考慮不要）
でもどうやって？

区間を終端ごとにまとめておく

i番目を0にしたときのベスト = i-1番目までのベスト = [0,i) に対するクエリの結果
- [0,i) に対するクエリでベストが得られる仕組みは後で考える
i番目を1にするときは？
- i-1番目までのベストの値を区間 [i,i] に追加してしまう
- そこで終わる区間をすべて遅延セグ木に追加
  - この時点でセグ木の中はi番目まで全て1にされた状態 + 各地点でのベストの値が登録された状態
- ここで [0,i) に対するクエリをするとどうなる？値が最大になる区間の値が出てくるはずだけど

うーん

各[i,i+1)には、[0,i)の範囲で完結する区間について考慮したベストが入っている（ということにしよう）
- その値を書き込んだ時点ではi+1以上の範囲にかかる区間は考慮されていない
iで終わる区間、即ち [α,i+1) をすべて追加すると、[i,i+1) の合計は（i+1での更新までの間）「i番目を1にした場合のベスト」を表すことになる
その後、i+1以降の更新でi+1以降にかかる区間が追加されることで、[i,i+1) の合計は「i番目以降をすべて1にした場合のベスト」を表していることになる？
- それでいい。そこを1にするってことはそこで踏んでいる全ての区間の影響も受けてもらうってことだから。
- で、そこを1にしなかった場合のベストは保持されるのか？

サンプル1（答えは20）

[ 0 ]
[ 0, 0 ]
[ 10, 10, 10 ]
[ 10, 0, 0, 0 ]
[ 10, 0, 10, 10, 20 ]

サンプル5（答えは10）

[ 10 ]
[ 10, 10 ]
[ 4, 4, 4 ]
[ 4, 4, 13, 13 ]
[ 4, 4, 13, 13, 14 ]
[ 0, 0, 10, 3, 4, 4 ]

そこを1にしなかったと言ってもそれ以前に1を使ったことがある中でのベストであり、当然以降の1の影響を受ける。ただそれだけのこと。すべてが0なら全く影響を受けない代わりにゼロである。
だいたい納得。

で
このferinさん解法は遅延セグ木を使っているんだけど、いい機会だから遅延セグ木について少し深めておこうと思ってbeet先生の記事を読んだ。

半群とかモノイドって？？と最初思ったけどそんなに難しい概念というわけではない
実装を読んで、変数や関数の名前を自分にしっくりくるものに置き換えてみたりした。

→AC
Submission #4076551 - Educational DP Contest / DP まとめコンテスト

X - Tower

X - Tower
こういう問題どこかで前に見たよね
それはさておき

可能なsub塔を $s_i$ が小さい順に見ていく？
いや
あるブロックの上に0個以上のブロックが積まれているとき
そのブロック（重さ $w_i$ ）の上にはそいつの丈夫さ $s_i$ 以下の重さの物が載っていて、重さの合計は $s_i+w_i$ かそれ以下になる。

１つ言えるのは、いくつかのブロックが積まれている時、この「重さの合計」の値は必ず昇順に並ぶ。（wもsも1以上なのでstrictに昇順になるはず）*3

なので逆に、とりあえず $s_i+w_i$ を昇順に並べておいて、使うか使わないかによって価値をDPしていけば良いのでは？
dp[何番目まで使った][そこまでの重さの合計] = 価値の合計の最大値
で、重さの合計は丈夫さ上限 ( $10^4$ ) を上回ることはない（※）ので $10^3\times 10^4$ だし余裕でしょ
→RE(1)
※はい、重さの合計の最大値は（丈夫さ上限＋最後のブロックの自重）なので $2\cdot10^4$ ですね
直して
→AC
https://atcoder.jp/contests/dp/submissions/4063174
自力AC出来て嬉しい

Y - Grid 2

水平区間・垂直区間を壁があるごとに更新していく作戦 → O(N)なりO(NlogN) で更新する式が立てられず断念
全体から壁を通る分を引く作戦 →どう重複するのか読めなくて断念
座圧したら行けるのか？そんなことはないだろ

TLからヒント情報：重複排除は包除原理で行けるとな（なるほど）
とすると
dp[ある壁][何個目]=経路数
で
何個目ってところは包除原理なので偶奇だけ分かればいい。
壁と壁の繋がりのグラフをtopological sortして先頭から試す感じ？
やってみる
→TLE連発…
topological sortがうまく行ってなくてループしてるとか？
単に左上から右下へと順番に見ていくだけで良いのでは？
→AC
https://atcoder.jp/contests/dp/submissions/4064928
はい

Z - Frog 3

Z - Frog 3
$N=2\times10^5$ なのでFrog 2の方法では $O(N^2)$ で死
TLにCHTというワードが出ているのだけれど何それ
CHT=Convex Hull Trick
でもそこまでどう持っていく？

2つの区間があって、それぞれの高さ差分を a,b とすると、この2区間を繋ぐ（１つ飛ばす）ことで削減できるコストは C-2ab である（∵ $(a^2+C)+(b^2+C)-((a+b)^2+C)$ ）
3つの区間があって、〃 a,b,c とすると、この3区間を繋ぐ（2つ飛ばす）ことで削減できるコストは 2C - 2(ab+bc+ca) = (C-2ab) + (C-2bc) + 2ac である
4つの区間があって、〃 a,b,c,d とすると、〃 3C - 2(ab+bc+cd+da+ac+bd) = (C-2ab) + (C-2bc) + (C-2cd) + 2(ac+bd+ad) である

てな辺りまでは考えたんだけど…これをどう最適化していく？

（続く）

競プロフレンズ先生の解説を途中まで読んで

EDPC解説 U～Z - kyopro_friends’ diary

あ
まず考え方のスタート地点が違う

DP問題って分かってるんだし、まず

dp[i] = 位置iに到達する最小コスト

を置こう。

そうすると

dp[i] = min(dp[j] + $(h_j-h_i)^2 + C$ )

で、 $h_j$ の関係ない項をminの外に出せて

dp[i] = $(h_i^2 + C)$ + min(dp[j] + $h_j^2-2h_jh_i$ )

$a_j=2h_j, b_j=dp[j]+h_j^2$ と置くと

dp[i] = $(h_i^2 + C)$ + min( $-a_jh_i+b_j$ )

といった形になっていて、これは傾きが負な直線( $y=-ax+b$ )の集合の中で $x=h_j$ で一番下に来るものを探す問題になっている。なるほどconvex hullだ。

動かす（舐める）変数と関係ある項と関係ない項にくくり分ける、というのは定石。
こないだ解いたTestProctoringでもけんちょん先生が綺麗にやってた。

傾きが負の直線をどんどん追加して行ったときに、convex hullの表側にもう出てこなくなった過去の直線を消して行くことで探索範囲を絞れる（しかもそれがdequeで実装できる）、というのがConvex Hull Trick (CHT)らしい。
蟻本の上級編のAnonymous Sequence (POJ)の解説に図解がある。

とりあえず写経しながら理解しようと思いつつ、どっちが先頭でどっちが末尾？って迷った。

後から追加するやつ：末尾（deq.push_back()で追加。deq.pop_back()で捨てられる）
一番古い生き残り：先頭（deq.front()あるいはdeq[0]で見られる。deq.pop_front()で捨てられる）

で、

直近の2本とこれから追加する1本を並べて、真ん中の（最後に追加した）1本がもうconvex hullの表に出てこないと判定できればdeqから捨てる（捨てられなくなるまで見ていく）
現在のの値でが最小値になるものをdeqの先頭（古いほう）から見ていく、というか2番目のほうが小さければ1番を捨てるの繰り返し。
- なんで総当たりじゃなくて古い方からの2つだけの比較で足りるのか？ →この条件だと必ず1本ずつしか入れ替わらないのか

だいたい分かった。
$a_i,b_i$ がdp[i]の値に依存するのを忘れて計算順序を入れ替えようとして変な値が出たりしたけど直せた。

→AC
https://atcoder.jp/contests/dp/submissions/4088607

＼わーい全部解けたー！！／

*1:嘘ですこないだDDCC Finalで御本人拝見しました

*2:ローカルでは最悪ケース（10万ノードを１本に繋げたやつ）でstack overflowしたので ulimit -s 16384 して通しました。

*3:必ずとか言っちゃってるけど本当にそうなのか不安

naoya_t@hatenablog

いわゆるチラシノウラであります