TopCoder SRM 616 Div2 ooo 1199->1338(highest)

5th, 1097.27pts, +0/-1 challenge
Volatility 321->409

最近Challenge失敗続きなので本気で控えたほうが良さそうですね

250: WakingUpEasy

ある整数から、配列の要素を循環させながら順に引いていって、何番目で0以下になるかを答える

class WakingUpEasy:
    def countAlarms(self, volume, S):
        L = len(volume)
        for i in xrange(20000):
            S -= volume[i % L]
            if S <= 0:
                break
        return i + 1

600: ColorfulCoinsEasy

コインの価値の表す配列が与えられる(コインの価値はより小さいもので割り切れる)
ある金額を最小の枚数のコインで表した時に、どのコインがどの種類であるか判断できるような金額が存在するかどうかを答える。

1番安いコインの価値が1、次に安いコインの価値が2とすると1は最大でも1枚しか使われることはない。
このようにあるコインで次に大きいコインの価値を割ったものマイナス1が最大使える枚数である。
それぞれのコインの枚数をソートして、小さい方からi番目のコインの価値がi+1よりも小さい場合、コインはうまく判別できないということがわかる。

class ColorfulCoinsEasy:
    def isPossible(self, values):
        L = len(values)
        if L == 1:
            return "Possible"
        
        div = [(values[i + 1] / values[i]) - 1 for i in xrange(L - 1)]
        
        div.sort()
        
        for i in xrange(len(div)):
            if div[i] < i + 1:
                return "Impossible"
        return "Possible"

1000: TwoLLogo

盤面が与えられてL字を2つ配置できる場合の数を答える。
Lが交差しない場合が一番簡単で、2つのL字の左下の角になる点を求めて上と右の長さを掛けあわせた積を足していけば良い
L字同士が交差する場合は長さが制限されたりするので場合分けして考える。

class TwoLLogo:
    def countWays(self, grid):
        H = len(grid)
        W = len(grid[0])
        grid_y = [[-1] * W for i in xrange(H)]
        grid_x = [[-1] * W for i in xrange(H)]
        for x in xrange(W):
            count = -1
            for y in xrange(H):
                if grid[y][x] == '.':
                    count += 1
                else:
                    count = -1
                grid_y[y][x] = count
        for y in xrange(H):
            count = -1
            for x in reversed(xrange(W)):
                if grid[y][x] == '.':
                    count += 1
                else:
                    count = -1
                grid_x[y][x] = count
        result = 0
        for y in xrange(1, H):
            for x in xrange(W - 1):
                if grid[y][x] != '.':
                    continue
                for y2 in xrange(1, H):
                    for x2 in xrange(W - 1):
                        if x2 <= x and y2 <= y:
                            continue
                        if grid[y2][x2] != '.':
                            continue
                        if x > x2 and y < y2:
                            result += grid_x[y][x] * grid_y[y][x] * grid_x[y2][x2] * grid_y[y2][x2]
                        elif y == y2:
                            result += min((x2 - x - 1), grid_x[y][x]) * grid_y[y][x] * grid_x[y2][x2] * grid_y[y2][x2]
                        elif x == x2:
                            result += grid_x[y][x] * grid_y[y][x] * grid_x[y2][x2] * min((y2 - y - 1), grid_y[y2][x2])
                        elif x < x2 and y < y2:
                            result += min((x2 - x - 1), grid_x[y][x]) * grid_y[y][x] * grid_x[y2][x2] * min((y2 - y - 1), grid_y[y2][x2])
                            result += (grid_x[y][x] - min((x2 - x - 1), grid_x[y][x])) * grid_y[y][x] * grid_x[y2][x2] * min((y2 - y - 1), grid_y[y2][x2])
                            result += min((x2 - x - 1), grid_x[y][x]) * grid_y[y][x] * grid_x[y2][x2] * (grid_y[y2][x2] - min((y2 - y - 1), grid_y[y2][x2]))
        return result