TopCoder SRM 631 Div2 oo- 1019->1135

31th, 671.63pts, +0/-0 challenge
Volatility: 422->???

Hardが950点だったので解けるかなーと思ったけど、問題文の意味が理解できずにタイムロスをしまくってギリギリ時間内には解けなかったorz

250: TaroGrid

column上の連続するセル数の最大値を答えるだけ

class TaroGrid:
    def getNumber(self, grid):
        H = len(grid)
        W = len(grid[0])
        M = 0
        for i in xrange(W):
            before = grid[0][i] 
            count = 1
            M = max(M, count)
            for j in xrange(1, H):
                if grid[j][i] == before:
                    count += 1
                    M = max(M, count)
                else:
                    before = grid[j][i]
                    count = 1
        return M

500: CatsOnTheLineDiv2

直線上のセルが並んでいる。
各セルについて猫のいる数と位置が与えられる。
猫は単位時間毎にセルを最大一つ移動できる。
ある時間\(time\)以内に同じセルに2匹以上猫がいないように移動できるか？

端から外側に向けて貪欲に猫を移動させていけば良い

class CatsOnTheLineDiv2:
    def getAnswer(self, position, count, time):
        arr = zip(position, count)
        arr.sort()
        
        visited = set()
        fail = False
        for pos, cnt in arr:
            for i in xrange(-time, time + 1):
                if cnt <= 0:
                    break
                
                if (pos + i) not in visited:
                    visited.add(pos + i)
                    cnt -= 1
            if cnt > 0:
                fail = True
                break
        if fail:
            return "Impossible"
        else:
            return "Possible"

950: TaroCoins

Taroはすべての非負の整数\(K\)について\(2^K\)の価値があるコインを\(2\)枚ずつ持っている
それらのコインを使って\(N\)を表す方法は何通りあるか

下の桁から繰り上がりの有無について持ちながら動的計画法

class TaroCoins:
    def getNumber(self, N):
        d = '{:b}'.format(N)[::-1]
        
        L = len(d)
        
        dp = [[0] * 2 for i in xrange(L + 1)]
        dp[0][0] = 1
        for i in xrange(L):
            if d[i] == '0':
                dp[i + 1][0] = dp[i][0]
                dp[i + 1][1] = dp[i][0] + dp[i][1]
            else:
                dp[i + 1][0] = dp[i][0] + dp[i][1]
                dp[i + 1][1] = dp[i][1]
        return dp[-1][0]