TopCoder SRM 660 Div1 Easy: Coversta

SRM660に参加。Easy提出被撃墜と1チャレンジミスで-25pt。1208 → 1109 (-99)。負の得点が痛い。

問題

m×nの表があり、各マスには0から9の数字が書かれている。また長さkの整数配列x, yを与えられる。あるマス(i, j)を選んだ時、(i+x[l], j+y[l]) (0 ≦ l < k) のマスをカバーできる。表の中から異なる2つのマスを選んだ時、カバーしているマスの数字の合計をスコアとする。与えられた表から得られるスコアの最大値を答えよ。

解法

まず各マスを選んだ場合の素のスコアを座標とともに記録し、スコアの大きい順に並べる。この配列をscoresとする。
あとはscores[i], scores[j] (0 ≦ i < j < min(k²+1, mn))について被っているマスの数字を減じて、2つのマスを選んだ時のスコアを計算し、スコアの最大値を取っていく。これで答えが求まる。

なぜこの方法で最大値が求まるかは以下のような理由による。
今、あるマスAを選んだとする。次にあるマスBを、カバーするマスがAのカバーするマスと被るように選ぶとする（BがAと同じマスでよいとする）。このときBの選び方は最大でもk²通りしかない。
したがってAに対してk²+1個のマスを調べれば、Aとカバーするマスが被らないようなマスを1つ以上見つけることができる。

scores[i], scores[j] に対して (0 ≦ i < j < min(k²+1, mn))の範囲についてスコアを計算すると、カバーするマスが被らないようなマスの組のスコアが1つ以上ある(k² + 1 ≦ mnのとき)。もしほぼすべてのマスの組でカバーの被りによってスコアがとても小さくなったとしても、カバーの被りの影響を受けないマスの組が1つは含まれることになる。scoresは大きい順に並んでいるのでこの範囲についてスコアを計算すればスコアの最大値を求めることができる。

k² < mnのときはO(k⁵)。それ以外の時はO(n² m² k) ≦ O(k⁵)。したがってO(min(n² m² k, k⁵)。
n, m ≦ 100, k ≦ 10なので最大でも10⁵のオーダーで済む。
以下のコードはpythonだが最大でも250ms程度しかかからなかった。

def place(self, a, x, y):
    n, m, k = len(a), len(a[0]), len(x)
    a = [map(int, list(a[i])) for i in xrange(n)]
    dwr = zip(x, y)
    
    scores = []
    for w in xrange(n):
        for r in xrange(m):
            tmp = 0
            for dw, dr in dwr:
                nw, nr = w + dw, r + dr
                if 0 <= nw < n and 0 <= nr < m:
                    tmp += a[nw][nr]
            scores.append([tmp, w, r])

    scores = sorted(scores, key = lambda z:z[0], reverse = True)
    ans = 0
    for i in xrange(min(k * k  + 1, n * m)):
        s, w, r = scores[i]
        cover1 = set((w + dw, r + dr) for dw, dr in dwr)
        for j in xrange(i + 1, min(k * k + 1, n * m)):
            if i == j: continue
            ss, ww, rr = scores[j]
            cover2 = set((ww + dw, rr + dr) for dw, dr in dwr)
            tmp = s + ss
            for p, q in cover1 & cover2:
                if 0 <= p < n and 0 <= q < m:
                    tmp -= a[p][q]
            ans = max(ans, tmp)
                
    return ans