続きでーす
このへんから初見で解答があやしいので、疑問点や改善点はぜひコメントください。
N - Slimes
【問題】長さ N の数列 a[i] がある。「隣り合う要素を足して一つにする」という操作を繰り返して 1 つにする。ただしコストがその和だけかかるとする。1 つにするためにかかる最小のコストを求めよ。
【制約】N <= 400. a[i] <= 1e9.
【答え】最後の操作を考えると、残り二つの数字は、ある区間からできたものと、もう一方の区間からできたものである。そこで、dp[l][r] を区間 [l, r) についての最小値として、区間の分け方を試して最小を求めるとよい。なお新たにかかるコストは i in [l,r) の a[i] の和なので、累積和を取っておくとよい。遷移が O(N) で全部で O(N^3) でできる (定数は小さい)
【メモ】区間DP. 典型であるところの「操作の後ろに注目」をすると思いつきやすそう。なおこういうときの区間は半開で取っておくと添え字の処理がやりやすい気がする。
O - Matching
【問題】頂点数 N, N の二部グラフがあるので、完全マッチングの個数を mod 1e9+7 で求めよ。
【制約】N <= 21.
【答え】N が小さいので全探索できそう。順にペアを作っていくとして、bit で相手の集合を表し、dp[bit] を「ここまで bit の表す相手を使ったときの残りの組み方の場合の数」とすれば、遷移が O(N) でできる。具体的には、まだ使ってない相手の中で辺のあるものを全部足せばよい。全部で O(N*2^(N-1)) となる。
【メモ】ビットDP. やはり遷移がたるいのでメモ化再帰にして、何人目まで使ったかも管理したが、これが分かりやすいかは謎。bitの演算をするときに結構失敗する (だいたい括弧を付ければ治る) んですが仕様がわからないですね... 主に演算の順位でバグってる気がするけどどうなんだろう。
P - Independet Set
【問題】木が与えられるので、独立集合 (頂点集合で、隣り合う頂点に置いていないもの) の個数を求めよ。
【制約】頂点数 <= 1e5.
【答え】適当に根を付けて考える。dp[v][col] を、v を根とする部分木について、v に col 個置くときの場合の数とする。このとき、dp[v][1] は v の子 u すべてについての dp[u][0] の積となり、dp[v][0] は v の子 u すべてについての dp[u][0] + dp[u][1] の積となる。あとはメモ化再帰で解ける。
【メモ】通称木DP. 基本作戦は、根を置いてから部分木についての情報管理をするというもの。今回の場合、置くか置かないかで状態数を増やすのがポイント (自然といえば自然だが)。
全方位木DPの記事に大変お世話になった。木DP を書くときは、根を付けること＋DFSの際親の情報を持っておくこと、などを意識すると書きやすい...気がする (木なのでdpテーブルを置かずできるときもあるが、危険回避のため置いておいた方が無難？)。なお全方位木DPはほとんど書いたことないです。
Q - Flowers
【問題】長さ N の数列 h[i], a[i] がある。添え字をいくつか選んで、できる h[i] の部分列が単調増加になるようにするとき、その添え字についての a[i] の和の最大を求めよ。
【制約】N <= 2e5. 1 <= h[i] <= N で h[i] はすべて異なる (i.e. h[i] は{1, ..., N} の置換) 。1 <= a[i] <= 1e9.
【答え】dp[he] を「最後が he の時の和の最大」として、dpテーブルを前から更新することを考える。すでに i-1 番目まで行ってから i 番目を行うときは、he = h[i] についてのみ、dp[he] = a[i] + max_{x in [1, h[i])} dp[x] と更新することになる。遷移が O(N) に見えるが、segment tree を使えば O(log N) でできるので、全体で O(N log N) でできる。
【メモ】データ構造によるDPの高速化。愚直なアイデアだと見ている場所も管理することになるが (これだと最後の高さを考えるのは自然か？) 、1 点しか更新しないため持っておく必要がない。またそのままやると O(N^2) だが、区間の max を見るのといちいち更新するのならセグ木でできる。
いわゆる「実家DP」 とかもこういうタイプの問題だったはず。まあ実家DPしたことないんですけどね。
なお、a[i]=1 なら有名問題 (LIS) だが、その場合は今回の方針の双対としてdp[ct] を「a[i] の和 (=数列の個数) が ct の時の最後の項の min」とおけばよい。遷移を書くと更新する場所がdp[ct-1]<h[i]<dp[ct] となる ct の場所となり、セグ木を使わなくとも、にぶたん (lower_bound) でできる。この解法見た時頭いいなーと思ったが、双対なだけだったんですね。
しかしまあセグ木は便利だなぁ。ライブラリの作者に感謝 (自分で書けよ) (モノイド表記のやつ本当に助かってます) (まじで思考停止できる) (遅延付きまでありがとうございます)。
R - Walk
【問題】数 K および単純有向グラフが与えられるので、長さ K の path の個数を mod 1e9+7 で求めよ
【制約】頂点数 N <= 50. K <= 1e18.
【答え】隣接行列を G = (a[i][j]) (i → j という辺の本数/有無) とする。
dp[i][s][t] を「s からt まで長さ i の path の個数」とすると、遷移の式は sum {k in [0,n-1]} dp[i-1][s][k]*a[k][t] となる。要は k で途中下車して場合の数を数えている。
この式の形から、実は s, t をindexとする行列 (dp[i][s][t]) は G^i で表されると分かる。よって、G^K を計算して各成分を足せばよい。行列累乗を使えば O(N^3 log K) でできる。
【メモ】DPから行列累乗に持っていく典型。今回は露骨というか有名問題だが、そうでなくとも遷移が線形な漸化式の場合は行列累乗で解けることもある (フィボナッチ数列とか)。まあだいたい試行回数 (今回だとK) が異常なことが多いので、察せられることの方が大半か。
行列累乗も (行列ライブラリからパクって) ライブラリ化しておいた。これで思考停止で書けるね！やったね！
S - Digit Sum
【問題】数 K, D が与えられるので、K 以下の正整数のうち各位の和が D の倍数のものの個数を mod 1e9+7 で求めよ。
【制約】K < 1e10000 (i.e. 文字列として長さ 1e4 以下). D <= 100
【答え】K が大きいので、上手く全部の数を拾うようにしたい。K[i] を K の上から i 桁目 (0-indexed) までみた時の値とし、dp[i][r] を「0 以上 K[i] 以下で各位の和が r mod D のものの個数」とする。
ここで K[i+1] 以下の数は、K[i] 以下の数の下に 0 から 9 をくっつけた (+例外処理をした) ものとみなせる。これを念頭におくと、dp[i][r] からの遷移は、0 <= d < 10 について dp[i+1][(r+d)%D] へそのまま寄与し、r = sum[i]%D (sum[i] は K[i] の各位の和) かつ d>S[i+1] のものだけ -1 する、という形になる。あとはこれを「配るDP」としてそのまま実装すればよい。なお 0 を入れたので最後に -1 すること。
計算量は、N を Kの桁数で d 進法として、O(KDd).
【メモ】いわゆる桁DP. ビット列がらみ (XORとか使う問題) でたまに出てきたりする。今回みたいにある数以下すべてを 1 回ずつ拾うときは、うまく処理する必要がある。今回は「上から見る→10倍して送る」を繰り返せばできる。
昔のABCであった七五三数の問題もそんな感じだったような。そのときは「各桁が7, 5, 3 のいずれかで少なくとも1回使われている数」を七五三数とよび、与えられた N 以下で D の倍数のものの個数をカウントするという問題で、DFSで全部呼び出す (+使ったかどうかのフラグ管理もする) という作戦で解けたはず。
その他、ビット列 b 以下の数をすべて拾うときは「上から i 桁固定して -1 し、それ以下を自由とする」みたいな取り出し方もよくやる気がする。いずれにせよ、遷移が結構だるいことが多いので、紙になどメモして丁寧にやるのが精神的にもいいと思う。
あと、微妙にオーバーフローさせてしまった。1e9+7 系は long long で扱う方が無難かなぁ (足し引きだけだと int でできるけど注意が必要)。
T - Permutation
【問題】1 から N までの置換してできる順列 p[i] について、隣り合う数の大小を表す長さ N-1 の不等号の列 を対応させることを考える。いま、逆に不等号列 S を与えたとき、それに対応する順列は何個あるか mod 1e9+7 で求めよ。
【制約】2 <= N <= 3e3.
【答え】例によって順列は 0-indexed とする。
dp[i][la] を「0 から i までの順列で、そこまで条件をみたし、最後が la のものの個数」とする。遷移を考えるとき、i までの順列で 最後が la のものを、i-1 までの順列と一対一対応させる。これは la より大きい数を la-1 にして送れば作れる。この対応を使えば、遷移が書ける。具体的には、S[i-1] == '<' なら dp[i][la] = sum_{0<=k<la}dp[i-1][k], S[i-1] == '>' なら dp[i][la] = sum_{0<=k<la}dp[i-1][k] となる。和は累積和を同時に求めれば O(1) でできるので、遷移が O(1) になり、全部で O(N^2) で解ける (定数は小さい)。
【メモ】順列をいかに全部拾うか。問題の制約上一番後ろは管理する必要があるので、それを加味するとこういう対応がわかりやすくていいと思う。順列の問題は何となく苦手意識があって、完全マッチングと対応が付いたりもするので (箱根駅伝DP？知らない子ですね...)、もう少し練習の余地がありそう。
累積和を取るのは慣れた。コツとして、累積和の条件式も紙に書き出すといいと思います、人間そんなにソラで計算できないので (僕の頭がロースペックなだけかもだけど...)。
U - Grouping
【問題】N 頂点の完全グラフがあり、各辺に価値が定まっている。頂点を適当に色を塗り、同じ色の頂点を結ぶ辺以外は消す。うまく色を塗って、残った価値の和を最大化したい。その最大値を求めよ。
【制約】N <= 16. abs(values) <= 1e9.
【答え】used をすでに使ったかを表すビット列とし、dp[used] を残りの頂点での答えとする。このとき、dp[used] の遷移は、残りを i 個として、最後は使うようにした 2^(i-1) 通りの取り方を全部試せばよい。sum[bit] を「bitの表す集合について完全グラフの辺の価値の和」とおきこれを前計算しておけば、dp[used] の遷移は 2^i 通り試すごとに O(1) で行える。全部で何回試すかは、二項係数＊二べきの和でだいたい (3^N)/2 くらいで、ギリ間に合う。なお sum[bit2] の前計算は O(N*(2^N)) でできる。
【メモ】管理の仕方は割と自然だが、計算量をどう減らすかが問題。適切な処理で、定数の小さい O(3^N) でできるようになる。
ちなみに N 個の grouping の個数を Bell number とよぶそうですねしらなんだ。B[5] が源氏香で有名なあれです。
V - Subtree
【問題】頂点数 N の木と数 M が与えられる。頂点 v に対し、v を元にもつ部分頂点集合であって辺で連結なものの個数を mod Mで求め、すべての v に対し出力せよ。
【制約】N <= 1e5. M <= 1e9.
【答え】v を根としたとき、v についての答えは、v の子 u に対し u を根とする部分木についての答えを ct[u] と したとき、prod_{u is child of v} (ct[u]+1) となる (+1 は、全部白もOKなため)。全部の頂点を根として試すと O(N^2) かかるが、全方位木DPをすれば問題ない。具体的には、根を fix して答えを求めたのち、子に親方向の場合の数の情報を伝播させるとよい。ここで情報を送る上でボトルネックになるのが次の問題：
長さ k の数列 a[i] があるので、各 i に対し prod_{j != i} a[i] mod M を求め出力せよ。
M が素数だと逆元が取れるため、全部かけてから割ればよい。しかし今回は一般の合成数なので逆元が使えず面倒。やりかたとしては M を素因数分解し、各素因数の個数と互いに素パートにわける。互いに素パートは逆元を使え、素因数の個数は肩の数字の足し算に変わったので同じ方法でできる。よって O(k log M) くらいではできる。
情報の伝播ごとにこの問題を解く必要があるが、それでも全部で O(N log M) でできる。
【メモ】実装が辛かった... けど、主だったバグが無かったのでまだ胃に優しかった。
全方位木DPを真面目に実装したのはほぼ初めてだったけど、たしかに割と思考停止で書けるということが分かった。木DPは「子の情報を親に流す」、全方位木DPは、木DP＋「親の情報を子に流す」というイメージで。
W - Intervals
【問題】正整数 N と M 個の区間 I[i] が与えられる。区間はすべて [1,N] に含まれる。また各区間 I[i] にはスコア a[i] が定まっている。長さ N の 01 列 S (1-indexed) に対し、S のスコアを次のように定める：
ある j in I[i] に対し S[j]=1 となるなら、a[i] を加算する。これをすべての i について行う。
S をうまく定めて得られるスコアを最大化したい。最大値を出力せよ。
【制約】 N, M <= 2e5. abs(a[i]) <= 1e9.
【答え】まず区間を右端で分類する。M 個の区間のうち右端が k のもの全体を J[k] とおく。
さて、dp[i] を「最後に 1 が現れるのが i 番目のビット列についての最大値」とする。たとえば N = 5 の場合、ビット列を i = 0 の方から 00000, 10000, ?1000, ??100, ???10, ????1 と分類することになる。このとき、????1 については、J[1] から J[4] までで考えたスコアの最大値に、J[5] のスコアの総和を足したものとなる。また、???10 については、J[1] から J[3] まで考えたスコアの最大値に、J[4], J[5] のうち 4 番目をもつもののスコアの総和を足したものとなる (?がどんな内容であっても成り立つ！！)。以下同様である。
したがって、dp テーブルを次のように順に更新していけばよい：
-- 「k フェーズ」を、J[1] から J[k] までで考えたスコアの最大値とする。
-- 最初は dp[0]=0 だけ記入されている。
-- k-1 フェーズまで終わったとする (dp[i] は i = k-1 まで記入されている)。このとき、まず dp[k] をmax_{0<= i <= k-1} dp[i] とする (いままでのスコアの最大値)。その上で、J[k] の元すべてについて、対応する区間の dp[i] にそのスコアを加算する。
-- N フェーズまで終わったら、max_{0<= i <= N} が答えとなる。
やること自体は、区間への値の加算と、ある区間についての最大値の出力なので、遅延セグ木を用いれば一回あたり O(log N) でできる。よって全体で O( (N+M)log N) で解ける。
【メモ】天下り的に解答を書いたが、実際にはかなり紆余曲折があったし相当悩んだ。
アプローチの一つは、2^N 通りあるビット列を O(N) 個のパターンに分類すること。桁DPとかでよくみる分類ですね。
もう一つのアプローチは和の取り方を工夫すること。この問題が「1 のある場所には重複してスコア加算する」だったら簡単で、場所ごとにみて正の部分だけ 1 にすればよい (場所ごとのスコアは遅延セグ木かいもす法で求まる)。しかし今回は 一回までしか加算しない。どうするか？ここでさっきのビット列の分類を考えると、?...?10...0 の形については、1 のある場所より前の区間だけみた最大値と、それ以降で 1 のある区間のスコアの和となる (後者を一回だけ足せるようになった！)。そこで区間の右端での分類と足す手順に気付けるかもしれない。ちなみにこの「ちょうど一回足すよう工夫する」アイデアは ARC068 - E Snuke Line で用いた気がする。
以上。なんとか自力で解けてよかった。しかしまあやってる操作はシンプルなので、こういう手順で解けるのはなんか不思議だなぁ...
X - Tower
【問題】N 個の物体があり、各物体 i に対し値 w[i], s[i], v[i] が定まっている。いくつか選んで次をみたすように一列に並べる。
一列に並べた物体を i[1], ..., i[k] で表す。各 j 番目について、sum_{p<j} w[i[p]] <= s[j] となっている。
並べた物体についての v[i] をその列の価値とする。うまく並べて価値を最大化したい。その最大値は？
【制約】1 <= N <= 1e3. 1<= w[i], s[i] <= 1e4. 1<= v[i] <=1e9.
【答え】まず条件を満たす物体の並べ方を 1 つとってくる。これに「正規な順序」を入れることを考える (そうすれば最初から正規な順序のものだけに帰着できるので、並べ方を無視できる)。隣り合う物体 a, b についての条件を精査すると、 w[b]+s[b] <= w[a]+s[a] ならば、順番を b, a に入れ替えてもよいと分かる。よって、はじめから w[i]+s[i] の昇順に並べておけば、ナップサックのように解くことができる。
上記のようにソートしたのち、dp[i][we] を「i 番目までで重さ we の時の価値の最大値」とする。dp[i][we] からの遷移は、物体 i+1 を置かないならそのままの価値で dp[i+1][we] へ、置けるなら dp[i+1][we+w[i+1]] へ、maxを取る形で移行する。最終的にmax_{we}dp[N][we] が答えとなる。なお、総重量は S = max_{i} s[i], W = max_{i} w[i] と置いて、S+W でおさえられる。したがって、計算量は O(N(S+W)).
【メモ】同じような問題をどこかでみたような...(どこかわすれちゃった)
全部試そうとすると、順列も込みで N!くらいはかかる。そこで、条件を満たす順列の中で「特別なもの」を定義し、特別なものに帰着させる。それにより、順列から部分集合にまで落とせる。それでも 2^N だが、ナップサック問題になったのでこれで O(N*重さ) に落とせる。
この「特別なものだけ考慮し帰着させる」のは今後も使えそう。帰着させるときは、隣り合う関係 (局所的な様子) に注目するとわかりやすい。そこで何かしらの量 (今回は w[i]+s[i]) が見つかったら、それを大域的に適用できるという流れ。
パッと思いついて気持ちよかった (こなみ)。これこれ！こういうことがやりたかったんよ！
【追記】同じ問題と言ってたものが見つかった。探したら昔解いて記事にしてた。CODE FESTIVAL 2017 Final D - Zabuton 700 です。
Y - Grid 2
【問題】H - Grid に同じ。ただし制約が異なる。以下問題を再掲。
H*W のグリッドが与えられる。グリッドの各マス目は空か障害物がある。左上から右下までのマスを伝った最短経路のうち、障害物のないマスのみを用いたものは何通りあるか？mod 1e9+7 で求めよ。
【制約】H, W <= 1e5. 障害物は N 個で、N <= 3e3.
【答え】以下始点を (0,0) として座標を入れる。また i 番目の障害物の座標を (h[i], w[i]) とおく。
終点も障害物があるとし、長さ N+1 のビット列を考え、障害物を踏むか踏まないかを表すとする (1が踏む、1-indexed)。求めたいのは 00...01 に対応する場合の数である。そこでそれを dp[N+1] と置き、1 <= i <= N なる i についても 同様に dp[i] を定める。
説明の簡略化のため例として i=5 の場合を考えると、00001 の場合の数を求めるには、????1 の場合の数から、1???1, 01??1, 001?1, 00011 の場合の数を引けばよい。
それぞれの場合の数は、B(r,c) := _{r+c} C_{c} として、B(h[5],w[5]), B(h[5]-h[1], w[5]-w[1])*dp[1], B(h[5]-h[2], w[5]-w[2])*dp[2], B(h[5]-h[3], w[5]-w[3])*dp[3], B(h[5]-h[4], w[5]-w[4])*dp[4]. となる。i が一般の場合でも同様である。よって組合せを前計算により O(1) で計算できるようにしておけば各遷移は O(i) でできるので、全部で O(N^2) でできる。
ただし、この方法には落とし穴があって、障害物の位置関係によっては同じルートを二回以上引いてしまう可能性がある。理由は、??? を計算した部分で以前の箇所を通ってしまう可能性があるため。回避策としては、i 番目から終点までに i-1 番目以前が存在しないようにすればよい。そこで予め座標を h[i] の方で昇順ソートしておくと、問題なく解ける。
【メモ】この設定と同じ問題をこどふぉ乱取りで発見して (scoreが 2500 か 3000 だった)、面倒そうだから放置してたんですよね...でもWを解いた経験から、割と素直に解けるのではと思い直し、やってみたら普通に解けました。
N 個すべて通らない方法なので包除原理でも使うのかなと思ったけど、部分集合同士をまとめるすべがよく分からなかったので、少し方針を改めることに。踏むかどうかをビット列で表し、2^N パターンから、計算できる O(N) パターンに減らせば、できました。W有能すぎる。
なお、最初 TLE を吐いてしまった。原因は組合せの計算の際いちいち逆元を計算していたら、O(N^2*log(H+W)) かかってしまった、というもの。そこで最初から逆元も計算しておくことで O(N^2) に改善できました。その分前計算が O*1 になっているため、問題の設定によっては (H+W が大きいケースとか) 逆元を取る場所を変える必要があるかも。いちおうライブラリとしては O(1) の方法を残しておくことにしました。
あと 1 問！
*1:H+W)log(H+W
