13回目のSRM。EasyMedが通って部屋2位全体160位くらい。842 -> 902 (+60)。なんとか緑に回復したが、やるだけのEasyMedでへんに時間を食ってしまったのがもったいない。

Easy 250: PeacefulLine

数列が与えられ、それを並び替えることを考える。並び替え後に同じ数字が隣り合う事のないような並べ方にできるかどうかを答える問題。

解法

数列中の一番多い数が数列の要素数の半分以下ならそのような並び替えが可能である。半分までなら[a, ?, a, ?, ... , a, ?, a]という風に並べることができるからである。

def makeLine(self, x):
    t = 0
    for i in x:
        t = max(t, x.count(i))
    return "possible" if t <= (len(x)+1)/2 else "impossible"

Med 500: TravelingSalesmanEasy

セールスマンがM個の町を配列 visit にしたがって訪問する。彼はいくつかの製品を持っており i 番目の製品は city[i] で売ることができ、proifit[i] のもうけを得ることができる。1度の訪問で売ることができる商品は1つのみで、1度売った商品はそれ以上売ることができない。彼の得ることのできる儲けの最大値はいくらになるかを答える問題。なお同じ町を何度も訪れる場合もある。

解法

単純に貪欲法でいい。ある町を訪れたとき売れる商品の中でもっとも高いものを売っていけば答えが得られる。

def getMaxProfit(self, M, profit, city, visit):
    ans = 0
    used = [False]*(len(city))
    for v in visit:
        mx = 0
        sale = -1
        for i in range(len(city)):
            if city[i] == v and profit[i] > mx and not used[i]:
                mx = profit[i]
                sale = i
        if sale > -1:
            ans += mx
            used[sale] = True
    return ans

Hard 1000: BuildingTowers

Div1Easyの難化バージョン。N個のビルを一直線上に建設することを考えている。ただし、以下の条件を満たす必要がある。

すべてのビルの高さは0以上でないといけない。
各ビルに 1 から N まで番号を振ると、ビル１は高さ０でないといけない。
隣り合うビルの高さの差は K 以下でないといけない。
x[i] 番目のビルの高さは t[i] 以下でないといけない。

これらの条件を満たすとき、建設することのできる最も高いビルの高さを答える問題。ただし N, K は最大1,000,000,000。x と t の要素数は最大500。x[i] < x[i+1] を満たす。

解法

N,Kの制限が大きいので配列でビルの高さを抱えてループ処理することはできない。まず高さ制限がない場合は（N-1)*K が答えであることは明白である。高さ制限がある場合、簡単のために x, t の先頭に1と0をそれぞれ挿入しておく。 abs(t[i] - t[i+1]) が (x[i+1]-x[i])×K よりも大きいときは、どうあっても高い方の制限に到達できないので t[i]（または t[i+1]）をならしていく。これを x, t の要素数回繰り返せば真の高さ制限を得ることができる。こうすることにより、各制限間にのみ注目していけば答えを探すことができるようになる。

ビル i とビル i+1 間に建てられるビルの高さの最大値を計算したい。ここで x-t 平面を考え、点 i (x[i], t[i]) を通る傾き K の直線と、点 i+1 (x[i+1], t[i+1]) を通る傾き -K の直線の交点の x 座標 px を求める。x は整数でないといけないから、点 i から直線を伸ばした場合は int(px)、点 i+1 から直線を伸ばした場合は int(px)+1 が、ビルの高さが最大となるx座標となる。よってビル i とビル i+1 間に建てられるビルの最大高さは、 max((px-x[i])×K+t[i], (x[i+1]-px-1)×K+t[i+1])。

def maxHeight(self, N, K, x, t):
    x,t = list(x),list(t)
    if len(t) == 0: return (N-1)*K
    x,t = [1]+x, [0]+t
    M = len(x)
    for loop in range(M):
        for i in range(M-1):
            t[i+1] = min(t[i+1],t[i]+(x[i+1]-x[i])*K)
            t[i]   = min(t[i],t[i+1]+(x[i+1]-x[i])*K)
    
    ans = 0
    for i in range(M-1):
        px = (K*(x[i]+x[i+1])+t[i+1]-t[i])/2/K
        ans = max(ans, (px-x[i])*K+t[i], (x[i+1]-px-1)*K+t[i+1])
    return max(ans,(N-x[-1])*K+t[-1])