Strorkisのブログ

信憑性については悪しからず

Codeforces Round #698 (Div. 2) 1478C - Nezzar and Symmetric Array

問題

Problem - C - Codeforces

 aを、 2n個の相異なる整数からなり、任意の a_iに対して a_i = -a_jとなる要素 a_jが存在する配列とする。

配列 aから生成した配列 dが与えられる。

ここで、 \displaystyle{ d_i = \sum_{j=1}^{2n}|a_i - a_j| }である。

元の配列 aは存在するだろうか。

解法

Editorial of Codeforces Round #698 (Div.1, Div.2) - Codeforces

Editorialを軸に説明を進める。

前提

 \displaystyle{
\begin{aligned}
d_i = d_j & (a_i = -a_j) \\
d_i \neq d_j &  (a_i \neq -a_j)
\end{aligned}
}

つまり、 dに相異なる n個の整数が2つずつ含まれていない場合、答えはNO。

この事実から、一般性を失わず、

 0 \lt a_1 \lt a_2 \lt \cdots \lt a_n かつ、任意の iに対して  a_{i + n} = -a_i

 0 \lt d_1 \lt d_2 \lt \cdots \lt d_n かつ、任意の iに対して  d_{i + n} = d_i

と仮定する。

式変形

前提より、 1 \leq i \leq nにおいて、

 \displaystyle{
\begin{aligned}
d_i &= \sum_{j=1}^{i}(a_i - a_j) + \sum_{j=i+1}^{n}(a_j - a_i) + \sum_{j=1}^{n}(a_i + a_j) \\
&= 2ia_i - \sum_{j=1}^{i}a_j + \sum_{j=i+1}^{n}a_j + \sum_{j=1}^{n}a_j \\
\end{aligned}
}

差分をとると、

 \displaystyle{
\begin{aligned}
d_{i+1} - d_i &= 2(i+1)a_{i+1} - 2ia_i - 2a_{i+1} \\
&= 2i(a_{i+1}-a_i)
\end{aligned}
}

つまり、 d_{i+1} - d_i 2iで割り切れない場合、答えはNO。

確認

 a_1 \gt 0ならば、 d_{i+1} - d_i \gt 0より、 1 \le i \le nにおいて a_i \gt 0

また、 1 \le i \lt j \le nにおいて a_{i+1}-a_iから a_j - a_iが求まるので、

 \displaystyle{
\begin{aligned}
d_1 - 2\sum_{i=1}^{n}(a_i - a_1) &= 2\sum_{i=1}^{n}a_i - 2\sum_{i=1}^{n}a_i +2\sum_{i=1}^{n}a_1 \\
&= 2na_1
\end{aligned}
}

つまり、 a_1が0以下であるか 2nの倍数ではない場合、答えはNO。

コード(Rust)

Submission #109130082 - Codeforces

感想

Editorialを読んでも理解できなかったため、記事を書いてみた。

少しは苦手意識を克服できた気がする。