見出し画像

AtCoder Beginner Contest 181を見直すD - Hachi

なにがし

問題

1から9で構成される数字列Sが与えられるので、並び替えて8の倍数にすることができる場合は「Yes」を出来ない場合は「No」を出力する問題

公式解説のコード

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")

（参照元：https://atcoder.jp/contests/abc181/editorial/259）

ある数字が8の倍数であるかどうかを調べるには。
8*125=1000なので、1000以上の整数については下3桁が8の倍数であるかどうかを調べれば良いです。1桁、2桁の場合は、数が少ないので剰余をとって調べてしまえば良いです。

公式の解説ではある文字列に、別の文字列が含まれているかを調べるために、標準モジュールのCollectionsからCounterをインポートしています。Counterは以下の様に使います。

>>> Counter("111223444")
Counter({'1': 3, '4': 3, '2': 2, '3': 1})

Counterは与えられた文字列に含まれる、要素とその数を辞書型のCounterオブジェクトで返してくれます。

以下の部分では集合の差を求めています。

   if not Counter(str(i)) - cnt:

A：8の倍数に含まれる数字 - B：数字列Sに含まれる数字

Aにしか含まれていない数字があるか、A,Bどちらにも含まれるがAの方が数が多い数字がある場合は、その値が含まれたCounterオブジェクトが返ってきます。
そうでない場合は、空のCounterオブジェクトのが返ってきます。

参照ページ


この記事が気に入ったらサポートをしてみませんか？