ARC119 E - Pancakes (800)
コンテスト中の考察
一部を反転させたときに差が変わるのは最大2カ所
2カ所の選び方は
$ \mathcal{O}(N^2)
これを全部試すのは間に合わない
ループ毎にまとめて計算しようとしてもほとんど変わらない
解説の方法
減る量の最大値は最長共通区間の2倍
反転後に最長共通区間より左側と最長共通区間より右側だけになる
$ A_i \lt A_{i+1}
の場合と
$ A_i \ge A_{i+1}
の場合の区間に分けてそれぞれ最長共通区間を求める
問題:
https://atcoder.jp/contests/arc119/tasks/arc119_e
提出:
https://atcoder.jp/contests/arc119/submissions/22754999
#ARC119
#800pt
#E
#ARC
#AtCoder