唯物是真 @Scaled_Wurm

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

最近何回かTopCoder(Div1)に参加したけど1問も解けてない

topcoder 競技プログラミング

修行の旅に出るか競技プログラミングやめたほうがよいっぽい

Easyの問題は解説読めばわかりはするんだけどなぁ……

TopCoder SRM 655 Div1 x-- 1323->1312

writeの解説

250: BichromePainting

'W'と'B'のいずれかで構成された正方形の盤面と、正方形のブラシサイズ\(k\)が与えられる
すべて'W'の盤面から、好きな回数だけ正方形のブラシで盤面を'W'と'B'で塗って、与えられた盤面が作れるかを答える

端から適当に埋めて解けると思ったけど、提出してから反例に気づいたorz

最後の盤面から逆に戻して考えていくのが典型らしい(？)

# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect

class BichromePainting:
    def isThatPossible(self, board, k):
        n = len(board)
        board = [list(board[i]) for i in xrange(n)]
        while True:
            complete = True
            for i in xrange(n - k + 1):
                for j in xrange(n - k + 1):
                    white = False
                    black = False
                    for p in xrange(i, i + k):
                        for q in xrange(j, j + k):
                            white |= board[p][q] == 'W'
                            black |= board[p][q] == 'B'
                    if white != black:
                        complete = False
                        for p in xrange(i, i + k):
                            for q in xrange(j, j + k):
                                board[p][q] = '.'
            if complete:
                break
        
        for i in xrange(n):
            for j in xrange(n):
                if board[i][j] != '.':
                    return 'Impossible'
        return 'Possible'

TopCoder Open 2015 Round 1A x-- 1312->1237

250: Similars

最小値\(L\)と最大値\(R\)の間の数値で共通する数字の数の最大数を答える

数字の状態はたかだか1024通りしかないので、その状態にまで圧縮してから数字の重複の有無を計算すればよいらしい

# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect

class Similars:
    def maxsim(self, L, R):
        count = collections.Counter()
        for i in xrange(L, R + 1):
            used = 0
            for b in set(str(i)):
                used |= 1 << int(b)
            if used in count:
                count[used] = 2
            else:
                count[used] = 1
        
        bit = list(count.elements())
        L = len(bit)
        result = 0
        for i in xrange(L):
            for j in xrange(i + 1, L):
                result = max(result, bin(bit[i] & bit[j]).count('1'))
        return result

TopCoder SRM 656 Div1 --- 1237->1225

RandomPancakeStack

\(d\)個のパンケーキのおいしさが与えられる(\(1\le d \le 250\))
パンケーキは一つ目から順に大きさが\(1, 2, 3,\dots\)となっている
ランダムにパンケーキを選び続けた時のおいしさの合計の期待値を答える
ただし、一度使ったパンケーキと、前に選んだパンケーキよりも小さなパンケーキは選ぶことができない

すぐに典型的な期待値の動的計画法だと思ったけど本番中には通せず(コードが間違っていてケーキの大きさを逆順に考えていた
\(i\)番目のケーキが\(j\)番目に選ばれる期待値を\(dp[i][j]\)とすると\(dp[i][j] = \sum_{i < k} \frac{1}{d - j}dp[k][j - 1]\)が成り立つので、全部の期待値を計算した後においしさをかけて足せばよい

dpの向き逆になっていて、おいしさの部分を反転して無理矢理つじつまを合わせているコード

# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect

class RandomPancakeStack:
    def expectedDeliciousness(self, d):
        L = len(d)
        p = 1.0 / L
        dp = [[0] * L for i in xrange(L)]
        
        for i in xrange(L):
            dp[i][0] = p
        
        for l in xrange(1, L):
            prob = 1.0 / (L - l)
            for s in xrange(L - 1):
                if dp[s][l - 1] <= 0:
                    continue
                for t in xrange(s + 1, L):
                    dp[t][l] += dp[s][l - 1] * prob
        
        result = 0
        for l in xrange(L):
            for j in xrange(L):
                result += dp[j][l] * d[L - j - 1]
        return result
'); jQuery.noConflict(true);