TopCoder SRM 651 Div2: Easy, Med

16回目のSRMだったが、サーバー側の問題でunratedに。EasyMedは本番中解けた。

Easy 250: RobotOnMoonEasy

WxHのマップにロボットが1体いる。マップには壁があり、ロボットは壁のマスには移動できない。ロボットを動かす一連の指令が与えられるので、すべての移動を終えた後にロボットが無事WxHのマップの中にいるかどうかを答えよ。

解法

問題文通りにきちんと実装すればいい。ロボットがいるマスは"S"となっているので、壁の条件判定の時に気を付けないとミスをするかもしれない。

def isSafeCommand(self, board, S):
    H = len(board)
    W = len(board[0])
    for y in xrange(H):
        for x in xrange(W):
            if board[y][x] == "S":
                w,h = x,y
    
    for s in S:
        if s == "R": dw,dh =  1, 0
        if s == "L": dw,dh = -1, 0
        if s == "U": dw,dh =  0,-1
        if s == "D": dw,dh =  0, 1
        nw,nh = w+dw,h+dh
        if not (0 <= nw < W and 0 <= nh < H):
            return "Dead"
        if board[nh][nw] != "#":
            w,h = nw,nh
    return "Alive"

Med 500:FoxAndSouvenirTheNext

あなたはいくつかのお土産を持っている。お土産にはそれぞれ価値が設定されており、両親にこのおみやげを平等に分けたい。平等に分けるとは、

1. 2人のもらうお土産の数は等しい
2. 2人のもらうお土産の価値の合計は等しい

ということである。このような分け方が可能かどうかを答えよ。お土産の数は最大50個まで。

解法

DPで解いていく。

下の解法は dp[お土産の価値の合計] = ((必要なおみやげの数）のセット) として、順番にお土産を計算に入れていった。最後に(お土産の数)/2 が dp[(価値の全合計)/2] にあるかどうかで実現可能か不可能化を判定している。

def ableToSplit(self, value):
    n = len(value)
    s = sum(value)
    if not (n%2 == 0 and s%2 == 0): return "Impossible"
    dp = [set([]) for i in xrange(s+1)]
    for i in xrange(n):
        for j in xrange(s-value[i],-1,-1):
            for k in dp[j]:
                dp[j+value[i]].add(k+1)
            dp[value[i]].add(1)
    return "Possible" if n/2 in dp[s/2] else "Impossible"