はじめに
この記事は競プロ Advent Calendar 2022 の 10 日目の記事ですが、ヒューリスティックコンテスト初心者がだらだらと解くだけの記事です。
使用言語はPythonです。
基本的なことしか書いていません。
解く問題は AtCoder 10th Anniversaryになります。
理論値の大体 80 % ~ 90 %を取ることを目標にしています。
atcoder.jp
AtCoder 10th Anniversary
1. 得点を取る
まずは、得点を取らないとヒューリスティックは始まりません。(多分)
なので、1 点でも得点を取るところから始めます。
得点に『カット回数が K 回を超える、または不正な直線を指定した場合は WA となる』、『一つ以上のテストケースで WA、または制限時間超過による TLE で提出全体の判定が WA や TLE になる』と書かれています。
K は入力で『K = 100』が確定しており、不正な直線に関しては問題文に『直線は2つの異なる整数座標 -109 ~ 109 を通る直線として指定する』と書かれています。
ここから 100 回ほど不正とならないように 2 点をランダムで選び、出力することで点数を取ることができそうです。
試しに、以下のようなコードを提出してみます。
from random import randrange
def rand():
return randrange(-10**9, 10**9+1)
N = 100
print(N)
for _ in range(N):
while True:
px = rand()
py = rand()
qx = rand()
qy = rand()
if px == qx and py == qy:
continue
print(px, py, qx, qy)
break
結果は AC となりました、しかし点数は 0 点です。
流石にランダムで 0 点では今後の実装に活かせない為原因を探ることにします。
atcoder.jp
適当な出力結果をビジュアライザで確認したところ、一本も直線が出ませんでした。
値が大きすぎる為か、全てケーキと関係ないところを結んでいるようです。
問題文を見るとケーキの大きさは半径 104 であるため、そもそも半径より大きい座標を指定する必要はないように感じます。
そこで、最初のコードを以下のように変更して提出してみます。
from random import randrange
def rand():
return randrange(-10**4, 10**4+1)
N = 100
print(N)
for _ in range(N):
while True:
px = rand()
py = rand()
qx = rand()
qy = rand()
if px == qx and py == qy:
continue
print(px, py, qx, qy)
break
このコードでは得点を約 59,000,000 点取ることができます。
満点は 100,000,000 点の為、半分以上は取れる計算になります。
atcoder.jp
ビジュアライザでも直線を引けていることが確認できます。
点数の条件や出力方法が分かったので、ここからは実装してさらに点数を上げる方法を考えていきます。
2. アイデアを試す
一発で理想となる答えを求めれるのが理想ですが、ヒューリスティックコンテストではそのような考えでは厳しそうです。
ランダムで直線を選び続けるのも、運で得点が増減するのは避けたいです。
ここは、規則的に直線を引くことで得点の向上を目指します。
ところで、普通ホールケーキは中心を基準に 6 等分や 8 等分のピースに切られることがほとんどです。
これをそのまま応用できないでしょうか。
試しに、ケーキに 50 個の直線を等分に引いてみます。
print(50)
x = 10000
y = 0
for _ in range(25):
print(x, y, -x, -y)
x -= 400
y += 400
for _ in range(25):
print(x, y, -x, -y)
x -= 400
y -= 400
しかし、1 ピース辺りに乗る苺が多すぎて点数が取れないようです。
今度は、上限いっぱいの 100 本を等分に引いてみます。
print(100)
x = 10000
y = 0
for _ in range(50):
print(x, y, -x, -y)
x -= 200
y += 200
for _ in range(50):
print(x, y, -x, -y)
x -= 200
y -= 200
それでも、1 個だけ乗っているピースがなかったりして、かなり厳しいように感じます。
そもそも、この切り方だと最大でピースが 200 個しかできません。
出席者は最大 1000 人の為、このやり方ではかなり不利に感じます。
もっと別の切り方を考える必要があります。
今まではランダム、つまり様々な方向から直線を引いていました。
逆に、全ての直線を縦、または横にするときれいに切り分けれるように感じます。
試しに、等間隔で縦と横に直線を引くことを考えます。
中途半端な数値になりますが、48 本の直線を引いてみます。
print(48)
x = -10000
for _ in range(24):
x += 800
print(x, 0, x, 1)
y = -10000
for _ in range(24):
y += 800
print(0, y, 1, y)
すると、きれいに格子状に分けられて見栄えよく感じます。
しかし、必要な個数のピースが足りないものも多く、まだ 11 個以上存在するピースも目につきます。
今度は 98 本の直線を引いてみます。
print(98)
x = -10000
for _ in range(49):
x += 400
print(x, 0, x, 1)
y = -10000
for _ in range(49):
y += 400
print(0, y, 1, y)
逆に今度は 3 個以下のピースができすぎて、等分のし過ぎが問題になっています。
そこで、中間くらいの配分で直線を引いてみます。
11個以上がほぼなく、程よく分散しているのでこれを提出してみます。
print(63)
x = -10000
for _ in range(24):
x += 800
print(x, 0, x, 1)
y = -10000
for _ in range(39):
y += 500
print(0, y, 1, y)
このコードでは、得点としては約 67,000,000 点取ることができました。
atcoder.jp
3. スコアを求める
先ほどの方法で引いた直線を動かせば、さらに得点を伸ばすことができないでしょうか。
なんとなく、今ある直線を上下か左右に動かせば、得点が増えたり減ったりしそうです。
いわゆる山登り法と言われる方法で、得点の向上を目指します。
今回は適当に直線を動かして、その得点が増えたら動かした状態を採用するということになります。
その為、その状態でのスコア、つまり、どの苺がどの部分に含まれるかを求める必要があります。
ただ求めるだけでは試行回数が減るので、なるべく高速に求める必要があります。
格子状に切るやり方だと、以下のような求め方が考えられます。
例えば、縦に切る線は固定し、横に切る線をランダムに動かしていくことを考えます。
まず縦にだけ切ると、 x 座標が縦のどの直線と直線の間にあるかが分かれば、苺がどこに属するか簡単に判明します。
なので、各苺を下図のように x 座標の位置でグループ分けします。
直線と被る場合は、問題文で『どのピースにも含まれない』と書かれている為、除外する必要があります。
次は横に切った時ですが、縦で分けた各グループごとに、y 座標が横のどの直線と直線の間にあるかが分かれば、その部分の苺の個数が分かります。
全部分の個数から、スコア計算式にあてはめ、スコアを求めることができます。
実装としては、まず縦のグループ分けをする部分は、あらかじめ苺を x 座標でソートしておけば求まります。
さらに各グループごとに y 座標をソートしておき、二分探索で部分ごとの苺の数を高速に求めることができます。
実装としては以下のようになります。
from bisect import bisect_left, bisect_right
def score_check():
x = 0
y = 0
for i in range(10):
x += min(a[i], cnt[i])
y += a[i]
ret = x / y * pow(10, 6)
return round(ret)
N,K = map(int,input().split())
a = list(map(int,input().split()))
Z = [list(map(int,input().split())) for _ in range(N)]
Z.sort()
x,y = [list(i) for i in zip(*Z)]
G = [[] for _ in range(25)]
pos = -10000
cur = -1
for i in range(N):
while pos < x[i]:
pos += 800
cur += 1
if pos == x[i]:
continue
G[cur].append(y[i])
for i in range(25):
G[i].sort()
P = [i for i in range(-10000, 10001, 500)]
cnt = [0] * 10
for i in range(25):
for j in range(40):
k = bisect_left(G[i], P[j+1]) - bisect_right(G[i], P[j])
if 1 <= k <= 10:
cnt[k-1] += 1
score = score_check()
4. 山登り法を試す
スコア計算の実装が終わった為、ここからは実行制限時間まで探索を行います。
制約に『3 sec』と書いているので、大体 2.7 秒くらいまで探索します。
横に切る予定の座標からランダムで座標を増減させ、その得点によって更新するかを判定します。
今回は単純に得点が増えれば更新するだけです。
実装は以下のようになります。
from time import time
from random import randrange
from bisect import bisect_left, bisect_right
def score_check():
x = 0
y = 0
for i in range(10):
x += min(a[i], cnt[i])
y += a[i]
ret = x / y * pow(10, 6)
return round(ret)
N,K = map(int,input().split())
a = list(map(int,input().split()))
Z = [list(map(int,input().split())) for _ in range(N)]
Z.sort()
x,y = [list(i) for i in zip(*Z)]
start_time = time()
G = [[] for _ in range(25)]
pos = -10000
cur = -1
for i in range(N):
while pos < x[i]:
pos += 800
cur += 1
if pos == x[i]:
continue
G[cur].append(y[i])
for i in range(25):
G[i].sort()
P = [i for i in range(-10000, 10001, 500)]
cnt = [0] * 10
for i in range(25):
for j in range(40):
k = bisect_left(G[i], P[j+1]) - bisect_right(G[i], P[j])
if 1 <= k <= 10:
cnt[k-1] += 1
score = score_check()
while time() - start_time < 2.70:
Q = list(P)
for i in range(1,40):
if randrange(1,101) % 2:
if randrange(1,101) % 2:
Q[i] += randrange(1,101)
else:
Q[i] -= randrange(1,101)
flg = False
for i in range(1,40):
if Q[i-1] >= Q[i] or Q[i] >= Q[i+1]:
flg = True
if flg:
continue
cnt = [0] * 10
for i in range(25):
for j in range(40):
k = bisect_left(G[i], Q[j+1]) - bisect_right(G[i], Q[j])
if 1 <= k <= 10:
cnt[k-1] += 1
now_score = score_check()
if now_score > score:
score = now_score
P = Q
print(63)
x = -10000
for _ in range(24):
x += 800
print(x, 0, x, 1)
for i in range(1,40):
print(0, P[i], 1, P[i])
このコードでは約 85,000,000 点を取ることができました。
atcoder.jp
6. 得点アップのアイデアを試す
ところで、途中から縦線と横線の本数を固定していましたが、ケースによっては本数を調整した方がいいのではないでしょうか。
seed = 0 では、縦の直線を 7 本、横の直線を 31 本等間隔に引けば初期の得点だけでも 700,000 点が稼げます。
ところが、これを同じように seed = 10 に適用しても 600,000 点程度しか取れません。
seed = 10 では、縦の直線を 15 本、横の直線を 49 本等間隔に引けば初期の得点だけでも 750,000 点が稼げます。
このことから、まず縦の直線、横の直線を何本引くかを探索した方がよさそうです。
ランダムに動かす予定の横の直線が多くなる方に調整します。
これらをまとめた実装が以下になります。
from time import time
from random import randrange
from bisect import bisect_left, bisect_right
def score_check():
x = 0
y = 0
for i in range(10):
x += min(a[i], cnt[i])
y += a[i]
ret = x / y * pow(10, 6)
return round(ret)
N,K = map(int,input().split())
a = list(map(int,input().split()))
Z = [list(map(int,input().split())) for _ in range(N)]
Z.sort()
x,y = [list(i) for i in zip(*Z)]
start_time = time()
G = [[] for _ in range(25)]
pos = -10000
cur = -1
for i in range(N):
while pos < x[i]:
pos += 800
cur += 1
if pos == x[i]:
continue
G[cur].append(y[i])
score = 0
tate = 0
yoko = 0
for ta in range(2,100):
if 20000 % ta != 0:
continue
t_wide = 20000 // ta
G = [[] for _ in range(ta)]
pos = -10000
cur = -1
for i in range(N):
while pos < x[i]:
pos += t_wide
cur += 1
if pos == x[i]:
continue
G[cur].append(y[i])
for i in range(ta):
G[i].sort()
for yo in range(ta,100):
if 20000 % yo != 0:
continue
y_wide = 20000 // yo
P = [i for i in range(-10000, 10001, y_wide)]
cnt = [0] * 10
for i in range(ta):
for j in range(yo):
k = bisect_left(G[i], P[j+1]) - bisect_right(G[i], P[j])
if 1 <= k <= 10:
cnt[k-1] += 1
now_score = score_check()
if now_score > score:
score = now_score
tate = ta
yoko = yo
t_wide = 20000 // tate
y_wide = 20000 // yoko
G = [[] for _ in range(tate)]
pos = -10000
cur = -1
for i in range(N):
while pos < x[i]:
pos += t_wide
cur += 1
if pos == x[i]:
continue
G[cur].append(y[i])
for i in range(tate):
G[i].sort()
P = [i for i in range(-10000, 10001, y_wide)]
cnt = [0] * 10
for i in range(tate):
for j in range(yoko):
k = bisect_left(G[i], P[j+1]) - bisect_right(G[i], P[j])
if 1 <= k <= 10:
cnt[k-1] += 1
score = score_check()
while time() - start_time < 2.70:
Q = list(P)
for i in range(1,yoko):
if randrange(1,101) % 2:
if randrange(1,101) % 2:
Q[i] += randrange(1,101)
else:
Q[i] -= randrange(1,101)
flg = False
for i in range(1,yoko):
if Q[i-1] >= Q[i] or Q[i] >= Q[i+1]:
flg = True
if flg:
continue
cnt = [0] * 10
for i in range(tate):
for j in range(yoko):
k = bisect_left(G[i], Q[j+1]) - bisect_right(G[i], Q[j])
if 1 <= k <= 10:
cnt[k-1] += 1
now_score = score_check()
if now_score > score:
score = now_score
P = Q
print(tate + yoko - 2)
x = -10000
for _ in range(tate-1):
x += t_wide
print(x, 0, x, 1)
for i in range(1,yoko):
print(0, P[i], 1, P[i])
しかし、これでは得点が変更前と大体同じになってしまいました。
https://atcoder.jp/contests/ahc012/submissions/37015442
7. 感想
今回は約 85 %の点数を取ったところで断念しました。
というより、6 で考えた渾身のアイデアがあまり点数が伸びないことに心がやられました。
考えたアイデアが実はあまり役に立たなかったり、いいアイデアを思いついてもそれが実装できなかったりで、かなり沼だと思いました。
ヒューリスティックでは普段の競プロでは使わないランダムに動かす山登り法や焼きなまし法、スコア上位 K 番目までを残して探索し続けるビームサーチなどがあります。
今回はこれらの練習の為に記事を書こうと思いましたが、焼きなまし法は得点の減少を許す時間などの指定が上手くできなかったのか伸びず、ビームサーチに至っては考えていた実装ができなくて泣きました。
9 割超えると意気込んでいた割に成果を出すことができなかったので、来年リベンジします。(予定)
