第2回ドワンゴからの挑戦状「花火」に対するシンプルな解法と最小費用流の双対
競技プログラミングアドベントカレンダー2017(その1)の二日目の記事です。
adventar.org
この記事では花火に対するシンプルな解法を説明します。これは最小費用流の双対問題を用いて説明できますので、そういったことに触れつつ解説します。本文は次のPDFに書きました。 http://tokoharu.github.io/tokoharupage/docs/advent2017.pdf
面白いポイントとしては、このテクを用いれば UTPC2012の"じょうしょうツリー"もかなりシンプルに書ける点だと思います。じょうしょうツリーについてはその解説では meldable heap を用いるというのが想定解法でしたが、今回紹介する方針でやればかなりシンプルにかけるかと思います。
そのほか
- tikz を使ったけどハマったときに結構苦労するなぁ
- Project Selection Problemの件はちょっと待ってください。
