[Codeforces] Round #533 C. Ayoub and Lost Array

Ayoub and Lost Array

https://codeforces.com/contest/1105/problem/C

考え方

題意

区間 \( [l, r]\) の数字の \( k \) 個の和が \( 3 \) の倍数となる組み合わせを求めます。ただし、\( (1, 2) \) と \( (2, 1) \) などは区別されます。

方針

与えられた区間の中で、\( n \mod 3 = q\) となるものの個数を \( k_q \) とします。そうすると、

\[ k_q = \lfloor \dfrac{r – q + 3}{3}\rfloor – \lfloor \dfrac{l – q  +2}{3}\rfloor \]

が成り立ちます。証明はしていないんですが、\( n \mod p = q \) となるものの個数は、

\[ k_q = \lfloor \dfrac{r – q + p}{p}\rfloor – \lfloor \dfrac{l – q  +p – 1}{p}\rfloor \]

が成立すると思います。

この値を用いて動的計画法を行います。

\( d[i][q]\) を数字を \( i \) 個選んだ和の剰余が \( q \) であるものの個数とします。ただし、\( d[1][q] = k_q \) とします。\( q = 0, 1, 2\) について考えると、次の式が成り立ちます。

\begin{eqnarray}
d[i + 1][0] &=& k_0d[i][0] + k_1d[i][2] + k_2d[i][1]\\
d[i + 1][1] &=& k_0d[i][1] + k_1d[i][0] + k_2d[i][2]\\
d[i + 1][2] &=& k_0d[i][2] + k_1d[i][1] + k_2d[i][0]
\end{eqnarray}

状態の遷移を考えると理解しやすいと思います。例えば、数字を\( i \) 個選んだ時の和が \( 3 \) の倍数となるのは、数字を \(i – 1\) 個選んだ時の和の状態がどういうときにどの数字を足せばよいのかを考えると、上記のようになります。

コード

感想

点数の割に難しいと思いました。

シェアする

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

フォローする