AtCoder Library Practice Contest 解説

 AtCoder Libraryの公開と同時に, AtCoder Library Practice Contestなるものが設置されました. 

↓これ

atcoder.jp

 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を作り, sからtへの最大流を求めることで置けるタイルの枚数の最大値が求まりまふ.

  • 始点にあたる頂点sと, 終点にあたる頂点tを持つ
  • NM個のマスに対応するNM個の頂点を持つ
  • sから, 障害物の無い白マスに対応する頂点に最大容量1の辺を持つ
  • 障害物の無い頂点に黒マスに対応する頂点から, tに最大容量1の辺を持つ
  • 1枚のタイルで覆う事の出来る白マスと黒マスに対応する頂点の間に, 最大容量1の辺を持つ

 mf_graphのflowを呼び出すと, 最大流が求まりまふが, その内部では今まで追加した辺それぞれに対し, flowのシミュレーションによってどれだけ水(?)が流れたかが保存されていまふ. edges()によって得られた辺のうち, flowの値が1のものは水が流れた(=マッチングが成立した)ということなので, この情報をもとに復元すればこの問題が解けまふ.

 E-MinCostFlow

 mcfグラフに, 負のコストの辺を追加できるとして, この問題の解き方を考えまふ(実際にはACLのMinCostFlowは非負のコストの辺しか追加できないのれふが, 最後に対処しまふ).

 総和の最大化を, 選んだマスの整数の-1倍の総和の最小化とみなすことで最小費用流で解けるようになりまふ. 見たこと無いと厳しい気がしまふが, 以下のようなmcf_graphを作りまふ.

  • 始点にあたる頂点sと, 終点にあたる頂点tを持つ
  • N個の行に対応するN個の頂点を持つ
  • N個の列に対応するN個の頂点を持つ
  • 始点から行に対応する頂点それぞれに, 最大容量K, コスト0の辺を持つ
  • 列に対応する頂点それぞれから終点に, 最大容量K, コスト0の辺を持つ
  • i番目の行に対応する頂点からj番目の列に対応する頂点に, 最大容量1, コスト-A{i,j}の辺を持つ
  • 始点から終点に, 最大容量NK, コスト0の辺を持つ

 そして, sからtNKの水を流した時のflowを求めれば, 最大値の-1倍が求まりまふ.

 ただし, 先に説明したように, ACLの最小費用流ではコストが負の辺を追加できません. そこで, 十分大きな定数Xを用意し, X-A{i,j}などをコストとすることで求められた答えからNKXを引いて対処する必要がありまふ.

 また, 復元はMaxflowの時と同様に……

H-Two SAT

 N本の旗それぞれに対し, その旗をXの位置に置くならばtrue, そうでなければfalseを取る変数を考えまふ.

 差がD未満の2か所すべてに対し, 少なくとも一方には旗が置かれないようにすれば良いれふ. 例えば, 旗0のXと旗1のYの差がD未満の時, add_clause(0,false,1,true)としまふ.

I-Number of Substrings

 LCP配列のi番目の要素は, Suffix Array上でi番目の接尾辞とi+1番目の接尾辞を比較して, 先頭の何文字が共通しているかを表していまふ.

 これを利用し, すべての部分文字列(重複有)の数から, Suffix Array上で一つ前の文字列と共通している文字列の接頭辞の個数を引いていけば, 部分文字列の個数を重複なく数えられまふ.

K-Range Affine Range Sum

 元々の総和がxであるような, 長さk区間にタイプ0の操作を行うと, 総和はxからbx+ckに変化しまふ. このことから, モノイドとして, 総和と区間の長さを持たせる必要がありまふ.

 また, 写像の合成は, ax+bcx+dをこの順に適用させるものとすると, (ac)x+(bc+d)となりまふ. 合成前も後も, xの係数と定数項によって表せるので, これらを持っておくことになりまふ. なお, idは1x+0れふ. また, compositionは, 先に適用させる写像が2番目の引数となる仕様のようなのでご注意ください.

 実装の際は, modintの利用をお勧めしまふ. modint.htmlには「必ずしもこのファイルの内容を確認する必要はありません」と書かれていまふが, この問題を始め, 多くの場面で有用れふ.

L-Lazy Segment Tree

 モノイドとして, 転倒数の他に, 区間に含まれる0の個数と1の個数を持たせまふ. 区間のマージに際し, 転倒数は, 左右の区間のそれの和に加えて(左側の区間の1の個数×右側の区間の0の個数)だけ増えまふ. 

 変更クエリれふが, 0/1を切り替えるだけなので, 区間ごとにこれまでクエリが適用された回数の偶奇を覚えておけば良いれふ. 

 切り替えクエリを適用した場合のモノイドの変化れふが, 0の個数と1の個数が入れ替わるのは良いとして, 転倒数の変化を頑張って追う必要がありまふ. 結論としては, 元々の0/1の組が(0の個数)×(1の個数)で, そのうち左が1であるものがもともとの転倒数なので, 引き算でもともと右が1であるものを求め, 置き換えれば良いれふ.