AtCoder Grand Contest 007:B - Construct Sequences
問題
https://atcoder.jp/contests/agc007/tasks/agc007_b
考え方
えー、難しい...
の順列
の順番になるように
を構築する。その際に
は単調増加で
は単調減少になるようにする必要がある。
いろいろな条件をいっぺんに考えることが難しいときは、ひとつずつ考えていくのがよさそう。
まずは は忘れて、
だけで条件を満たす数列を構築するとしよう。
としておく。これは
とすると
が単調増加であることを満たす。数列の項がすべて
または
である数列の累積和をとると単調性が満たされるので累積和をとることを考えよう。そうすると
について単調増加になる。
さて累積和を取る過程の をする際に
に足す分の
を
から引くことにする、つまり
とすると
となって
は
によって定まることがわかる。したがって
とした
を仮定しても
は単調増加であることに変わりがない。具体的には最初に構築した
が保たれる。
について考えよう。
であることから
はすでに単調減少になっていることが分かる。ただし
は
になりうる。構築すべき数列は
であるので、
を
に一様に足すことで数列の大小関係を維持したまま、
とすることができる。
よって上記のような手順で数列 を構築すると解が求められることになる。
Submission #4383041 - AtCoder Grand Contest 007
どこに着目して考察するべきだったか
差分をキャンセルするという考えにいたると解けるかもしれない...
何がバグっていたか
得た知見(典型ポイント)
類題
- D - Non-decreasing 数列の累積和に一様に値を足す考えは似ています。