とても寒い

模試の結果が冷えている

SRM 453 div1 easy

勝敗を全列挙する

#coding: utf-8
def solve(i,j,s,P,N,M):
    ret = 0
    if i == j:
        if i == N-1:
            k = sorted(s)
            k.reverse()
            ss = tuple(k)
            if ss[0] == M:
                if ss not in P:
                    P.add(ss)
                    ret = 1
        else:
            ret = solve(0,j+1,s,P,N,M)
    else:
        # i vs j
        s[j] += 2
        ret += solve(i+1,j,s,P,N,M)
        s[j] -= 2

        s[i] += 1
        s[j] += 1
        ret += solve(i+1,j,s,P,N,M)
        s[i] -= 1
        s[j] -= 1

        s[i] += 2
        ret += solve(i+1,j,s,P,N,M)
        s[i] -= 2
    return ret

class TheBasketballDivOne:
    def find(self, n, m):
        P = set([])
        if m > 2*n: return 0
        scores = [0 for i in range(n)]
        return solve(0,0,scores,P,n,m)

SRM 452 div1 easy

Greedy
証明は

ABAB
CDCD
ABAB
CDCD

みたいな塗り分けをするとできる

#coding: utf-8
class NotTwo:
    def maxStones(self, width, height):
        a = [[0 for i in range(width+2)] for j in range(height+2)]
        ans = 0
        for c in range(2,width+2):
            for r in range(2,height+2):
                if a[r-2][c] == 0 and a[r][c-2] == 0:
                    a[r][c] = 1
                    ans += 1
        return ans

SRM 449d1 easy

あり得るすべての辺の長さの組合せを列挙して最大の面積の三角形を求める．

#coding: utf-8
import math
EPS = 0.0001
def pitagoras(x):
    a = 0
    ret = []
    while a ** 2 <= x / 2 + 1:
        r = x - a ** 2
        b = math.sqrt(r)
        b += EPS
        c = int(b)
        if c ** 2 == r:
            ret.append((a,c))
        a += 1
    return ret
class MaxTriangle:
    def calculateArea(self, A, B):
        a = pitagoras(A)
        b = pitagoras(B)
        if len(a) == 0 or len(b) == 0:
            return -1.0
        ans = 0.0
        for i,j in a:
            for k,l in b:
                ans = max(ans,max(abs(i*k+j*l),abs(i*l+j*k)))
        return ans / 2.0

SRM 448 div1 easy

期待値計算

#coding: utf-8
#        1 2 3 4 5 6 7 8 9 T
cs = [0, 4,4,4,4,4,4,4,4,4,16]
scr= [0,11,2,3,4,5,6,7,8,9,10]

def solve(v,s):
    if s >= 21:
        return 0.0
    else:
        a = sum(v)
        e = 0.0
        for i in range(1,11):
            if v[i] > 0:
                n = v[i]
                v[i] -= 1
                e += (solve(v, s+scr[i]) + 1) * n / a
                v[i] += 1
        return e
class TheBlackJackDivOne:
    def expected(self, cards):
        crd = []
        for d in cards:
            c = d[0]
            if c == 'A':
                crd.append(1)
                cs[1] -= 1
            elif '0' <= c <= '9':
                crd.append(int(c))
                cs[int(c)] -= 1
            else:
                crd.append(10)
                cs[10] -= 1
        s = sum(crd)
        return solve(cs,s)

SRM 447 div1 easy

実装

# coding: utf-8

d = ((-2,-1),(-2,1),(-1,-2),(-1,2),(1,-2),(1,2),(2,-1),(2,1))
blocked = [[False for i in range(8)] for j in range(8)]
def calc(y,x):
    if 0 <= y < 8 and 0 <= x < 8 and (not blocked[y][x]):
        ret = 0
        for dy,dx in d:
            ny,nx = dy+y,dx+x
            if 0 <= ny < 8 and 0 <= nx < 8 and (not blocked[ny][nx]):
                ret += 1
        return ret
    return 100

class KnightsTour:
    def visitedPositions(self, board):
        for r,i in zip(board,range(8)):
            for c,j in zip(r,range(8)):
                if c == 'K':
                    y,x = i,j
                elif c == '*':
                    blocked[i][j] = True
        ans = 0
        while True:
            blocked[y][x] = True
            t = None
            s = 9
            for dy,dx in d:
                p = calc(y + dy, x + dx)
                if p < s:
                    s = p
                    t = (y+dy,x+dx)
            if t is not None:
                y,x = t
                ans += 1
            else:
                ans += 1
                break
        return ans

SRM 446 div1 easy

他の面に出たときは，今までいた面の反対側から出てくると考えると，1面だけ考えればよい．

#coding: utf-8
cube = (('RED','BLUE','RED'),
        ('BLUE','GREEN','BLUE'),
        ('RED','BLUE','RED'))
direction = ((0,1),(1,0),(0,-1),(-1,0))
class CubeWalking:
    def finalPosition(self, movement):
        d = 0
        px,py = 1,1
        for m in movement:
            if m == 'L':
                d -= 1
                if d < 0: d += 4
            elif m == 'R':
                d += 1
                if d >= 4: d -= 4
            elif m == 'W':
                dx = direction[d][0]
                dy = direction[d][1]
                px += dx
                px %= 3
                py += dy
                py %= 3
        return cube[px][py]