SRM608 div2

250-概要
数直線上を[-A, B]の範囲で動けるロボットがいます。
右(R)か左(L)へ進むよう指示を出します。
初めロボットは0の点に配置されています。
指示が終わったとき、ロボットはどの点にいるでしょう。

解法・感想
minとmaxで範囲を超えないよう押さえ込みます。

ソースコード

from math import *
class OneDimensionalRobotEasy:
    def finalPosition(self, commands, A, B):
        cur = 0
        for c in commands:
            if c == "R":
                cur = min(B, cur + 1)
            elif c == "L":
                cur = max(-A, cur - 1)
        return cur 

600-概要
飴の入った箱が与えられます。
全ての箱の中身を合わせると飴の数はC個になります。
それぞれの箱には、その箱に入っている飴の数の上限が与えられています。
今X個の飴が必要です。
最低でいくつの箱を取り出せば良いでしょう。

解法・感想
(最低限得られる飴の数) = max(0, C - (開けていない箱の上限の和))
あとは上限の大きな箱から開けていき最低限得られる飴の数がXを超えるまで回せば求まります。
tupleで与えられているのを忘れ.sort()を使っていたため弾かれてました。
プラグインに頼り切った結果です。残当。

ソースコード

class MysticAndCandiesEasy:
    def minBoxes(self, C, X, high):
        N = len(high)
        high = list(high)
        high.sort()
        su = [sum(high[:i]) for i in xrange(1, N + 1)]
        for i in xrange(N):
            if C - su[N - i - 1] >= X:
                return i
        return N

1000-概要
隣接行列が与えられます。
ある人が長さLの経路が何通りあるか調べたいそうです。
多項式時間で解けるでしょうか。

解法・感想
ある点を通る閉路（単純閉路？）が二つ以上存在すると指数時間必要になります。
これを求めるには始点（終点）を合流地点とするような二つの閉路の存在を確かめれば十分です。

ソースコード

class BigOEasy:
    def isBounded(self, graph):
        graph = [map(lambda x: x == "Y", g) for g in graph]
        N = len(graph)
        def check(start):
            q = set([start])
            visited = [False] * N
            flag = 0
            while len(q) != 0:
                cur = q.pop()
                for i in xrange(N):
                    if not graph[cur][i] or visited[i]:
                        continue
                    if i == start:
                        flag += 1
                        if flag > 1:
                            return True
                    else:
                        visited[i] = True
                        q.add(i)
            return False
        for i in xrange(N):
            if check(i):
                return "Unbounded"
        return "Bounded"