修行の旅に出るか競技プログラミングやめたほうがよいっぽい
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