過去にVol.1にも挑戦しましたけど、今回も挑戦してみた
とりあえず100点取れました
問題設定
高さ\(H\)、幅\(W\)の長方形の領域上でものが置ける場所かどうかが\(01\)で与えられる。
入力で与えられる長方形(最大\(HW\)個)それぞれについて、上の領域に配置した時に何箇所に置くことができるかを答える
例
高さ1、幅2の長方形を配置することを考える。
以下の盤面の\(0\)がものを置ける場所であり、一番上の列に2箇所、上から3番めの列に2箇所の合計3箇所に配置することができる。
1000 1101 1001 1111 1111 1111 1111
解法
あらかじめどんな大きさの長方形を何個置くことができるか計算しておく。
すべての位置\(i, j\)についてその場所を右下の角として、すべての高さについてその高さのときの最大の長方形の幅を計算し、高さと幅のペアをカウントしておく。
これは動的計画法を使って注目している場所の上と左側をみれば楽に計算できる。
- \(dp[i][j][h]=座標(j,i)を右下の角とする高さhの長方形の最大の横幅\)としたとき、ものを置くことができるある座標について
- 高さが\(1\)の時、\(dp[i + 1][j + 1][1] = dp[i + 1][j][1] + 1\)
- 高さが増える時、\(dp[i + 1][j + 1][h] = \min(dp[i + 1][j + 1][1], dp[i][j + 1][h - 1]))\)
すべての位置とすべての高さでループするので、この部分の計算量は\(O(H^2W)\)
上で計算した結果を用いて各長方形について何箇所におくことができるかを考える。
ある長方形(高さ\(S_i\)、幅\(T_i\))のクエリが与えられた時、上の動的計画法で数えた結果のうち高さが\(S_i\)に等しくかつ幅が\(T_i\)より大きい場合の総和が求めるべき値である。
以下のコードでは動的計画法でカウントした結果を元に高さごとに事前に分けたものをソートして、最大の幅について累積和をとっておいて、二分探索で値を求めている(速くなっているかはわからない
クエリとなる長方形の最大数が\(HW\)なので、この部分の計算量は\(O(HW \log HW)\)ぐらい(？)
import collections import bisect H, W = map(int, raw_input().split()) board = [raw_input() for i in xrange(H)] N = input() query = [tuple(map(int, raw_input().split())) for i in xrange(N)] dp = [[[0]*(H + 1) for j in xrange(W + 1)] for k in xrange(H + 1)] result = collections.Counter() for i in xrange(H): for j in xrange(W): if board[i][j] == '0': dp[i + 1][j + 1][1] = dp[i + 1][j][1] + 1 result[(1, dp[i + 1][j + 1][1])] += 1 for h in xrange(2, i + 2): dp[i + 1][j + 1][h] = min(dp[i + 1][j + 1][1], dp[i][j + 1][h - 1]) if dp[i + 1][j + 1][h] > 0: result[(h, dp[i + 1][j + 1][h])] += 1 else: break acc = collections.defaultdict(list) for (h, w), v in result.iteritems(): acc[h].append([w, v]) for h in acc: acc[h].sort() for h in acc: temp_sum = 0 for i in xrange(len(acc[h]) - 1, -1, -1): temp_sum += acc[h][i][1] acc[h][i][1] = temp_sum for h, w in query: idx = bisect.bisect_left(acc[h], [w, 0]) if idx < len(acc[h]): print acc[h][idx][1] else: print 0
