[Codeforces] Codeforces Round #668 (Div. 2) A. Permutation Forgery

2020年9月8日

問題

方針

順列 \( p \) と異なる順列 \( p^{\prime} \) が \( F(p) = F(p^{\prime}) \) となるような \( p^{\prime} \) を見つけます。

\( F(p) \) は、

\[ {p_1 + p_2, p_2 + p_3, \cdots, p_{n-1} + p_{n}}\]

の \( n – 1 \) 個の要素を昇順に並び替えたものなので、\( p^{\prime}_i = p_{n- i +1}\) とすると、\( F(p^{\prime}) \) は、

\[ {p_n + p_{n-1}, p_{n-2} + p_{n-3}, \cdots, p_{2} + p_{1}}\]

を昇順に並び替えたものになるので、 \( F(p) = F(p^{\prime}) \) となります。

コード