TopCoder SRM 660 Div1 x-- 1232->1250

あとちょっとでeasyが解けそうだったけど、残念ながら今回も1問も解けずorz

230位, 0.0点, +0/-0 challenge
Volatility: 218->201

250: Coversta

各マスに\(0\)から\(9\)の数字が書かれた四角形の盤面と、最大の長さが\(10\)の配列\(x, y\)が与えられる
盤面のうち\(2\)つの位置を指定する
指定した位置に配列\(x, y\)のそれぞれの要素\((x[k], y[k])\)を足したそれぞれの位置にあるマスがカバーされる
適当な\(2\)つの位置を指定して、カバーされたマスの数値の合計の最大値を求める(共通してカバーしているマスは\(1\)回分しか数えない)

解法

位置\(a\)を単独で指定した時のカバーする合計値を\(score_a\)とおく
\(a, b\)が共通のカバーするマスを持つ位置で最大値になるペアで、\(a, c\)がまったく共通のカバーするマスを持たない位置で最大値になるペアと考える
位置\(a, b\)が共通でカバーするマスの合計値を\(score_{a\cap b}\)と置くと、合計が最大になる場合は以下の2通り

• カバーするマスが共通している場合: \(score_a + score_b - score_{a\cap b}\)
• カバーするマスがまったく共通していない: \(score_a + score_c\)

以上のことからカバーするマスが共通しているときに最大になる場合を考えると、\(score_a + score_b - score_{a\cap b} > score_a + score_c\)
この時\(score_b > score_c\)となるので、\(1\)箇所を指定した時残りの\(1\)箇所は、\(score_c\)より大きくなる
カバーするマスがまったく共通していないときに最大になる場合は\(score_c\)そのものなので、結局\(score_c\)以上の位置についてだけを調べればよい

配列\(x, y\)の長さを\(K\)とする
重複する可能性があるマスの数を見積もると、配列\(x, y\)で与えられた位置のすべてのペアについて考えればよいので\(K(K-1)\)個ぐらい(もっと小さくできる？

各位置を単独で指定した時のカバーする合計値を計算してソートしておく
単独で見た時の合計値が多い順に\(K(K-1)+2\)個を見れば、\(score_c\)が必ず含まれている(\(K=1\)の時のために\(+2\)しているが、\(K>1\)のときは\(K(K-1)+1\)でよいはず)
なので上位\(K(K-1)+2\)個の合計値になる位置のそれぞれのペアについて最大値を求めれば正しい答えが得られる

盤面の縦幅、横幅を\(N, M\)とすると計算量は\(O(NMK + NM \log NM + K^5)\)ぐらい

\(2\)つの位置を単独で見た時の合計値の和が現在の最大値より少ない場合は枝刈りしてもよいかも

# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect

class Coversta:
    def place(self, a, x, y):
        n = len(a)
        m = len(a[0])
        K = len(x)
        
        temp = []
        for i in xrange(n):
            for j in xrange(m):
                cum = 0
                for k in xrange(K):
                    p = j + y[k]
                    q = i + x[k]
                    if 0 <= q < n and 0 <= p < m:
                        key = (p, q)
                        cum += int(a[q][p])
                temp.append((cum, i, j))
        temp.sort(reverse=True)
        
        result = 0
        for score1, ti, tj in temp[:K * (K - 1) + 2]:
            i, j = ti, tj
            visited = set()
            for k in xrange(K):
                p = j + y[k]
                q = i + x[k]
                if 0 <= q < n and 0 <= p < m:
                    key = (p, q)
                    if key not in visited:
                        visited.add(key)
            tcum = score1
            for score2, i, j in temp[:K * (K - 1) + 2]:
                if score1 + score2 <= result:
                    break
                v2 = visited.copy()
                cum = 0
                if ti == i and tj == j:
                    continue
                for k in xrange(K):
                    p = j + y[k]
                    q = i + x[k]
                    if 0 <= q < n and 0 <= p < m:
                        key = (p, q)
                        if key not in v2:
                            v2.add(key)
                            cum += int(a[q][p])
                cum += tcum
                if result < cum:
                    result = cum
        return result