読者です 読者をやめる 読者になる 読者になる

唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

TopCoder SRM 615 Div1 o-- 1211->1199

564th, 146.69pts, +0/-1 challenge
Volatility 355->321

例のごとくChallenge失敗してDiv2落ち。

250: AmebaDiv1

ある正の整数の大きさのアメーバがいて自分と同じ大きさの石があったら食べて2倍の大きさになる。
いくつかの石がある順で与えられ、最初のアメーバの大きさとしてすべての正の整数がありうると仮定した時、アメーバの最終的な大きさとしてありえない値の個数を数える。

以下の図の例では石が[3, 2, 1]の順で与えられていて、最終的にアメーバは1と3の大きさにはならない。
f:id:sucrose:20140405002405p:plain

解法

アメーバと等しい大きさの石が存在しない場合にはアメーバの大きさは変化しない。
なので、ありえない大きさの候補としては石と等しい大きさの場合のみ考えればよい。
石は最大で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)

問題のwriterの方の解説

-->