■ - asdf1の日記

JOI予選の4問目にしては比較的優しい難易度だったのではないでしょうか.

今のところ問題は公開されていないので言及は控えます.

こういうのは大体,数列Aの最大値から降順に処理するとうまくいきます.

具体的にはmaxAからminAまでのある数をiとすると今から高さi以上の島を陸地にすると考えます.

この時にi+1の時の島の数がわかればiの時の島の数がわかります.

詳しく説明すると,iの時,陸地にするその両サイドがすでに陸地だったらどうなるでしょうか？

答えはi+1の時に出した陸地の数が一つ減りますね.

同じように片側だけすでに陸地なら？

答えは変わりません.

両サイドとも沈没しているのら？

答えはi+1の時の陸地の数から一つ増えますね.

あとはこれを実装すればよいです.

これでACできる！！！！わけではないんですよね…

コーナーケースがあります！！！！！

それは数列Aの要素が全部0の時です！！！（これ考えた人、性格が悪s）

この手の問題はCodeforcesでよく問われる気がしますので、Codeforcesをやろう！