100個の円（Code Formula 2014 本選）

問題リンク

atcoder.jp

解法

焼きなまし法で通せる！！

以下のソースコードを手元で実行すると10秒程度で実行が終わるため、出力をコピペしてtext(cat)で投げるとOK。

ソースコード

(言語 : python3)

import sys
import random
import math
N=100
X=[]
Y=[]
for i in range(N):
    X.append(random.randrange(i+1,1500-i))
    Y.append(random.randrange(i+1,1500-i))
cnt=0
for i in range(N):
    for j in range(i+1,N):
        if (X[i]-X[j])**2+(Y[i]-Y[j])**2<(i+j+2)**2:
            cnt+=1
time=1
while(cnt>0):
    print("#"*cnt,file=sys.stderr)
    i=random.randrange(N)
    nx=random.randrange(i+1,1500-i)
    ny=random.randrange(i+1,1500-i)
    before=0
    after=0
    for j in range(N):
        if i==j:
            continue
        if (X[i]-X[j])**2+(Y[i]-Y[j])**2<(i+j+2)**2:
            before+=1
        if (nx-X[j])**2+(ny-Y[j])**2<(i+j+2)**2:
            after+=1
    if (before-after)*time>math.log(random.random()):
        cnt=cnt-before+after
        X[i]=nx
        Y[i]=ny
    time+=1
for i in range(N):
    print(X[i],Y[i])

一応軽く解説。0-indexedであるためi番目の円の半径はi+1である。random.randrange(i+1,1500-i)というような定義をしているのは、このように定義すると円が枠をはみ出すことがないためである。

乱数で100個の円のうち好きなものを一つ選んで、その円を（長方形に収まる範囲内で）好きなところに動かすことを考える。

ここで、cntという変数はであって、円iと円jが交わるようなの組の個数と定める。 1個の円の位置を更新したとき、差分だけcntを再計算することで、計算量をO(N²)からO(N)に下げている。（N=100で、実際には約50倍の高速化である。）

提出リンク

atcoder.jp

余談

提出用ファイルを得るためには、以下のようなコマンドを投げるとよい。（windowsだとpowershellを使うべし）

python3 100_circle.py > 100_circle_output.txt

実行するとたくさんの#が流れてくるが、エラー出力なので提出用ファイルの中身には影響しない。 1行の中にある#の数は現在のcntの大きさを表している。これは進捗が確認できて面白いため入れてあるだけなので、不要ならばコメントアウトしても構わない。

おまけ

コードの最後に以下を追加すると図示することができる（matplotlibをインストールしていないとエラーになることに注意）

import matplotlib.pyplot as plt
import matplotlib.patches as patches

fig = plt.figure()
ax = plt.axes()
for i in range(N):
    c=patches.Circle(xy=(X[i],Y[i]),radius=i+1,ec="b")
    ax.add_patch(c)
r=patches.Rectangle(xy=(0,0),width=1500,height=1500,ec="#000000",fill=False)
ax.add_patch(r)
plt.axis('scaled')
ax.set_aspect('equal')
plt.show()

実行結果をプロットしたものは以下のようになる。（注：上記リンクの提出結果と同じ結果ではない。）

実行結果1

実行結果2

実行結果3