n-knuu's logs

憧れ駆動。だいたい競プロ

天下一プログラマーコンテスト2015予選A C. 天下一美術館

解法

まず、完成前と完成後で色が同じ場合、色の変換も交換も意味がない。
よって、完成前と完成後の色が異なる場所だけ考えればよいことが分かる。

次に、同じ色のマスを交換することは意味がない。
なぜなら、その場合、交換した後に必ずもう1コストずつかかる(=同じ場所に2コストずつかける)ことになり、その場合は最初にそのマスを変換しさえすればよい(=1コストのみでよい)からである。

よって、完成前と完成後の色が異なり、かつ隣り合う異なる色のマスのみをできるだけ多く交換して、交換できなかった場所は色を変換すればよい。
ここで、交換する場合が、本来は色の変換で2コストかかるものが1コストでよい(=1コスト減る)と考えれば、答えは
(完成前と完成後の色が異なるマスの数) - (完成前と完成後の色が異なるマスのうち、隣り合う異なる色のマス間の最大マッチング)
となる。ここで、色は二色しかないので、グラフは二部グラフとなるため、最大マッチング=最大フローとなるので、容易に求めることができる。

コード


感想

1年ちょっとぶりにACした。
マス目で詰まったときはフローが使えないかと考えてみるべき。