AGC007 B - Construct Sequences

f:id:tkr987:20210420022450p:plain

https://atcoder.jp/contests/agc007/submissions/21896735

  •  \sum k の公式が成り立つ理由

f:id:tkr987:20210420025852p:plain
結論から言うと  a_i = i * 3 * 10^4 + j \ (p_{j} = i) が答えになる。

 N に比べて  a_i の制約が非常に緩いことから、ある程度の余裕を持たせて昇順数列 a を考えたほうが良いのかな、という気持ちになる。 \sum k 公式のように例えば M=30000 の等差で昇順・降順の a と b を作って加算してみると全ての合計が同じになる。ここで a に  p_j j だけ順番に加算していくと元々全ての合計が同じだったため  a_i + b_i の合計が p の順番になってくれる。このとき M が N に比べて十分に大きければ a の昇順が崩れることもない。

 

感想: 気づけそうで自力で気づくのは難しい…