mini-notes

競技プログラミングの解法メモを残していきます。

第一回 アルゴリズム実技検定 N - 整地

問題:N - Land Clearing

解答:Submission #10067145 - 第一回 アルゴリズム実技検定 過去問

メモ: 車が通る場所を決めると、各石について取り除く必要があるかどうかが一意に決まる。石が[li, ri]にある場合、車が通る場所の左端点が(li - c, ri)となる場合にその石を取り除かなければならない。このとき石を取り除くためにはコストがpiかかるので、車が通る場所の左端点を設定して取り除く石のコストを合計すればよい。

石の合計コストが変化するのは各石についてli - c(減少)とri(増加)であるため、これらの座標とコスト増減を配列に格納し、座標の小さい方からコストを変化させてゆき、コストの最小値を求める。

コスト増減時に重要な点として、(li - c, ri)は開区間として処理する必要がある。すなわち、石が[li, ri]にある場合は車が通る場所の左端点をli - c, riにそれぞれ設定することが可能である

実装としては、下記に気を付けるとうまくいきそう。

  • li-c < 0となる石については座標0で取り除く必要がある。
  • li-c = rj となるケースでは、「rj-εでiの石が除去されjの石が除去されない」「rjでiの石もjの石も除去されない」「rj+εでiの石が除去されずjの石が除去される」ため、li-cの減少を反映しかつrjの増加を反映しないタイミングが必要。これは座標とコスト増減を格納する配列を「座標の小さい順→コストの小さい順(減少→増加)」とソートしてあげるとうまくいく。
  • 車が通る場所の左端点がw-cの場合は、riがちょうどw-cになる場合はコスト減少を反映する必要があるが、li-cがちょうどw-cになる場合やriがw-cを超える場合はコスト増減を反映する必要がない。ただし、li-cがちょうどw-cになる場合はコストの増加の反映なので、最小値に影響しないことが明らかなら反映してもよい。