Rustコトハジメ

Rustで競技プログラミングをやる人の覚書のようなものです。

蟻本

「Bride and Prisoner」番兵と開区間を使って実装をシンプルにする

考えることは単純だけど、実装の考え方が汚いとバグるなぁという問題。 問題 P個の牢屋があり、そこに1人ずつ囚人が入っている。 今、Q人の囚人Aiを解放したいが、解放するごとにそこから左右に連続した囚人の数をコストとして払う必要がある。 最小のコスト…

「Asteroids」二部マッチングへの帰着

わりとよくある考え方。2nから2nのDPへの変形を行いたいが、そうは行かない場合、nが小さいなら二部グラフを疑いたい。 問題 nxnのグリッドに0,1が書かれている。1の個数はk個である。 あなたは、1行または1列のすべての1を0に書き換える操作を何回が行い、…

「Intervals」セグメント系問題の最小費用流への帰着

意外に汎用性の高い考え方かも知れない。少なくともK=1とすれば単なる最短路の問題になる。 問題 n個のセグメントがあり、各々にwiの重みがある。 どの点もたかだかk個のセグメントに被覆されるようにセグメントを選ぶ時、重みの最大値はいくつか? 制約: n,…