こんちゅう

エッセイ・小説・ブログ・楽譜置き場。 不定期更新。

AtCoder ABC 153

解けなかった問題を覚書程度に記す。

ABC153 F

atcoder.jp

水色問題は解けなあかんでしょ......つらい。

けっきょくソートを除いてO(N)で解かなければならない。一番左から貪欲に爆破すればいいのだけれど,その地点での残り体力をいかにして求めるか。例えば爆破したときにそのダメージをqueに入れておいて,毎地点においてqueのfrontと比較して,爆破範囲を過ぎていたら取り除けばいい。するとqueを参照する回数は合計でO(N)で済む。

試験も終わったし,また精進したい。レートが上がらんのよ。