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]