panda_noir https://blog.hatena.ne.jp/panda_noir/ panda noir 競プロのブログ https://kyopro.pandanoir.net/ codeforces.com 問題概要 簡単に言えば ある配列が与えられる ある要素1つを選ぶ その要素より左は広義単調増加、右は広義単調増加ように配列の各要素の値を減らす 操作後の配列のうち総和が最大となるときの配列を出力せよ。 C1と同様の問題で、制約のみが異なる。 codeforces.com 解法 C1と同様に、ある要素を選んで実際に配列を構築するやりかたは計算量がO(n2)かかる。今回は制約がn <= 5e5なので通らない。 ある位置を選んだ後、実際に配列を構築するのはO(n)で可能。つまり、今回ネックとなっているのは「どの位置を選ぶべきか？」の判定部分である。 第一感としては累積和… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkyopro.pandanoir.net%2Fentry%2F2020%2F04%2F02%2F230641" title="Skyscrapers (hard ver) - panda noir 競プロのブログ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2020-04-02 23:06:41 rich https://kyopro.pandanoir.net/entry/2020/04/02/230641 1.0 100%