buyoh.hateblo.jp

競プロ参加記録.開設したばかりなので暫くお待ちください.

No.459 C-VS for yukicoder

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

No.459 C-VS for yukicoder - yukicoder

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

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


実行速度

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

非想定解法で殴る yukicoder Advent Calendar Contest 2016 - koyumeishiのブログ

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

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

構築するフロー

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

  1. パックは全体で{n}個あり,{i}番目のパックは{cmd[i]}を左端とする位置に落とされる.
  2. パックは1つ以上9つ以下のブロックを持つ
  3. パックは幅3つ高さ3つの容量を持つ
  4. フィールドの{x}列には{field[x]}個のブロックが積み上がっている

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

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

f:id:m_buyoh:20170109134918p:plain

まずは頂点について.

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

次に辺について.

  • {S \rightarrow p_i}
    • 水源から湧き出るブロックを各パックに振り分ける有向辺です.
    • 頂点{p_i}に1つ以上9つ以下のブロックを振り分けたいので,辺の流量は1以上9以下になります.
  • {p_i \rightarrow q_j}
    • パックのブロックの配置方法に関する有向辺です.
    • {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 \rightarrow T}
    • フィールドに置かれたブロックの数を検証する有向辺です.
    • 頂点{q_x}の流量は,過不足無く{field[x]}なので, 頂点{q_x}を根本とする有向辺は,{T}を矢先とする辺のみです.

instance

標準入力から次が与えられたとします.

2 4 3
..#.
..##
0
1
0

グラフは次のようになります.流量が書かれていない辺がありますが,心眼で見てください.

f:id:m_buyoh:20170109134928p:plain

実装

最小流制約付き最大流問題は,普通の最大流問題に帰着できます.調べてみてください.


writerとして

問題のミスは無かったのですが,手製テストケースの余分な改行,余分な0を含んだミスがあり,リジャッジを2回行ってました.ごめんなさい.

フローっぽい,というのは気づいていたのですが,最大流問題を1つも解いたことが無い,greedy解法が見つかったといった事情でこんな感じになってます.『フローっぽいけどフロー解法が無い』といった事態を避けるため,制約を強化(10k)しています.

実は未だテストケースのミスが残ってます.