AtCoder Library Practice Contest 解説
AtCoder Libraryの公開と同時に, AtCoder Library Practice Contestなるものが設置されました.
↓これ
ACL Contestの前にこれを解いておくと良さそうなのれふが, 解説が少ないようなので簡易的に……
※AtCoder Libraryの使い方や, 含まれるアルゴリズムの詳細の解説はあまりしません.
A-Disjoint Set Union/B-Fenwick Tree/C-Floor Sum/F-Convolution/G-SCC/J-Segment Tree
これらの問題は, 問題文中で求められる機能そのものがAtCoder Libraryにあるため, それを使えば良いれふ.
配布されているzipファイル内に入っているdocument_ja内を確認しながら, 使えるようになりましょう (まだ目を通していないとしたら, index.htmlが初めに読むべきドキュメントれふ). ACLPCの各問題に対する実装例も, 個別のライブラリのドキュメントの下の方に載ってまふ.
D-Maxflow
Maxflowで二部マッチングを解く問題れふ. マス目は, 黒と白の市松模様で全体を塗ることにすると, タイルはちょうど1マスの白マスとちょうど1マスの黒マスを覆う事になりまふ. 隣接する(障害物のない)白マスと黒マスが合コンにおける男と女のような関係になるため, 二部マッチングと見なせまふ.
具体的には, 次のようなmf_graphを作り, から
への最大流を求めることで置けるタイルの枚数の最大値が求まりまふ.
- 始点にあたる頂点
と, 終点にあたる頂点
を持つ
個のマスに対応する
- 障害物の無い頂点に黒マスに対応する頂点から,
- 1枚のタイルで覆う事の出来る白マスと黒マスに対応する頂点の間に, 最大容量1の辺を持つ
mf_graphのflowを呼び出すと, 最大流が求まりまふが, その内部では今まで追加した辺それぞれに対し, flowのシミュレーションによってどれだけ水(?)が流れたかが保存されていまふ. edges()によって得られた辺のうち, flowの値が1のものは水が流れた(=マッチングが成立した)ということなので, この情報をもとに復元すればこの問題が解けまふ.
E-MinCostFlow
mcfグラフに, 負のコストの辺を追加できるとして, この問題の解き方を考えまふ(実際にはACLのMinCostFlowは非負のコストの辺しか追加できないのれふが, 最後に対処しまふ).
総和の最大化を, 選んだマスの整数の-1倍の総和の最小化とみなすことで最小費用流で解けるようになりまふ. 見たこと無いと厳しい気がしまふが, 以下のようなmcf_graphを作りまふ.
- 始点にあたる頂点
個の行に対応する
- 始点から行に対応する頂点それぞれに, 最大容量
, コスト0の辺を持つ
- 列に対応する頂点それぞれから終点に, 最大容量
番目の行に対応する頂点から
番目の列に対応する頂点に, 最大容量1, コスト
の辺を持つ
- 始点から終点に, 最大容量
, コスト0の辺を持つ
そして, から
に
の水を流した時のflowを求めれば, 最大値の-1倍が求まりまふ.
ただし, 先に説明したように, ACLの最小費用流ではコストが負の辺を追加できません. そこで, 十分大きな定数を用意し,
などをコストとすることで求められた答えから
を引いて対処する必要がありまふ.
また, 復元はMaxflowの時と同様に……
H-Two SAT
本の旗それぞれに対し, その旗を
の位置に置くならばtrue, そうでなければfalseを取る変数を考えまふ.
差が未満の2か所すべてに対し, 少なくとも一方には旗が置かれないようにすれば良いれふ. 例えば, 旗0の
と旗1の
の差が
未満の時, add_clause(0,false,1,true)としまふ.
I-Number of Substrings
LCP配列の番目の要素は, Suffix Array上で
番目の接尾辞と
番目の接尾辞を比較して, 先頭の何文字が共通しているかを表していまふ.
これを利用し, すべての部分文字列(重複有)の数から, Suffix Array上で一つ前の文字列と共通している文字列の接頭辞の個数を引いていけば, 部分文字列の個数を重複なく数えられまふ.
K-Range Affine Range Sum
元々の総和がであるような, 長さ
の区間にタイプ0の操作を行うと, 総和は
から
に変化しまふ. このことから, モノイドとして, 総和と区間の長さを持たせる必要がありまふ.
また, 写像の合成は, と
をこの順に適用させるものとすると,
となりまふ. 合成前も後も,
の係数と定数項によって表せるので, これらを持っておくことになりまふ. なお, idは
れふ. また, compositionは, 先に適用させる写像が2番目の引数となる仕様のようなのでご注意ください.
実装の際は, modintの利用をお勧めしまふ. modint.htmlには「必ずしもこのファイルの内容を確認する必要はありません」と書かれていまふが, この問題を始め, 多くの場面で有用れふ.
L-Lazy Segment Tree
モノイドとして, 転倒数の他に, 区間に含まれる0の個数と1の個数を持たせまふ. 区間のマージに際し, 転倒数は, 左右の区間のそれの和に加えて(左側の区間の1の個数×右側の区間の0の個数)だけ増えまふ.
変更クエリれふが, 0/1を切り替えるだけなので, 区間ごとにこれまでクエリが適用された回数の偶奇を覚えておけば良いれふ.
切り替えクエリを適用した場合のモノイドの変化れふが, 0の個数と1の個数が入れ替わるのは良いとして, 転倒数の変化を頑張って追う必要がありまふ. 結論としては, 元々の0/1の組が(0の個数)×(1の個数)で, そのうち左が1であるものがもともとの転倒数なので, 引き算でもともと右が1であるものを求め, 置き換えれば良いれふ.
