技術室奥プログラミングコンテスト#4 Day1 D - スキップ
問題概要
個のマス目があり、
個目のマス目には
が書かれている。この内、任意の個数のマス目を選んだ時、選んだマス目の集合
{
}について、
点分のポイントが得られる時、ポイントの最大値を達成する
の要素数の最小値を求める。
解法
のある連続した3要素について考えてみる(下では1,3,5としている)。
ここで、5を飛ばして1から3まで行ったとしても(赤の経路)、両者の差の絶対値は2のため、2ポイントしか得られないため、この時点で最大値を達成することは不可能となってしまう。このような場合は素直に5を飛ばさないで|5-1|+|3-5|=6ポイントを得た方が良い。
反対に、これが1,3,5のような並びであった場合、3を飛ばしても得られるポイントは最終的に同じ6ポイントである。
このことから、連続する要素の内、(左端がその要素の集合中の最小値∧右端が最大値)∨(左端がその要素の集合中の最大値∧右端が最小値)が成り立っていれば両端の2要素以外は全てスキップすることができる。
よって、各について、その直前までの
が増加であったか若しくは減少であったかを見てあげて、直前までは増加しているのに
では減少している、もしくはその逆であれば答えに1を足していけばよい。
ただ、多分これが想定コーナーケースだろうと勝手に思っているが、の全要素が同じ場合、どんな選び方をしてもポイントは0になるため、問題文曰く、遊ばないという選択を取って0を答えとしなければならない。
これを実装して、AC。。
