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

[Supership](https://supership.jp/)の名畑です。「[映画「鬼太郎誕生 ゲゲゲの謎」興収が11.5億円を突破！大ヒット御礼で本編冒頭映像が公開](https://animeanime.jp/article/2023/12/12/81781.html)」とのこと。めちゃくちゃ人気のようで本当に嬉しいです。

## はじめに

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

> ABC/ARC/AGCなどのアルゴリズムコンテストと異なり、最適解を出すのが難しい問題に対し、出来るだけ良い解を作成するコンテストとなります。
> 
> [AtCoder Heuristic Contest 001](https://atcoder.jp/contests/ahc001)より

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

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

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

## 対象の問題 AtCoder Ad

- [AtCoder Heuristic Contest 001 A - AtCoder Ad](https://atcoder.jp/contests/ahc001)

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

- 広告を表示できるスペースは **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**しておきます。

```Python
import math
```

### 入力

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

```Python
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**です。

```Python
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**の昇順で並べ替えます。

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

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

### 広告を置いていく

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

```Python
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
```

### 答えの出力

```Python
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**で配置する
1. 広告をランダムに一つ選ぶ
1. 四方のいずれに伸ばすかをランダムに1つ選ぶ
1. 対象の広告を対象の方向に伸ばした結果として満足度が上がるのであれば、それを採用する
1. 2〜4を制限時間以内で繰り返す

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

この考え方について詳しくは[局所探索法](https://ja.wikipedia.org/wiki/%E5%B1%80%E6%89%80%E6%8E%A2%E7%B4%A2%E6%B3%95)や[山登り法](https://ja.wikipedia.org/wiki/%E5%B1%B1%E7%99%BB%E3%82%8A%E6%B3%95)で調べてみてください。

### コード

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

```Python
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%程度**足りませんが、かなりの改善です。

ちなみにコンテスト開催時の[順位表](https://atcoder.jp/contests/ahc001/standings)を見ると、上位は**99%以上**獲得が当たり前の世界です。

## 最後に

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

## 宣伝

[SupershipのQiita Organization](https://qiita.com/organizations/supership-inc)を合わせてご覧いただけますと嬉しいです。他のメンバーの記事も多数あります。

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