397th, 0pts, +0/-0 challenge
Volatility 394->355
Challenge失敗+システムテスト落ちでDiv2に落ちることが多いので、安全策でChallengeはせず。
結局250がシステムテストで落ちて0点でした。
250: MinimumSquare
二次元空間上の異なる点(座標はすべて整数)が\(n\)(最大値は100)個与えられる。
それらの点のうち\(K\)個以上を線よりも内側に含む正方形の面積の最小値を求める(ただし正方形の各辺は\(x\)軸\(y\)軸に平行であり各頂点の座標は整数)
以下の図の場合は正方形に含まれている点の数は4つ
解法
もし\(x\)軸での範囲がわかっていれば、その範囲に含まれる点を\(y\)座標でソートして\(K\)個ずつ見ていけば\(y\)軸での範囲の最小値が求められる。
このとき縦と横の範囲の長い方+2が正方形の辺の長さとなる。
点の数の最大値は\(n=100\)なので\(x\)軸の範囲をすべての点の組み合わせに対して総当たりしても十分に間に合う。
計算量は総当りの\(O(n^2)\)と内部でソートするときの\(O(n\log n)\)なので\(O(n^3 \log n)\)のはず
方針はあっていたけど残念なミスでシステムテスト死orz
以下のコードは一応Practice通った
# -*- coding: utf-8 -*- import math,string,itertools,fractions,heapq,collections,re,array,bisect class MinimumSquare: def minArea(self, x, y, K): p = [(x[i], y[i]) for i in xrange(len(x))] print p.sort() L = len(p) area = 10**40 for i in xrange(L - K + 1): for j in xrange(i + K, L + 1): candidate = p[i:j] min_x = candidate[0][0] max_x = candidate[-1][0] candidate.sort(key=lambda x: x[1]) L2 = len(candidate) for k in xrange(L2 - K + 1): min_y = candidate[k][1] max_y = candidate[k + K - 1][1] c_x = (max_x - min_x) c_y = (max_y - min_y) r = max(c_x, c_y) + 2 area = min(area, r * r) return area