ARC063 D 高橋君と見えざる手 / An Invisible Hand

問題概要

N個の街におけるりんごの価格が与えられる。左から順に街を訪問し、りんごを売買し最大の利益を上げる人がいる。コストcでりんごの売買価格をcだけ変化させることができるとき、最大の利益を1以上下げるのに必要なコストを求めよ。

取った方針

最大の利益を上げられる区間をすべて列挙する。これは左から見ていった際の最小値を記録しておき、i番目の街について(i番目の街の価格-最小値)を計算し、それが最大となるパターンをvector<pair<int,int>>で覚えておけばO(N)で求めることができる。
その区間の左端か右端をつぶせばよいので、区間が被っていることも考慮して、「より多くの区間に含まれる方」をコスト1かけてつぶすことを考える。それを全区間について行えばO(N)で解ける。

正しい方針

実は制約を読み落としていて、すべての街において価格はそれぞれ異なる、という制約がある。
この制約を考えると、区間が被ることはないので、単に最小となる区間の個数を数えるだけで求まる。O(N)。

得られた知見

・誤読に気を付ける
・特定の条件を満たす値を覚えながら配列を舐めるパターン

解くのに必要な要素

・全探索は不可能だけど実は左から順番に見ていくだけでオッケーという問題はたまに見る。

周辺調査によって得られた知見

・特になし