2013-02-25から1日間の記事一覧
問題文 : 住み心地解法 : もし, ランク X がある区画Aの住み心地の中央値になれば, ランクX + 1 が他のどの地点にあったとしても, 区画A での中央値はX となる. そこで, ランクについて二分探索を行い, 中央値になりうるかを確かめる. ランクの地点が影響を…
問題文 : 庭園解法 : O(n^3) で長方形列挙を行い, 上下左右から周長の最大値を記録してやれば良い. 長方形列挙は, y 軸の2 点はO(H^2) で決め打ち, x 軸については尺取り法でO(W) で求めれば良い.計算量はO(WH^2) だが, 制限時間ギリギリなので結構大変.コー…