564th, 146.69pts, +0/-1 challenge
Volatility 355->321
例のごとくChallenge失敗してDiv2落ち。
250: AmebaDiv1
ある正の整数の大きさのアメーバがいて自分と同じ大きさの石があったら食べて2倍の大きさになる。
いくつかの石がある順で与えられ、最初のアメーバの大きさとしてすべての正の整数がありうると仮定した時、アメーバの最終的な大きさとしてありえない値の個数を数える。
以下の図の例では石が[3, 2, 1]の順で与えられていて、最終的にアメーバは1と3の大きさにはならない。
解法
アメーバと等しい大きさの石が存在しない場合にはアメーバの大きさは変化しない。
なので、ありえない大きさの候補としては石と等しい大きさの場合のみ考えればよい。
石は最大で200個しか与えられないので、実際に定義通りシミュレーションしてみて可能だった石の大きさを候補の中から引けばよい。
# -*- coding: utf-8 -*- import math,string,itertools,fractions,heapq,collections,re,array,bisect class AmebaDiv1: def count(self, X): X = X count = 0 visited = set() candidate = set(X) reached = set() L = len(X) for i in xrange(L): if X[i] in visited: continue visited.add(X[i]) temp = X[i] for j in xrange(i, L): if X[j] == temp: temp *= 2 reached.add(temp) return len(candidate - reached)
