[AtCoder] ABC 182 C – To 3

2020年11月9日2020年12月12日

問題

方針

自然数 \( 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 \) が答えとなります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    string N;
    cin >> N;
    int k = N.length();
    int a[3]{};
    int sum = 0;

    for (int i = 0; i < k; i++) {
        a[(N[i] - '0') % 3]++;
        sum += N[i] - '0';
    }

    if (a[0] == k || a[1] == a[2] || (sum % 3 == 0)) {
        cout << "0\n";
    } else if (((k == 1 && (a[1] == 1 || a[2] == 1))) || ((k == 2 && (a[1] == 2 || a[2] == 2)))) {
        cout << "-1\n";
    } else if (a[1] == 0 || a[2]  == 0) {
        cout << (a[1] + a[2]) % 3 << "\n";
    } else {
        cout << "1\n";
    }
    return 0;
}