早稲田卒のAI研究者のブログ

データサイエンス、機械学習、競技プログラミング、音楽、勉強

【愚直全探索】ABC075 D - Axis-Parallel RectangleをPythonで解いてみた

atcoder.jp



全探索のアルゴリズムを勉強するために、上記の問題を解いてみました。
その思考の過程をブログに書いて皆さんに共有することで自分を高めたい、そういうわけです。めっちゃ利己的。
そういうわけなので議論があればよろしくお願いします。

問題文は各自上記のページから見てください。

思考過程


なるほどなるほど…。

座標を用いるような視覚的な問題は、とりあえず図を書いてみましょう。

f:id:mashkun:20191015203046p:plain

上にN=5, K = 5または3のときの長方形を書いてみました。
図からわかることとして、内部に含んでいる点のうち最端のものが長方形の辺の境界になる、ということ。
具体的に言うと、長方形の横と縦の長さはそれぞれ、長方形に含まれている点(x、y)の最大値最小値の差になる、ということ。

これが分かれば、とりあえず候補となる長方形の面積は求められそう。
だが、特定のK個の点に対する最小面積を見つけるためのうまい方法が思いつかない。
というのも、存在する全ての点に対して長方形を含ませるかを検討し、面積を求める必要があるからだ。
そこで、仕方なく愚直に全探索してみる。

全探索の方法としてはシンプル。
まず、与えられた点すべてを含む長方形を考える。
次に、長方形の横の長さを固定して、縦の長さを変えていく。
辺の長さを変えたあと、長方形に含まれる点の数を計算する。
もし点の数がK以下だったら、面積を求める。
というもの。

下図は、辺の長さを変えていく過程。

f:id:mashkun:20191015203043p:plain

これをコードに起こしてみる。

コード実装

プログラムの流れは以下のようにする。
1. x座標とy座標を別のリストで保持
2. x座標とy座標をソートしたリストを新たに作成
3. 長方形の辺を狭めていくために4つのfor文を利用
4. 長方形に含まれる点の個数を計算
5. 面積を求め、以前計算した面積よりも小さいか否かを判定


N, K = map(int, input().split())
x_list = [0]*N
y_list = [0]*N
for i in range(N):
    x_list[i], y_list[i] = map(int, input().split())  # x座標とy座標を別のリストで保持

x_sort_list = sorted(x_list)
y_sort_list = sorted(y_list)  # x座標とy座標をソートしたリストを新たに作成
ans = float("inf")

for i in range(len(x_sort_list)):  # 長方形の辺を狭めていくために4つのfor文を利用
    for j in range(len(y_sort_list)):
        for k in range(i+1, len(x_sort_list)):
            for l in range(j+1, len(y_sort_list)):
                num = 0
                for m in range(N):
                    if x_sort_list[i] <= x_list[m] <= x_sort_list[k] and y_sort_list[j] <= y_list[m] <= y_sort_list[l]:
                        num += 1  # 長方形に含まれる点の個数を計算
                if num >= K:
                    ans = min((x_sort_list[k] - x_sort_list[i]) * (y_sort_list[l] - y_sort_list[j]), ans)
                    # 面積を求め、以前計算した面積よりも小さいか否かを判定
print(ans)

無事、ACでした。*1


*1 Python3ではTLEだったのでPyPy3で通しました。