【ABC181 D】「Hachi」を解く【Python3】

コンテスト一覧へ

 

8の倍数が好きな蜂の高橋くんのために、与えられた数字列Sを並び替えて8の倍数が作れるかどうかを判定する問題です。

提出
from collections import Counter

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

cnt = Counter(s)

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

print("No")

今回は公式の解答例がわかりやすかったので、そちらを参考にしています。

D – Hachi 解説
https://atcoder.jp/contests/abc181/editorial/259

1000が8の倍数であるため、(8の倍数同士を足しても8の倍数になることから)下3桁が8の倍数であるかどうかを調べればよいことがわかります。

2桁以下の場合は、シンプルに8で割り切れるか調べます。

3桁以上の場合、「1~9」の数字の個数を数え、下3桁の候補が作れるかどうかを調べていきます。

collectionsモジュールのCounter()を使用することで、リスト内の要素の個数がわかります。

from collections import Counter
list = [1, 1, 1, 1, 2, 3, 3]
c = Counter(list)
print(c)
# > Counter({1: 4, 3: 2, 2: 1})

数字列の要素の数を数えて「cnt」に入れておきます。

「112~1000」までの候補(8の倍数)を調べ、「(候補内の要素の数) – (数字列Sの要素の数)」を判定します。

この結果の要素が空だった場合に「Yes」を出力してプログラムを終了させます。

from collections import Counter
list1 = [1, 2, 8]
list2 = [1, 1, 1, 2, 3, 4, 6, 8]
c = Counter(list1)-Counter(list2)
print(c)
# > Counter()

プログラムが終了せず、最後までループした場合、「No」を出力します。

スポンサーリンク

【ABC181】解説記事リスト

コンテスト一覧に戻る

コメントを残す

メールアドレスが公開されることはありません。