D - コイン集め (Coin Collecting) Editorial
by 
noimi
コインを長方形領域内に集めるところまでは公式解説と同様。
\(1\) 行目に含まれるコイン、マス \(2\) 行目に含まれるコイン、マスのキューを計 4 つ持ちながら左から走査する。
2 行分のマスとコインを追加する度、キューに含まれるマスの数とコインの数がともに正の間、キューの先頭の要素高々 4 つに対して貪欲にマッチングさせ、コスト最小のペアを取り除く操作を繰り返す。
これを行うことで答えが求まる。
[証明]
【先頭から貪欲にとっていい理由】
マスまたはコインのどちらかは、走査中の最右端にしか存在しないので明らか。
【両方が正になる度にマッチングさせ切っていい理由】
そうしない場合走査中の右端より右側からの流入があるということになるが、これは組み替えても損することがない(公式解説の無駄な横の移動がないことと同じ)
posted:
last update: