グラス的長距離相互作用格子ガス

理系ネタ

http://www.azspcs.net/Contest/DelacorteNumbers
L×Lの正方形に1からL^2までの整数を置く。各整数は他の整数と距離の二乗のエネルギーで相互作用し、その強さは最大公約数に比例。
L=3〜27までの場合に相互作用が正と負の場合の基底状態を求めよ。
締め切りは来年正月。一位賞品はなんかよくわからない店の$500の商品券。さあ統計力学の力を世界に見せ付けるのだ。

TIPS

まあとりあえずメトロポリスでアニールしてみるかという事になるわけですが、そうなると更新はまあ二つを入れ替える、くらいしか思いつかないわけで。その試行でのエネルギー変化の計算がホットスポットですね。素朴にやると演算量はN二乗に比例。
変化だけ計算すればいいことに気がつくとN一乗でいける。
さらにGCDをGCD-1で置き換えても問題が等価ということに気がつけばGCDが１でないペアは全体の４０％程度なのでかなり時間削減できる。
さらにその式を睨んで因数分解し演算数を減らせばさらに倍速くらいに行ける。
あとは一回のステップで扱うテーブル等がすべてキャッシュに収まるようにサイズを減らす。
この辺りまでが小手先でなんとか出来るレベル。
そこから先は出てくる状態を睨んで問題に潜む構造を読み取らねばならないでしょうね。結構奥が深くて面白い問題です。
10x10までやってみた感じではMINよりMAXが難しい。業界で言う所のグラッシーでメタスタに嵌りやすい感じ。