Edit

【pythonでABC181を解説】D - Hachi

問題概要

問題ページ

D - Hachi
D - Hachi

問題ページへ移動する

問題文

19 の数字のみからなる数字列 \(S\) が与えられます。

蜂の高橋くんは、 \(8\) の倍数が好きです。

高橋くんは、数字列 \(S\) を並び替えて \(8\) の倍数を作ろうとしています。

\(8\) の倍数を作れるかどうか判定してください。

制約

  • \(1 \leq |S| \leq 2 \times 10^5\)
  • \(S\) の各文字は 19 のいずれか

問題の考察

ACコード

import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    s = str(input().rstrip('\n'))
    d = collections.defaultdict(int)
    for i in range(len(s)):
        d[s[i]] += 1
    for i in range(1, 1000):
        if i % 8 == 0:
            t_d = collections.defaultdict(int)
            st = str(i)
            if len(st) >= min(len(s), 3):
                for j in range(len(st)):
                    t_d[st[j]] += 1
                is_ok = True
                for j in range(len(st)):
                    if t_d[st[j]] > d[st[j]]:
                        is_ok = False
                        break
                if is_ok:
                    print("Yes")
                    exit()
    print("No")


if __name__ == '__main__':
    solve()

-Edit
-