ABC432 D問題: 問題の解法と計算量の考察
ABC432 D問題: 問題の解法と計算量の考察
導入
本問題は問題文を一読するだけだと幾何的なイメージがつきにくく、またシミュレーションの実装も重たいため難問であると感じました。
大嵐の処理が矩形の分割と平行移動の組み合わせだとわかりさえすれば解法への見通しが立ちます。
まず大嵐による変形の特性を確認し、シミュレーションと連結判定の実装手順を説明した上で、この実装による計算量について考察します。
問題文
全文：ABC 432 D - Suddenly, A Tempest
2 次元グリッド上の長方形をクエリに従って変形する問題です。詳しくは次の項で読み解きます。
問題の読み解き
以下では入力例の図に従って
入力例 1 を見ると、まず 1 回目の大嵐 X 2 2 によって
2 回目の大嵐 Y -1 1 では境界線
図 1: 大嵐による変形の基本イメージ
問題文の説明だとわかりづらいですが、大嵐による変形は直観的には「境界線で全領域を 2 分割し、互いの領域を境界線に沿って平行移動する」という操作に相当します。
操作の特性から、分割された矩形同士が重なることはありえません。
すべての操作が終わった後に矩形の連結を調べて各連結成分の合計面積を計算します。
以上を踏まえ、問題を解く方針を次のように立てました。
- 各大嵐のシミュレーションを「矩形の分割」と「矩形の平行移動」に分けて実装し、分割によって生じたすべての矩形について位置とサイズの情報を得る
- 各矩形の辺の位置をキーとし、軸と平行な線上に辺を持つ矩形を
x y - 各グループに含まれる矩形同士について、線分の交差判定を利用して隣接の有無を判定する
- DSU (Disjoint Set Union, Union-Find) によって矩形間の連結状態を管理し、最後に連結成分の面積をそれぞれ求める
以下でそれぞれの実装におけるポイントを説明し、その後に具体的な実装を示します。
シミュレーションの実装
大嵐が来る前は 1 個の矩形のみが存在します。
1 回の大嵐に対し、その時点で存在するすべての矩形について処理を行います。
矩形が境界線をまたがない場合は適切な方向へ平行移動させ、境界線をまたぐ場合は 2 つの矩形に分割してそれぞれを平行移動させます。
そこで矩形を表す Rect クラスを作成し、平行移動と分割に対応する shift, split メソッドを実装しました。位置とサイズを持つ tuple で管理することも可能ですが、クラスを作成したほうがコードの見通しがよくなり、ミスを避けられます。
また split を行った際に幅と高さが負やゼロになる場合は ValueError を送出するようにしました。ミスによる WA を RE として検出できるため、原因を絞り込むのが楽になります。
各矩形の辺によるグループ化
隣接する可能性がある矩形は同一線上に辺を持つもの同士のみです。この線の座標により矩形をグループ化することで、隣接しうる矩形同士のみを比較し、それ以外の比較をせずに済みます。これによって計算量の削減が見込めます。
また各グループは「辺が一直線上にある」という条件を満たすため、矩形の隣接判定をより単純な線分の交差判定に帰着でき、実装が簡単になります。
具体的には共有する線の
図 2: 矩形のグループ化の模式図
矩形同士の隣接判定を行って連結する
グループ化した各矩形のうち、実際に辺が重なるもの同士を連結させます。
連結状態の管理には DSU が使えます。矩形に index を割り振り、隣接するとわかった矩形の index 同士を merge することで連結成分をまとめることができます。
DSU の実装自体はネット上に多数公開されており、私は今回 ある(Aru)'sテクログ さんの実装を借用しました。
分割を繰り返した後の矩形の数はどんなに多く見積もっても
また、一直線上にある線分は
図 3: 線分の交差判定
実装例
import itertools
# 引用：https://tech.aru-zakki.com/python-unionfind/
# Disjoint Set Union: Union Find Tree
class DSU:
def __init__(self, n):
self.n = n
self.parentOrSize = [-1] * n
def merge(self, a, b):
x, y = self.leader(a), self.leader(b)
if x == y:
return x
if -self.parentOrSize[x] < -self.parentOrSize[y]:
x, y = y, x
self.parentOrSize[x] += self.parentOrSize[y]
self.parentOrSize[y] = x
return x
def same(self, a, b):
return self.leader(a) == self.leader(b)
def leader(self, a):
if self.parentOrSize[a] < 0:
return a
self.parentOrSize[a] = self.leader(self.parentOrSize[a])
return self.parentOrSize[a]
def size(self, a):
return -self.parentOrSize[self.leader(a)]
def groups(self):
m = {}
for i in range(self.n):
x = self.leader(i)
if x in m:
m[x].append(i)
else:
m[x] = [i]
return list(m.values())
class Rect:
def __init__(self, x, y, w, h) -> None:
self.x = x
self.y = y
self.w = w
self.h = h
def left(self):
return self.x
def bottom(self):
return self.y
def right(self):
return self.x + self.w
def top(self):
return self.y + self.h
def shift(self, shift_axis, amount):
"""shift_axis 軸方向に移動する"""
if shift_axis == "X":
self.x += amount
else:
self.y += amount
def split(self, split_axis, a):
"""a を通り split_axis 軸に垂直な線で矩形を分割し、右上側の矩形を返す"""
if split_axis == "X":
new_rect = Rect(a, self.y, self.right() - a, self.h)
self.w = a - self.left()
if not (self.left() < a < self.right()):
raise ValueError
else:
new_rect = Rect(self.x, a, self.w, self.top() - a)
self.h = a - self.bottom()
if not (self.bottom() < a < self.top()):
raise ValueError
return new_rect
def area(self):
return self.w * self.h
def solve1(n, x, y, t):
# 各大嵐で矩形を分割処理する
rects = [Rect(0, 0, x, y)]
for c_i, a_i, b_i in t:
for rect in rects[:]:
if c_i == "X":
shift_axis = "Y"
split_axis = "X"
lower = rect.left()
upper = rect.right()
else:
split_axis = "Y"
shift_axis = "X"
lower = rect.bottom()
upper = rect.top()
if a_i <= lower:
rect.shift(shift_axis, b_i)
elif upper <= a_i:
rect.shift(shift_axis, -b_i)
else:
new_rect = rect.split(split_axis, a_i)
new_rect.shift(shift_axis, b_i)
rect.shift(shift_axis, -b_i)
rects.append(new_rect)
# x 座標, y 座標ごとに連結判定を行うグループを分ける
x_segments = {}
y_segments = {}
for i, rect in enumerate(rects):
# segments[pos] = (lower, upper, idx)
x_segments.setdefault(rect.left(), []).append((rect.bottom(), rect.top(), i))
x_segments.setdefault(rect.right(), []).append((rect.bottom(), rect.top(), i))
y_segments.setdefault(rect.bottom(), []).append((rect.left(), rect.right(), i))
y_segments.setdefault(rect.top(), []).append((rect.left(), rect.right(), i))
# 各グループ内の 2 矩形間で連結判定と連結を行う
dsu = DSU(len(rects))
for d in (x_segments, y_segments):
for segments in d.values():
for segment1, segment2 in itertools.combinations(segments, 2):
lower1, upper1, idx1 = segment1
lower2, upper2, idx2 = segment2
# 範囲の公差判定
if max(lower1, lower2) < min(upper1, upper2):
dsu.merge(idx1, idx2)
# 各連結成分の面積を求める
areas = []
for idx_group in dsu.groups():
s = 0
for idx in idx_group:
s += rects[idx].area()
areas.append(s)
areas.sort()
return areas
計算量の考察
時間計算量は矩形を分割・平行移動する回数と、最終的に生じた矩形同士での隣接判定の回数との和に支配されます。
各大嵐の処理で常にすべての矩形が切断されると仮定すると、矩形を処理する回数はたかだか
最悪計算量
最悪計算量を評価するため矩形の総数として
すべての矩形の辺が一つの線に含まれるような状態が発生したと仮定すると、上述したコードの時間計算量は
と見積もれます。ただしこの矩形数
平均計算量
ここでは平均計算量を理論的に導出することはせず、実際にランダムなケースを実行した結果を集計するに留めます。
上述したコードを
| N | max(segs) | len(rects) | |
|---|---|---|---|
| 平均値 | 14 | 2.72 | 9.94 |
| 平均値 | 28 | 3.52 | 20.64 |
| 平均値 | 56 | 4.52 | 43.48 |
| 最大値 | 14 | 18 | 40 |
| 最大値 | 28 | 26 | 84 |
| 最大値 | 56 | 30 | 164 |
| 標準偏差 | 14 | 1.40 | 4.71 |
| 標準偏差 | 28 | 1.90 | 10.34 |
| 標準偏差 | 56 | 2.48 | 23.32 |
ここで
この結果から、隣接判定を行う矩形グループのサイズは大半が 4-5 個以下、矩形の総数はおおよそ
まとめ
本問題は幾何的なイメージの掴み方、実装、計算量の見積もりのそれぞれに山がある難問でした。
実際には時間制限があるためクラスを用いた構造化は避けることが多いですが、こういった複雑な問題に対しては有効なアプローチとなりそうです。
計算量については評価しきれなかった部分があるため、ご指摘などあればぜひコメントをお寄せください。
Discussion