AtCoder Heuristic Contest(AHC)はどんな問題なのだろうと思って初めて解いてみた記録[Python]

Supershipの名畑です。「映画「鬼太郎誕生 ゲゲゲの謎」興収が11.5億円を突破！大ヒット御礼で本編冒頭映像が公開」とのこと。めちゃくちゃ人気のようで本当に嬉しいです。

はじめに

これまで私の記事で何度も取り上げてきた競技プログラミングのサイトAtCoderには大きく分けて2種類のコンテストがあります。そのうちの一つがABC、ARC、AGCなどのアルゴリズムコンテストであり、もう一つがAtCoder Heuristic Contest(AHC)です。

ABC/ARC/AGCなどのアルゴリズムコンテストと異なり、最適解を出すのが難しい問題に対し、出来るだけ良い解を作成するコンテストとなります。

AtCoder Heuristic Contest 001より

今までこのAHCの問題を解いたことはなかったのですが、試しに解いてみたというのが今回の記事の趣旨となります。

コードを提出してスコアが出るまでを目的としているので「攻略法を示すわけではない」です。
高得点をとるまでを解説してはいません。

私と同じで「AHCってなにそれ？」みたいな人が「ああ、AHCってこんなものなんだー」と思うためだけの記事です。

対象の問題 AtCoder Ad

• AtCoder Heuristic Contest 001 A - AtCoder Ad

ざっくりとは下記のような問題です。

• 広告を表示できるスペースは 10000 × 10000
• 広告は長方形でなくてはいけない
• n社の広告を設置する
• どの企業にも広告に対して希望する座標(xとy)と面積(r)がある
• 会社毎の満足度は希望する座標が含まれない場合は0となります
• 会社毎の満足度は希望する座標が含まれる場合はrにどれだけ近い面積であるかで決まり、正確には面積をsとすると 1 - (1 - min(r, s) / max(r, s)) ^ 2 となる
• 満足度の合計が大きくなるようにコードを書く

つまりはできる限り希望を満たすように広告をスペース内に収めるという問題です。

コード

Python (PyPy 3.10-v7.3.12) で書きました。

import

あとでmathを用いるのでimportしておきます。

import math

入力

adsという2次元配列にx、y、rを格納しておきます。
あとで使うので、何番目かを示すiも格納します。

N = int(input())
ads = [[] for i in range(N)]
for i in range(N):
    x, y, r = map(int, input().split())
    ads[i] = [x, y, r, i]

定数と変数の用意

ansは答えを格納するためのものです。長方形の対角となる2頂点の座標 (x0, y0, x1, y1) です。
dotsはスペースの各座標にすでに広告があるかどうかを格納します。初期値はすべてFalseです。

MAX_LENGTH = 10000
ans = [[0, 0, 0, 0] for i in range(N)]
dots = [[False] * (MAX_LENGTH + 1) for i in range(MAX_LENGTH + 1)] 

並べ替え

今回は

• 小さい広告から順番に、xとyを左上とし、面積r以上の正方形を、置けるなら置いていく
• 面積rで広告が置けないときは、空いている場所に1 × 1のサイズで置く

という非常にシンプルなアルゴリズムで実装してみます。

ですので、rの昇順で並べ替えます。

sorted_ads = sorted(ads, reverse=False, key=lambda x: x[2])

別にadsを上書きしてもいいのですが、あとでスコア計算をしたくなった時に元のadsもあった方が良さそうなので残しておきました。

広告を置いていく

雑ですが下記です。
説明はコメントを読んでください。

for val in sorted_ads:
    x, y, r = val[0], val[1], val[2]
    length = math.ceil(math.sqrt(r))  # rを満たす正方形として各辺の長さを求める
    copy_dots = dots.copy()
    check = True
    
    # 左上から順番に走査する
    for j in range(y, y + length):
        for k in range(x, x + length):
            # すでに広告が置かれていれば走査終了
            if j > MAX_LENGTH or k > MAX_LENGTH or copy_dots[j][k]:
                check = False
                break
            copy_dots[j][k] = True  # 広告が置かれたこととする
        if not check:
            break

    if check:  # 広告を置けた
        dots = copy_dots.copy()  # 広告を置いた状態でdotsを更新する
        ans[val[3]] = [x, y, x + length, y + length]  # 答えを格納する
    else:  # 広告を置けなかった
        check = False
        # 左上から走査し、空いているスペースに1 × 1で広告を置いてしまう
        for j in range(0, MAX_LENGTH):
            for k in range(0, MAX_LENGTH):
                if not dots[j][k] and not dots[j + 1][k + 1]:
                    dots[j][k] = dots[j + 1][k + 1] = True  # 広告を置く
                    ans[val[3]] = [k, j, k + 1, j + 1]  # 答えを格納する
                    check = True
                    break
            if check:
                break

答えの出力

for i in range(N):
    print(*(ans[i]))

結果

提出してみると、得点は約20,000,000,000でした。
満点は50,000,000,000なので、半分にすら到達していない。

このコードのダメなところ

• 線同士は重なっていいルールであるが、線同士も重ならないコードとなっていて無駄がある
• 正方形である必要がない
• r以上の正方形で置けないときは、1 × 1のサイズとしてしまっている
• xとyが左上である必要もない
• 実行時間が5sec与えられているが2sec程度しか使っていない。
• 広告の数は最大でも200なので、重なり判定のためだけに2次元配列を走査するのは重い

などなど。

改善してみる

上記コードだとあまりに雑すぎるので少し改善してみます。
アルゴリズムを変更してみます。

1. すべての広告において、まずはxとyを基準位置として1 × 1で配置する
2. 広告をランダムに一つ選ぶ
3. 四方のいずれに伸ばすかをランダムに1つ選ぶ
4. 対象の広告を対象の方向に伸ばした結果として満足度が上がるのであれば、それを採用する
5. 2〜4を制限時間以内で繰り返す

これであれば先ほどのコードのダメなところがすべて改善されていいます。

この考え方について詳しくは局所探索法や山登り法で調べてみてください。

コード

コードは以下です。
先ほどのコードよりずっとシンプルなので、コメントだけでわかるかと思います。

import time
import random

start_time = time.time() * 1000  # 開始時刻

N = int(input())
MAX_LW = 10000  # スペースの縦と横
ads = [[] for i in range(N)]  # 入力値保存
ans = [[0, 0, 0, 0] for i in range(N)]  # 広告毎の配置座標

for i in range(N):
    x, y, r = map(int, input().split())
    ads[i] = [x, y, r]
    ans[i] = [x, y, x + 1, y + 1]  # 1 × 1を初期値とする

while True:
    # 結果出力のための100msecを余して終了(ギリギリを攻めすぎるとオーバーするので要注意)
    if time.time() * 1000 - start_time > 4900:
        break

    ad = random.randrange(N)  # 広告をランダムに選ぶ
    direction = random.randrange(4)  # 方向をランダムに選ぶ 上右下左

    # 現在の座標(x1,y1,x2,y2)と伸ばした後の座標(x1d,x2d,y1d,y2d)
    x1, y1, x2, y2 = ans[ad][0], ans[ad][1], ans[ad][2], ans[ad][3]
    x1d, y1d, x2d, y2d = x1, y1, x2, y2

    if direction == 0:  # 上
        y1d -= 1
    elif direction == 1:  # 右
        x2d += 1
    elif direction == 2:  # 下
        y2d += 1
    elif direction == 3:  # 左
        x1d -= 1

    # 伸ばす前後の満足度判定
    before_s = (x2 - x1) * (y2 - y1)
    after_s = (x2d - x1d) * (y2d - y1d)
    before_score = 1 - (1 - min([before_s, ads[ad][2]]) / max([before_s, ads[ad][2]])) ** 2
    after_score = 1 - (1 - min([after_s, ads[ad][2]]) / max([after_s, ads[ad][2]])) ** 2
    if before_score >= after_score:
        continue

    # はみ出ていないか判定
    if x1d < 1 or y1d < 1 or x2d > MAX_LW or y2d > MAX_LW:
        continue

    # 重なっていないか判定
    overlap = False
    for i in range(0, N):
        if i == ad:
            continue
        elif (ans[i][0] < x1d and ans[i][2] < x1d) or (ans[i][0] > x2d and ans[i][2] > x2d):
            continue
        elif (ans[i][1] < y1d and ans[i][3] < y1d) or (ans[i][1] > y2d and ans[i][3] > y2d):
            continue
        overlap = True

    # 座標の更新
    if not overlap:
        ans[ad] = [x1d, y1d, x2d, y2d]

# 出力
for i in range(N):
    print(*(ans[i]))

結果

45,000,000,000を超えました。 90%超です。
まだ満点には 10%程度足りませんが、かなりの改善です。

ちなみにコンテスト開催時の順位表を見ると、上位は99%以上獲得が当たり前の世界です。

最後に

アルゴリズムコンテストとはまた違った面白さがありますね。
もうちょっとやってみようかな。

宣伝

SupershipのQiita Organizationを合わせてご覧いただけますと嬉しいです。他のメンバーの記事も多数あります。

Supershipではプロダクト開発やサービス開発に関わる方を絶賛募集しております。
興味がある方はSupership株式会社 採用サイトよりご確認ください。