問題

https://atcoder.jp/contests/agc007/tasks/agc007_b

考え方

えー、難しい...

$N$ の順列 $p_i$ の順番になるように $a_{p_i}+b_{p_i}$ を構築する。その際に $\{a_N\}$ は単調増加で $\{b_N\}$ は単調減少になるようにする必要がある。

いろいろな条件をいっぺんに考えることが難しいときは、ひとつずつ考えていくのがよさそう。

まずは $\{b_N\}$ は忘れて、 $\{a_N\}$ だけで条件を満たす数列を構築するとしよう。 $a_{p_1}=1, a_{p_2}=2, \cdots, a_{p_n}=n+1$ としておく。これは $b_{p_i}=0$ とすると $a_{p_i}+b_{p_i}$ が単調増加であることを満たす。数列の項がすべて $a_i \ge 0$ または $a_i \le 0$ である数列の累積和をとると単調性が満たされるので累積和をとることを考えよう。そうすると $\{a_N\}$ について単調増加になる。

さて累積和を取る過程の $a_{i+1} = a_i + a_{i+1}$ をする際に $a_{i+1}$ に足す分の $a_i$ を $b_{i+1}$ から引くことにする、つまり $b_{i+1} = -a_i$ とすると $a_{i+1} + b_{i+1} = a_i + a_{i+1} -a_i = a_{i+1}$ となって $a_{i+1} + b_{i+1}$ は $a_{i+1}$ によって定まることがわかる。したがって $b_{i+1} = -a_i$ とした $\{b_N\}$ を仮定しても $a_{p_i}+b_{p_i}$ は単調増加であることに変わりがない。具体的には最初に構築した $a_{p_1}=1, a_{p_2}=2, \cdots, a_{p_n}=n+1$ が保たれる。

$\{b_N\}$ について考えよう。 $b_{i+1} = -a_i$ であることから $\{b_N\}$ はすでに単調減少になっていることが分かる。ただし $\{b_N\}$ は $b_i \lt 0$ になりうる。構築すべき数列は $1 \le a_i, b_i \le 10^9$ であるので、 $|min(b_i)|+1$ を $\{b_N\}$ に一様に足すことで数列の大小関係を維持したまま、 $b_i \gt 0$ とすることができる。