No.459 C-VS for yukicoder - buyoh.hateblo.jp

Advent Calendar Contest 2016の10日目の問題のwriterをしました．

問題文・想定解法はリンク先の通りです．

本記事ではフローを用いた別解について書きます．結局年明けになってしまった．

実行速度

koyumeishiさんがフローを用いた別解でACしています．

計算量が重いので，ライブラリが下手糞だとhttp://yukicoder.me/submissions/143764こんな感じになります． (2017/05/07追記:ACしましたhttp://yukicoder.me/submissions/172412)

2random6.txtまでのテストケースは緩くしてありますので，素朴な実装でもこれらのテストケースにはACする見込みがあります．線形計画法でもACできるでしょう．

問題文と入力から与えられる制約を並べてみる．

有向辺の容量を『ブロックの数』と見立てたフローを作ります．

先に，どのようなグラフになるのか示します．こんな感じ．

f:id:m_buyoh:20170109134918p:plain

まずは頂点について．

- 水源です．
- 流し台です．
- ${i}$ 個目のパックを表現する頂点です．
- この頂点の流量は，パックが持つブロックの個数になります．すなわち，1以上9以下です．
- フィールド列を表現する頂点です．
- この頂点の流量は，その列に積まれているブロックの個数になります．すなわち，過不足無く ${field[x]}$ です．

次に辺について．

- 水源から湧き出るブロックを各パックに振り分ける有向辺です．
- 頂点 ${p_i}$ に1つ以上9つ以下のブロックを振り分けたいので，辺の流量は1以上9以下になります．
- パックのブロックの配置方法に関する有向辺です．
- ${i}$ 番目のパックの1列目のブロックは， ${cmd[i]}$ 列目のフィールドに落とされるので， ${p_i \rightarrow q_{cmd[i]}}$ の有向辺を加えます．
- 2,3列目も同様に， ${p_i \rightarrow q_{cmd[i]+1}}$ ， ${p_i \rightarrow q_{cmd[i]+2}}$ の有向辺を加えます．
- パックの1列には0以上3以下のブロックが含まれるので，流量は0以上3以下です．
- フィールドに置かれたブロックの数を検証する有向辺です．
- 頂点 ${q_x}$ の流量は，過不足無く ${field[x]}$ なので，頂点 ${q_x}$ を根本とする有向辺は， ${T}$ を矢先とする辺のみです．