ABC182 C - To 3 から学んだ

4560 ワード
AtCoder Python AtCoderBeginnerContest Python テキストリンク




bit 全探索かな？。
っで、どうやるんだっけ？
こちらが神です。

ザックリ見積もりで計算量が O(10^6 ~ 10^7) 。
python で行けない可能性を危惧し、pypy で提出。無事通った。

To3.py
N = list(input())

from itertools import product
def solv():
    ans = float("inf")
    for nums in product([0,1],repeat=len(N)):# O(2*10^5)
       nums = list(nums)
       score = ""
       if sum(nums) == 0:
          continue
       for i in range(len(N)):# O(19)
          if nums[i] == 1:
              score += N[i]
       score = "".join(score)
       if (int(score))%3 == 0:
          ans = min(len(N)-len(score),ans)
    print(ans if ans != float("inf") else -1)

solv()