[CSA] Round #2 Circular Subarrays

Circular Subarrays

https://csacademy.com/contest/beta-round-2/task/circular_subarrays/statement/

このような問題のカテゴリー分けをどうするか悩ましいのですが、数列が与えられるので、数列ということにしておきます。

解説を読んでもなかなか理解できませんでしたが、良問だと思います。

考え方

円形の配列 \( a \) が与えられたとき、サイズ \( K \) の連続する部分配列は \( N \) 個あり、その部分配列の和が全て等しくなるように配列の要素を増減させます。どういうことかというと、 \( i \) 番目の部分配列の和を \( S_i \) とすると、

\[
\begin{eqnarray}
S_1 &=& a_1 + a_2 + \cdots + a_K \\
S_2 &=& a_2 + a_3 + \cdots + a_{K + 1}\\
& \vdots &\\
S_{n-1} &=& a_{n – 1} + a_{n} + \cdots + a_{K-2}\\
S_n &=& a_n + a_1 + \cdots + a_{K – 1}
\end{eqnarray}
\]

これらの和が全て等しくなるように操作を行います。全ての和が等しいような数列 \( a \) が満たすべき条件を考えると、\( S_1 = S_2 \) より、\( a_1 = a_{K + 1}\) であることが分かります。同様にしてすべての部分配列に対して条件を考えると、値が等しくなるような要素のグループが出来上がります。

公式の解説では、このようなグループの数は、

\[ \dfrac{N}{gcd(N, K)} \]

となるようです。したがって、グループの数を \( m \) とし、その \( i \) 番目の集合を \( G_i \) とすると、

\[
\begin{eqnarray}
G_1 &=& \{a_1, a_{1 + K}, a_{1 + 2K}, \cdots \}\\
G_2 &=& \{a_2, a_{2 + K}, a_{2 + 2K}, \cdots \}\\
& \vdots &\\
G_m &=& \{a_m, a_{m + K}, a_{m + 2K}, \cdots \}\\
\end{eqnarray}
\]

のようになります。ここで注意すべき点は、あるグループに属する配列の要素番号は他のグループには属しません。

各グループの要素の値を等しくするために必要な操作の最小回数は、そのグループの中央値と要素の絶対値の和となります。この考えは割とよく見かけると思います。

したがって、全てのグループに対して必要な操作回数の和が答えとなります。

ソースコード

感想

中央値を使って操作の最小回数を求める方法は知っていましたが、グループ分けをして考えることは思いつきませんでした。個人的には良い問題だと思います。

グループの総数はグループ分けを行っていけば分かりますが、総数を答える問題があるととすれば、知っておいて良い知識だと思います。また、\( N \) と \( K \) が互いに素であるとき、グループは1つなので、全ての要素が等しくなる必要があります。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする