けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 181 D - Hachi (茶色, 400 点)

AtCoder AtCoder400点 ABC-D 茶色diff 数学(整数問題) 全探索 倍数判定や九去法 for文 next_permutaion

整数 n を 8 で割ったあまりは、 n の下三桁を 8 で割ったあまりに等しい！

問題概要

整数 S が長さ N の文字列として与えられる ( S は '1'〜'9' のみで構成される)。

S の各文字を並び替えてできる整数の中に、8 の倍数となるものが存在するかどうかを判定せよ。

制約

  • 1 \le N \le 2 \times 10^{5}

考えたこと

実は次のことが成り立つ。

  • 2 の倍数かどうかの判定：下一桁が 2 の倍数かどうか
  • 4 の倍数かどうかの判定：下二桁が 4 の倍数かどうか
  • 8 の倍数かどうかの判定：下三桁が 8 の倍数かどうか

一般に 2^{k} の倍数であることは、下 k 桁が 2^{k} の倍数であることと同値となる。8 の倍数の場合について簡単に示しておこう。

1000 = 2^{3} \times 5^{3}

なので、1000 が 8 で割り切れることに注意する。よって、任意の整数 n に対して、 n を 1000 で割った商を q, あまりを r とすると

n = 1000q + r

となる。 r はまさに「 n の下三桁」である。このとき

n ≡ 1000q + r ≡ r \pmod 8

となることがわかる。よって、 n を 8 で割ったあまりは、 r を 8 で割ったあまりに等しい！！

元の問題へ

以上のことを踏まえて、元の問題に戻ろう。つまり S を上手に並び替えることで、下三桁を 8 の倍数にできるかどうかを判定する問題となる。

まず N \le 3 の場合は単純に全探索で OK。

N \ge 4 のときは、次のように考えられる。

8 の倍数の下三桁としてありうるものをすべて考える。それらのうち、 S から充足できるものがあるかどうかを判定する。

1000 未満の 8 の倍数は 124 個しかないので十分高速と言える。

コード

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

bool solve(string &S) {
    if (S.size() <= 5) {
        sort(S.begin(), S.end());
        do {
            int val = 0;
            for (auto c : S) val = val * 10 + (int)(c-'0');
            if (val % 8 == 0) return true;
        } while (next_permutation(S.begin(), S.end()));
        return false;
    }
    vector<int> all(10, 0);
    for (const auto c : S) all[c-'0']++;
    for (int i = 0; i < 1000; i += 8) {
        vector<int> num(10, 0);
        int i2 = i;
        for (int iter = 0; iter < 3; ++iter) {
            num[i2 % 10]++;
            i2 /= 10;
        }
        bool ok = true;
        for (int v = 0; v < 10; ++v) if (num[v] > all[v]) ok = false;
        if (ok) return true;
    }
    return false;
}

int main() {
    string S; cin >> S;
    if (solve(S)) cout << "Yes" << endl;
    else cout << "No" << endl;
}