11回目のSRM。EasyMedを通して部屋1位、全体30位。HardはTLEだった。他の参加者に比べるとMedを素早く提出できたのがよかった。943 -> 1074。金曜のSRMでDiv1に入る。

Easy 250

長さnの数列(0-based index)が与えられる。この数列は時間が経つごとに次の条件により更新されていく。

前後の数が自分より大きければ、次の時間に1増えた数になる。
前後の数が自分より小さければ、次の時間に1減った数になる。

数列が時間が進んでも更新されなくなったとき、その最終状態を答える問題。

問題文の条件通りにコードを組めばOK。

def performTheExperiment(self, colonies):
    col = list(colonies)
    while True:
        flag = True
        bcol = col[:]
        for i in range(1,len(colonies)-1):
            if bcol[i] > bcol[i-1] and bcol[i] > bcol[i+1]:
                col[i] -= 1
                flag = False
            elif bcol[i] < bcol[i-1] and bcol[i] < bcol[i+1]:
                col[i] += 1
                flag = False
        if flag: break
    return col

Med 500

n個(2 ≦ n ≦ 50)のカートが直線上に並んでいる。カート i の先頭はpositions[i]にあり、その長さはlengths[i]である。また、１つのカートを距離1動かすのにコストが1かかるとする。カートを動かして、すべてのカートを接触している状態にするときの最小コストを答える問題。positionsとlengthsの最大値は10**9。

カートをまとめて動かしても個別に動かしても移動コストは変わらないので１つずつ考えていくことにする。まずカートをlengthsとともにpositionsの大きさ順に並び替える。固定するカートを1つ決め、近い順から左側のカートを動かすコスト、近い順から右側のカートを動かすコストをそれぞれ足し合わせていった値の最小値を取ればそれが答えとなる（このときまとめたカートの先頭と最後尾の位置の更新を忘れないいようにする）。

def minimizeCost(self, positions, lengths):
    n = len(positions)
    both = sorted(zip(positions,lengths))
    positions = [both[i][0] for i in range(n)]
    lengths = [both[i][1] for i in range(n)]
    ans = 10**16
    for fix in range(n):
        tmp = 0
        r = positions[fix]
        l = positions[fix] + lengths[fix]
        for i in range(fix-1,-1,-1):
            tmp += (r-positions[i]-lengths[i])
            r -= lengths[i]
        for i in range(fix+1,n):
            tmp += (positions[i]-l)
            l += lengths[i]
        ans = min(ans,tmp)
    return ans

Hard 1000

n 人がつぎのゲームを k ラウンド行う。

各プレイヤーは m 個のフィールドから1つ選択する。
等確率で1つのフィールドが選ばれる。
選ばれたフィールドを選択していたプレイヤーはゲームから抜ける。プレイヤーたちが k ラウンド後に1人以上のプレイヤーが残っているように最善を尽くすとき、k ラウンド後に1人以上のプレイヤーが残っている確率を答える問題。

ここでいう最善を尽くすとは今いるプレイヤーたち rn 人をm個のフィールドにできるだけ均等に振り分けるという事になる。r = rn%nとすると、ラウンドが進むごとに r/m の確率で rn/m+1 人がゲームから抜け、(m-r)/m の確率で rn/m 人がゲームから抜ける。この状態変化を dfs で追っていけば答えが求められる。ただし、k ≦ 50であるから、工夫しないと 2⁵⁰ ≒ 10¹²個の再帰が呼び出されてしまう。考えてみると、状態変化前後での人数の変化が rn/m+1 か rn/m なので、多く状態をなんども計算していることに気付く。よって残りプレイヤー数と残りラウンド数についてメモを取り、メモ化再帰にしてやればいい。

def findProbability(self, n, m, k):
    memo = {}
    def solve(players,remain):
        if (players,remain) in memo: return memo[players,remain]
        if players <= 0: return 0
        if remain == 0: return 1
        onegroup = players/m
        r = players%m
        res = 1.0*r/m * solve(players-onegroup-1,remain-1)
        res += 1.0*(m-r)/m * solve(players-onegroup,remain-1)
        memo[(players,remain)] = res
        return res
    ans = solve(n,k)
    return ans