[AtCoder] ABC 182 C – To 3

2020年11月10日

問題

方針

自然数 \( x \) が \( 3 \) の倍数であるとき、各桁の和である数字和も \( 3 \) の倍数となります。\( i \) 桁目の数字を \( x_i \) とすると、消す可能性のある数字は、\( x_i \bmod 3 \neq 0 \) となる数字です。ここで、\( x_i \bmod 3 \) の頻度を \( a_{x_i \bmod 3} \) とします。 \( a_0 \) は \( 3 \) の倍数の数字となります。

同じ剰余である数字を \( 3 \) つ選ぶと、その数字和は \( 3 \) の倍数となります。また、\( x_i \bmod 3 = 1 \) と \( x_j \bmod 3 = 2 \) となる数字の組も数字和は \( 3 \) の倍数となります。

よって、\( 3 \) の倍数が作れないときは、\( k = 1 \) のとき、\( a_1 = 1 \vee a_2 = 1 \) と \( k = 2 \) のとき、\( a_1 = 2 \vee a_2 = 2 \) です。また、消される桁数は最大でも \( 2 \) であることが分かります。

以降では、数字和が \( 3 \) の倍数ではなく、\( 3 \) の倍数を作れるとします。消す可能性のある数字の候補は \( a_1 + a_2 \) 個あるので、この値を減らすことを考えます。減らし方は次の \( 3 \) 通りです。

  1. \( a_1 \leftarrow a_1 – 1 \) 、\( a_2 \leftarrow a_2 – 1\)
  2. \( a_1 \leftarrow a_1 – 3 \)
  3. \( a_2 \leftarrow a_2 – 3 \)

減らした後は、\( \ 0 \leq a_1 + a_2 \leq 2 \) となります。\( a_1 = 0 \) のとき、\( a_2 \bmod 3 \) が答えであり、\( a_2 = 0 \) のとき、\( a_1 \bmod 3 \) が答えとなります。そうではないとき、\( a_1 + a_2 = 1\) とできるので、\( 1 \) が答えとなります。

コード