D - Hachi Editorial by tatyam


並び替えて \(8\) の倍数を作れるかという問題なので、 \(8\) の倍数の判定法について考えてみましょう。

\(1000 = 8 \times 125\) なので、 \(10^3,10^4,10^5\dots\ \) はすべて \(8\) の倍数になり、下 \(3\) 桁のみが \(8\) の倍数であるかを決定します。

\(8\) の倍数になるときの下 \(3\) 桁の候補 \(000, 008, 016, \dots, 976, 984, 992\) がそれぞれ作れるかどうかを調べることで、 \(O(|S|)\) でこの問題を解くことができます。

\(|S| \leq 2\) の場合に注意してください。

回答例 (C++)

#include <bits/stdc++.h>
using namespace std;
 
bool solve(string s){
    if(s.size() == 1) return s == "8";
    if(s.size() == 2){
        if(stoi(s) % 8 == 0) return 1;
        swap(s[0], s[1]);
        return stoi(s) % 8 == 0;
    }
    vector<int> cnt(10);
    for(char x : s) cnt[x - '0']++;
    for(int i = 112; i < 1000; i += 8){
        auto c = cnt;
        for(char x : to_string(i)) c[x - '0']--;
        if(all_of(c.begin(), c.end(), [](int x){ return x >= 0; })) return 1;
    }
    return 0;
}
int main(){
    string s;
    cin >> s;
    puts(solve(s) ? "Yes" : "No");
}

回答例 (Python)

from collections import Counter

n = input()

if len(n) <= 2:
    if int(n) % 8 == 0 or int(n[::-1]) % 8 == 0:
        print("Yes")
    else:
        print("No")
    exit()

cnt = Counter(n)

for i in range(112, 1000, 8):
    if not Counter(str(i)) - cnt:
        print("Yes")
        exit()

print("No")

posted:
last update: