Codeforces #713(Div.3) E: Permutation by Sum [JP]

問題概要

• 1 から $n$ までの順列 $P$ を考える
• $1\le l\le r\le n$ の $l,r$, $1\le s\le \frac{n(n+1)}{2}$ の $s$ が与えられる
• $P_l+P_{l+1}+...+P_r=s$ となる 1 から $n$ までの順列が存在するならばそれを出力、存在しないならば -1 を出力する

解説

1 から $n$ までの順列の中で長さ $r-l+1$ で生成できる最小値、最大値を考える。
以下、$k=r-l+1$ として扱う。

最小値
初項 1、 項数 $m$ 、公差 1 の等差数列としてみると、
$min(m)=\frac{m(m+1)}{2}$
が導かれる。

最大値
初項 $x$ 、項数 $m$ 、公差 -1 の等差数列としてみると、

$max(x,m)=\frac{m\ast (2\ast x+(m-1)\ast -1)}{2}$
$max(x,m)=\frac{m(2x-m+1)}{2}$

が導かれる。

$min(k)\le s\le max(n,k)$ の間にある $s$ は条件を満たすことがわかる。
残るは実装のみで、$n$ から大きい順に 指定の配列に入れるか入れないかを決めていけば良い。

方針
初めに答えを入れる用の配列 $res$ を用意する。
次に $n$ から大きい順に考えていく。
$n$ からfor 文を回し、
$max(i,k)-s\ge 0$ かつ $s-i\ge min(k-1)$ を満たすならば
配列 $res$ の $l+k$ に $i$ を代入、$k=k-1,s=s-i$ で置き換える。
これを $k$ が 0 になるまで繰り返し、最終的に $s=0$ が達成できれば OK である。
あとは配列の空いている部分に使用していない文字を代入していけば良い。

提出したソースコード