TopCoder SRM 642 Div2

SRM過去問解きその１。EasyとMediumはかなり簡単め。Hardは普通にHardな難易度だった。本番では解答早さが重要そうな問題セットに思える。

問題とサマリーはこちら。

Easy 250: ForgetfulAddition

各桁が1から9でできた数字が与えられるので、2分割して足したときの最小値を答える問題。やるだけ。

def minNumber(self, expression):
    ans = 10**10
    for i in range(1,len(expression)):   
        ans = min(ans,int(expression[:i])+int(expression[i:]))
    return ans

Medium 500: LightSwitchinPuzzle

連続するN室のライトのオンオフの状態が与えられる。 i 番目の部屋のスイッチを押すと i の倍数の部屋すべてのスイッチが切り替わるという謎仕様になっている。すべての部屋のライトをオフにするのに最低何回スイッチを押さないといけないかを答える問題。

貪欲法でOK。１番目から見ていき、部屋のライトがついていたらスイッチを押せばいい。こうすれば（というかこうしないと）すべての部屋をライトをオフにすることができる。

def minFlips(self, state):
    state = list(state)
    ans = 0
    for i in range(len(state)):
        if state[i] == "Y":
            ans += 1
            for j in range(i,len(state),i+1):
            state[j] = ("Y" if state[j] == "N" else "N")
   return ans 

Hard 1000: TallShoes

ある王国にはN個の都市があり、それぞれの都市間が移動可能なようにN-1本以上からN*(N-1)/2本以下の道路が敷かれている。それぞれの道路には高さ制限がある。この国の王様は都市0から都市N-1まで移動したいのだが、そのときできるだけ厚い厚底ブーツをはいて目立ちたいと考えている。王様の高さが制限より大きいとその道路は通れないが、ある道路に対してお金を k**2 払うことで高さ制限を k 上げることができる。王様の予算を B としたとき、王様は最大どれだけの高さで都市0から都市N-1まで移動することができるかを答える問題。

以下の様な全探索コードを書いたがTLEしてしまった。グラフ問題はまだまだ苦手だ。ちゃんとした解答はまた後日。

def maxHeight(self, N, X, Y, height, B):
    inf = 10**10
    
    def getmaxh(path):
        res = 0
        cnt = 0
        h = 10**16/2
        dh = 10**16/4
        while cnt < 3:
            cost = sum(max(0,h-hi)**2 for hi in path)
            if cost > B:
                h -= dh
            else:
                res = max(res,h)
                h += dh
            dh = (dh+1)/2
            if dh == 1: cnt += 1
        return res
    
    H = [[0]*N for _ in range(N)]
    G = [[inf]*N for _ in range(N)]
    for i in range(N): G[i][i] = 0
    for i in range(len(X)):
        x,y,h = X[i],Y[i],height[i]
        G[x][y] = G[y][x] = 1
        H[x][y] = H[y][x] = h

    global ans
    ans = 0
    paths = []
    def getpaths(s,g,path,route):
        global ans
        if G[s][g] == 1:
            tmp = getmaxh(path+[H[s][g]])
            if tmp >= ans: ans = tmp
            else:
                for i in range(1,N-1):
                    if H[s][g] < H[s][i]:
                        break
                else:
                    return
        for i in range(1,N-1):
            if G[s][i] == 1 and H[s][i] >= H[s][g] and i not in route:
                getpaths(i,g,path+[H[s][i]],route+[i])
    
    getpaths(0,N-1,[],[0])

    return ans