TopCoder SRM 646 Div2

12回めのSRM。Easy提出被撃墜、1challenge missで驚きの-25pointで、前々回の再来。頭が悪い。1074 -> 841 (-233)。灰色から出直し。

Easy 250

数列numbersを与えられる。1回の操作である数字に1を加えるか1を減じるかできる。k (k ≦ 2) 個の連続する数字を数列の中に作るとき、必要な操作の最低数を答える問題。

k = 1 のときは明らかに0。k = 2 のときは数列をソートして 前後の数字の差 - 1 の最低値を取ればそれが答えとなる。

def find(self, numbers, k):
    if k == 1: return 0
    numbers = sorted(numbers)
    ans = 10**10
    for i in range(len(numbers)-1):
        ans = min(ans, numbers[i+1]-numbers[i]-1)
    return ans

Meddium 500

xy平面上のいくつかの点にブロックが置いてある。原点からスタートし、1秒で東西南北のどれか1つの向きに進めるとする。もちろんブロックのあるマスには行けない。k 秒後のx座標のとりうる最大値を答える問題。

まずx,yの負符号が邪魔なので適当にインクリメントしておく。平面操作の問題だが、ここでは深さ優先探索よりも幅優先探索の方が重複なく効率よく最大到達距離を操作できる。k が最大1000なので愚直に探索すると間に合わないので、一度訪れた点を管理しておき、訪れていない点へ幅優先で検索していけば訪れうるすべての点を効率よく探索できる。あとはそのx座標の最大値を答えればよい。どう移動してもansを超えられない場合、そこで探索を打ち切ることで計算量を減らしている。なおこの解法はpythonだと計算量がきつく、計算量をきちんと削減していかないと間に合わない。

def find(self, x, y, k):
    xy = zip([xi+1005 for xi in x], [yi+1005 for yi in y])
    visited = [[0]*2010 for _ in range(2010)]
    for x0,y0 in xy:
        visited[y0][x0] = 1
    ans = 1005
    
    que = [[1005,1005,k]]
    while que:
        x0,y0,k0 = que.pop(0)
        if k0 == 0: continue
        if not visited[y0][x0+1]:
            visited[y0][x0+1] = 1
            ans = max(ans,x0+1)
            que.append([x0+1,y0,k0-1])
        if not visited[y0][x0-1]:
            visited[y0][x0-1] = 1
            if k > ans-x0+1: que.append([x0-1,y0,k0-1])
        if not visited[y0+1][x0]:
            visited[y0+1][x0] = 1
            if k > ans-x0: que.append([x0,y0+1,k0-1])
        if not visited[y0-1][x0]:
            visited[y0-1][x0] = 1
            if k > ans-x0: que.append([x0,y0-1,k0-1])
    
    return ans

Hard 1000

あなたのチームは yourScore の得点を持っている。またnumberOfTeams[i]のチームたちはscore[i]の得点を持っている。試合は2チームで行い、勝つと3得点、負けると0得点を得る（引き分けはない）。各チーム残り2試合を戦うことになっている（同じ組み合わせで2試合戦ってもよい）。自分のチームの順位は同じ得点のチームたちの中で最高とする。すべての試合が終わった後、自分のチームが到達しうる最高の順位を答えるという問題。（トーナメントという設定だったけど別にトーナメントの状況じゃないように思える。）

自分のチームが残り2試合勝つ（6得点得る）とするのは当然だが、他のチームの勝ち負けをどうするかが問題となる。自分の得点との差を考えるとそのチームの勝ちが自分のチームの順位に影響を与えるかどうかがわかる。

1.勝っても自分のチームの順位に影響を与えない。

　1-1. score[i]-yourScore > 6で結果によらず自分のチームより順位がいいチームたち

　1-2. score[i]-yourScore ≦ 0で結果によらず自分のチームより順位が悪いチームたち

2.勝つと自分のチームの順位に影響を与える可能性がある。

　2-1. 6 ≧ score[i]-yourScore > 3 で1度勝つと自分より順位が良くなるチームたち

　2-2. 3 ≧ score[i]-yourScore > 0 で2度勝つと自分より順位が良くなるチームたち

得点差によって上のように分類できる。

勝っても自分の順位に影響を与えないチームから勝ってもらいたい。全体の残りの勝ちの数は全チーム数 total と等しく、勝ちの数をこれに合わせる必要がある。まず、できるだけ1に属するチームに勝ってもらい、それでも必要な勝ち数に届かなければ2-2に属するチームに1度ずつ勝ってもらう。それでも必要な勝ち数に届かなければ2-1に属するチームに2度勝ってもらい、さらに必要ならば2-2に属するチームにもう1度勝ってもらう。1-1に属するチーム数に自分を追い抜いたチームの数を足し合わせれば答えとなる。

def find(self, yourScore, scores, numberOfTeams):
    total = 1+sum(numberOfTeams)
    R = len(scores)
    W = sum(numberOfTeams[i] for i in range(R) if scores[i]-yourScore > 6)
    L = sum(numberOfTeams[i] for i in range(R) if scores[i]-yourScore <= 0)
    A1 = sum(numberOfTeams[i] for i in range(R) if 6 >= scores[i]-yourScore > 3)
    A2 = sum(numberOfTeams[i] for i in range(R) if 3 >= scores[i]-yourScore > 0)
    
    ans = W+1
    remain = total-2*(W+L+1)-A2
    if remain > 0:
        if remain <= 2*A1:
            ans += (remain+1)/2
        else:
            remain -= 2*A1
            ans += A1+remain
    return ans

落ち着いて考えればHardにしては簡単な方だと思う。