エイシングプログラミングコンテスト2020 E
このタイプの貪欲を見出すのが苦手というか安定しないので、書き留めておきます。
この問題を少々読み解くと、次のようになります
N個のものを一列に並べる、i番目のものはx_i番目以降に配置するとスコアa_i(>0)を得られる。この時得られるスコアを最大化せよ
この時注目する点は以下の2つです
・条件を満たした時+a_i,満たさない時±0である(罰金はない)
→ある位置に入れるものを考えていて条件を満たすものがない場合は、採用しないとして良い
これより、貪欲をするとして満たすものがないときに何を採用するのかということを難儀する必要はないとわかります。
・手前から順番に見ていくことにすると、だんだん条件を満たすものが増える(減らない)
→これにより手前から順に見ていけば、ある場所で使えなかったものでも消えることがないので、一番高いものを取るとして損をすることがありません(たぶん)
このことから手前から採用することの正当性が直感的にわかります。逆にこういった問題において、上の2点を満たすような見方をすると正当な貪欲になる可能性が高いことが言えます、覚えておくと貪欲で見通しが立ちやすいかもしれません。
