びったんびったん

ユーザビリティ・プログラミングについて。

ビームサーチは DP

この記事は Competitive Programming (1) Advent Calendar 2018 - Adventar の 6 日目です。
5 日目の記事は armeria_betrue さんの 解説記事のはなし - ARMERIA です。
7 日目の記事は xuzijian629 さんの Implicit Treap - 競プロ練習記録 です。

ビームサーチとは

ビームサーチとはグラフのヒューリスティック探索アルゴリズムです。 初期ノード群から BFS 順に探索していき、深さ(初期ノードからの遷移回数)ごとに良さそう順のノードの上位 N コ以外を枝刈りすることで時間 / 空間計算量を改善します。

58-72p でくわしく説明されているので引用します。

本記事の趣旨

ビームサーチといったら上述のような説明が定番?です。 その説明は正しいのですが、私はビームサーチを上述を含んだより広汎なアルゴリズムだと思っています。なので、私の現在の解釈である「ビームサーチは DP の拡張」という観点で説明してみます。 色々な視点から同じものの説明がなされるのも一般に良いことですし。

ビームサーチは DP

DP の説明は省略します。

f:id:hakomof:20181205200921p:plain

例えば、木を探索するとして、どんな経路を通ったかによらず以降の最適な経路が同じ状態を同一とみなすと、木は DAG になり合流部以降の重複探索をなくすと DP になります。 つまり、どういう状態群を同一とみなすかは DP の一端です。

同様に今度は深さが同じ状態群を同一とみなして DP で解いてみましょう。

f:id:hakomof:20181205200949p:plain

単純な形ですが DAG は DAG です。 この DAG を DP するコードを起こすとこんなかんじでしょうか。

State dp[Depth];
dp[0] = initialState;
for (int d = 0; d < Depth - 1; ++d) {
    for (State nextState : dp[d].getAllNextStates()) {
        dp[d + 1] = max(dp[d + 1], nextState);
    }
}

お気づきいただけただろうか… この配る DP の振る舞いは幅 1 のビームサーチと完全に一致します(なにやら冗長なただの greedy でもよいです)。 なぜ一致するのかというとビームサーチが DP そのものだからというほかないです。 結局、ビームサーチは深さごとに状態をまとめる、 DAG になる、 DAG のトポロジカル順序である深さの昇順にビームを更新していく、と DP をしているに過ぎなかったのです。

ビームサーチの DP との違い

  • 状態のまとめ方が過剰
  • 評価関数
  • ビーム幅

状態のまとめ方が過剰

効率的な探索をしてなお最適解が現実的な時間で求まらないとき、非最適解でよいから現実的な時間で求めたいという動機があります。 そこで、現実的な実行時間になるまで状態を過剰にまとめるというのが思想の出発点だと思っています。

評価関数

本来異なる状態を同一とみなす以上、最適解に通じる状態が残るとは限りません。 ですが、状態のつぶれた情報をフルに駆使した評価関数で精度の底上げができます。

ビーム幅

例えば、実行時間が 10 秒くらいになるような状態数が 500 万くらいに状態をまとめるといった器用なことはできません。 そのため、実行時間と性能に融通が利きません。 ですが、ビーム幅を導入すると実行時間は約ビーム幅倍になり相応に性能が上がる(ことがある)ので、少し融通が利くようになります。


以上よりビームサーチは状態の過剰なまとめを許容する形に拡張された配る DP だと思っています。

で、何ができるの?

  • ビームは深さ以外でも切れます
  • あるビーム内状態の次状態は直後のビームでなくてよいです
  • 1 次元でなくてよいです
  • ビームサーチ以外の嘘 DP との併用や換装ができます
  • DP の知見が流用できます

例えば以下のような 2 次元の DP をビームサーチ化するとしたら、ビームはタテにもナナメにも切れます(切った後も DAG になっています)。 逆にヨコにはループができるので切れません。1

f:id:hakomof:20181205212430p:plain

f:id:hakomof:20181205212441p:plain

f:id:hakomof:20181205212503p:plain

ビームをどう切るかで性能が大きく変わるのは想像にたやすいでしょう。 肝心のビームをどう切ればよいかですが、 パラメータが違う状態同士の優劣判断が一番難しいパラメータで切るのが良さそうに思います。 なぜなら、各ビームにはそのパラメータが同じ状態しか含まれないので、そのパラメータを評価関数に含めなくてよくなるからです。 例えば、ゲーム AI などで 5 ターン目と 100 ターン目の比較は難しいからビームをターンで切るといったかんじです。

おわりに

近年マラソンをする人が増えうれしい限りで、焼きなまし / ビームサーチを覚えたい / 覚えたといったツイートをよく見かけるようになりました。 しかし、インターネット上の情報は少なく例も単純です。 そこで、実際のビームサーチ(や焼きなまし)が単純な例よりもはるかに柔軟でそれ自体に工夫の余地が多いことを少しでも感じてもらえたらなと思い本記事を書きました。 もちろん、それ以前のどんな方針を立てるかがマラソンで一番おもしろいとは思います。 ですが、ビームを撃つとか焼くとか決めた上でそれ自体を改造するのも十分おもしろいので楽しんで欲しいなと思います。


  1. 切れないことはない

Topcoder Marathon KnightsAndPawns

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=17225&pm=14994

焼きなましに飽きた1点をのぞけば、おもしろい問題だったと思います。

f:id:hakomof:20180731200014j:plain

方針

  1. 空のボードにナイトをごく少数ランダムに配置して初期状態とする。
  2. ナイト数を固定してペナルティ最小化の焼きなまし(SA)をする。近傍はナイト1つの移動だけで追加や削除はしない。
  3. ペナが0つまりvalidな状態に到達したら、ベストを更新して、その状態にナイトを1つランダムに追加して2に戻る。

例えば、
ナイト数100のvalidな状態をSAで求める。その状態にナイトを1つ追加して、
ナイト数101のvalidな状態をSAで求める。その状態にナイトを1つ追加して、
ナイト数102のvalidな状態をSAで求める…
これを時間いっぱい繰り返します。

この方針の優位性

方針に悩んだので、とりあえずナイト数とvalidが存在するかどうかの関係性を洗いました。雑なSAで調べました。それによると、あるX以下のナイト数はすべてvalidをつくれて、Xより大きいナイト数はすべてvalidをつくれないという綺麗な感じに分かれました。また、Xのvalidな最適解はわりと高速に求まったので、これは最適解を拾えるケースはきっちり拾えないと死にそうという印象になりました。(最終方針だとケースの半分強で最適解と思われるものが安定して出る)

これらを元に前述の方針を立てました。

メリット

  • ナイト数を1つずつ増やしながらvalid解を求めていくので、時間に余裕があれば安定して最適解が出る
  • SAのスコアが単なるペナなのでペナ方向のランダムウォークは理想的に行われる

デメリット

  • ナイト数を1つずつ増やしながらvalid解を求めていくので、収束が遅い。ですが、valid解にナイトを1つ追加した解つまりペナがとても少ない解からSAをはじめることでこのデメリットはかなり軽減される。
  • ナイト数を固定しているので、ナイト数方向のランダムウォークは皆無

他にもいくつか考えましたが、この方針が強そうだったので採用しました。

方針の続き

前述の方針そのままにさらに工夫を足します。

近傍を絞る

近傍はナイトを1つ動かす。ですが、ランダムなナイトをランダムな空きマスに動かすのではなく、

  • invalidなナイトをランダムな空きマスに動かす。
  • 攻撃されすぎなナイトを攻撃しているナイトを、ランダムな空きマスに動かす。
  • 攻撃されなさすぎなナイトを攻撃できる空きマスに、ランダムなナイトを動かす。

の3種類に絞ります。いずれもあるナイトのinvalidを解消する近傍です(たいていは別のマスにinvalidが移るだけですが)。SAはこのようなたとえスコアが下がっても部分的に改善する近傍だけが必要かつ十分なようで、それ以外の近傍を削ることが重要かつ頻出です。状態内のinvalidなナイトはとても少ないのでものすごい削られます。

毎試行必ず遷移するSA

普通のSAは近傍をランダムに選んで受理されたら遷移するので、試行回数×受理確率=遷移回数がパフォーマンスの目安になります。もし受理確率を100%にできたらもともとの受理確率が1%だとしたら100倍の高速化になります。今回の問題はこれができます(別途処理を追加するので10倍くらいの高速化(うろ覚え

このテク、過去のKnightsAttacksというコンテストで使ったのでそのときのツイートを流用します。(別にKnightがらみでなくてもこのテクは使ええます)

今回は黒赤青すべてのマスが変化するので41種類

今回は-16から+16の31通り

過去のコンテストのツイートバリバリ流用できるのほんと草生える

多スタート

局所にはまることはあるのでボードが小さいときは2回スタート

Example scores

Example scores:
0) 15.0
1) 1293.0
2) 3391.0
3) 1444.0
4) 1869.0
5) 173.0
6) 1415.0
7) 261.0
8) 230.0
9) 1499.0

f:id:hakomof:20180731195934j:plain f:id:hakomof:20180731200014j:plain f:id:hakomof:20180731200135j:plain f:id:hakomof:20180731200110j:plain f:id:hakomof:20180731200120j:plain f:id:hakomof:20180731200347j:plain f:id:hakomof:20180731200427j:plain f:id:hakomof:20180731200443j:plain

Topcoder Marathon Match 100 SameColorPairs

問題文

方針

私は焼きなまし厨なのでとりあえず焼きなましを考えます。

この問題の要求する解は消すペアとその順番です。その解そのものを(順番を含めて)直接焼きなますというのは難しそうです。なぜならあるペアを消すと新たにペアが消せるようになる、といった順序関係が強そうなので、順番を安易に変えると状態が壊れそうだからです。

そこで消すペアと順番を分けて考えてみます。消すペアの集合(消せる消せないにかかわらずすべてのマスをペアにしたもの)を固定したときの順番はどうなるでしょうか。これは以下のような簡単な貪欲で最適な順番、最適なスコアが求まります。

  1. 消せるペアを消す
  2. 新たに消せるペアが増えるのでそれも消す
  3. 1つも消せなくなるまで消す

なので、

  • 消すペアの集合を焼きなましの状態とする
  • 状態を少し変えたら、先の貪欲でスコア(差)を求めて遷移判定をする

とすれば焼きなましに帰着できました!

近傍

同じ色のペアを2つ選んでつなぎかえます。マスAとBを消すペアとマスCとDを消すペアを、ACを消すペアとBDを消すペアに変えるといった感じです。

状態に制限がなく、近傍も小さいのでうまく焼きなませそうです。

ですが、先の貪欲はめちゃくちゃ遅いのでまともにまわりません。なので収束速度の底上げ・高速化をしていきます。

盤面を分割して順に焼きなまします。探索空間が小さくなり収束が速くなることが期待されます。消すペアは近いことが多いので局所的な焼きなましはあまりデメリットになりませんでした。

盤面は1-27分割しますが最後の2ブロックだけ多スタートします。

近傍は、消せないペアか他のペアをたくさん囲っているペアの中から選びます。他のペアをたくさん囲っているペアというのは、囲われているペアが先に消えることを縛っていて、それがたくさんということは大局的に良い状態ではない可能性があります。なので変更の候補です。

近傍のつなぎかえ先は(広義)近いマスほど高確率で選ばれるようにします。

先の貪欲は次のような言い換えができます。消すペアを頂点として、ぺアXを消してからでないとペアYを消せないときXからYに有向辺を張った依存グラフを、閉路の手前までトポロジカルソートすると先の貪欲と同じ結果が得られます。消せるペアを探す手間が省ける分こっちのほうがたぶん速いです。

評価値は、消せるペア数 - 依存グラフの最小閉路の数 / 2.5です。閉路以下のペアはすべて死ぬので閉路の数をペナルティとすると探索空間がなだらかになってよさげです。

依存グラフは差分更新します。更新が必要な辺は、変更する2つのペアに入出する辺だけなので、グラフ全体を毎回つくりなおさなくていいです。

依存グラフを差分更新するにあたり、新しいペアを囲うペアを列挙する必要がありますが、愚直にすべてのペアを走査すると遅いので、バイナリ空間分割という衝突している物体の列挙を高速にするアルゴリズムを使います。囲われていることと衝突していることは同じことなので転用できます。

Yandex Algorithm 2018 Optimization track. Round 2 News freshness

問題文

暫定3位でした。険しい。問題自体はとてもおもしろかった。

greedy

巡回するサイトを1つずつ順番に決めていってパスをgreedyにつくります。パスがつくり途中だと2週目以降にいつどのサイトを訪れるかが定まらずスコアに加味できないので困ります。そこでパスの周期(timeToIndexの和)を決め打ちします。あらかじめ決めた周期(それ以外認めない)になるようにパスをつくることで、つくり途中でも2週目以降のスコアを計算できるようになります。

実装としては、最初は自由にパスを伸ばします。そして周期-150を切ったら、パスの後尾からランダムに伸ばして周期ジャストでパスの先頭に戻れるものの中からgreedyに1つ選ぶなどすると、だいたい成功します。

評価関数は、testerスコアの期待値 / すべてのパスのtimeToIndexの和としました。すべてのパスのtimeToIndexの和でわることで、timeToIndexあたりのスコアが高い効率のよいサイトが選ばれていきます。

あとはテキトーな周期で何回かgreedyしてmaxをとれば8600点以上が出ました。

周期

周期についていろいろ。

timeToIndexあたりのスコアがよいサイトばかりを選ぶとtimeToIndexが小さいので周期が短くなります。しかし周期が長いと週回数が少なくなり、1つのクローリングが影響する箇所が少なくなるのでよいスコアを得やすいです。短いことにも長いことにもメリットがあるので周期には短すぎず長すぎないベターな長さが存在します(実験によって確認)。

ベターな周期はすべてのサイトのtimeToIndexの和の45%-70%(5000-20000)ぐらいになるようです。またパス長は周期を長くするためにNギリギリであることが理想的ですがgreedyによって得られるパス長はNの65%-100%くらいになります。

ほどよい周期のパスをgreedyで得るために評価関数をtesterスコアの期待値 / pow(すべてのパスのtimeToIndexの和, timeCoef)に変えます。timeCoefが1に近いほど周期が短く、0に近いほど長くなります。timeCoefのよさげな値は3分探索で求めることができますがgreedy1回がとても重いのでやめました。timeCoefのよさげな値をローカルで時間をかけて求めて、testcaseパラメータと最小二乗法でえいっしたらこんな式に、

timeCoef = sqrt(S / (double)numberOfEdges) * -7.836528104606689 + 0.7974926014955707;

timeCoefは決まりましたが、そのtimeCoefに対応する周期は事前にわかりません。周期が長すぎるとパス長制限で構築に失敗しますし、短いほどスコアが悪くなります。なので2分探索で構築に失敗しない最大の周期を求めます。

ここまででよさげな周期を求めることができました。これで8700点ぐらい

周期には他にも着眼点があって、周期がtopicのfreqの倍数のときスコアがよくなります。というのも、そうであるときニュースの生成周期とクローリングの周期がそろうので、1週目で高スコアをとれれば、すべての周回で高スコア(同スコア)をとれるためです 。周期がずれてるとすべての周回で高スコアをとるのは難しくなります。

なのでいずれかのtopicのfreqの倍数であるような周期の中から2分探索すると8740点ぐらい

山登り

この問題はぱっと見山登り/焼きなましできない系に見えますができます。

timeToIndexの和が110程度の部分パスをランダムに選びます。そしてtimeToIndexの和が同じであるようにランダムに生成した部分パスと置換します。こういう近傍だと変更域以外の時間がずれないので山登り/焼きなましが有効ななだらかに近い探索空間になります。

greedyの結果を山登りして8790点ぐらい

入力バイナリから画像を作成するプログラムを公開しました

圧縮する入力バイナリは2次元のradianceのデータなようです。 このデータの画像はnetCDFデータのビューアから見ることができるようで、見るためにはnetCDFデータをビューアで開く、Rad行をダブルクリック、Create a 2D plotを選択します。

f:id:hakomof:20171216003749p:plain

とりあえず入力バイナリがどんなものか理解するために、入力バイナリから同じ画像を作成するプログラムを書きました。動作にはPython3、ライブラリPillowが必要です。(ソースコードはブログ最下部)

py script.py bin_4obs/OR_ABI-L1b-RadC-M3C01_G16_s20172101802185_e20172101804558_c20172101805000.bin

f:id:hakomof:20171216003715p:plain

これで画像が作成されます。色がぜんぜん違いますが、グラデーション色が違うだけでradianceはビューアと一致しています。

入力バイナリは、2次元を1次元につぶした2バイトのunsigned short?のradianceの基本値?が連続しているようです。この基本値にバンドごとに固有の定数(これはビューアからコピペしたので ミスってるかも)をかけて足すと、ビューアのradianceと一致しました。

というわけで適当にお役立てください。また、私はまったく詳しくない人なので間違っているかもしれないです(間違っていたら教えてください、そしてごめんなさい)。

from math import *
import os.path
import struct
import sys
from PIL import Image

def rgb(minimum, maximum, value):
    minimum, maximum = float(minimum), float(maximum)
    ratio = 2 * (value - minimum) / (maximum - minimum)
    b = int(max(0, 255 * (1 - ratio)))
    r = int(max(0, 255 * (ratio - 1)))
    g = 255 - b - r
    return r, g, b

all_scale_factor_and_add_offset = [
    (0.8121064, -25.936647),
    (0.15859237, -20.289911),
    (0.37691253, -12.037643),
    (0.07073108, -4.5223684),
    (0.09580004, -3.0596137),
    (0.030088475, -0.9609507),
    (0.001564351, -0.0376),
    (0.007104763, -0.5586),
    (0.022539102, -0.8236),
    (0.02004128, -0.9561),
    (0.03335779, -1.3022),
    (0.05443998, -1.5394),
    (0.04572892, -1.6443),
    (0.049492206, -1.7187),
    (0.05277411, -1.7558),
    (0.17605852, -5.2392),
]

file = sys.argv[1]
band = int(os.path.basename(file)[19:21])
scale_factor = all_scale_factor_and_add_offset[band - 1][0]
add_offset = all_scale_factor_and_add_offset[band - 1][1]
scale = int(sqrt(os.path.getsize(file) / 7500000))
width = 2500 * scale
height = 1500 * scale
radiances = [[0 for _ in range(width)] for _ in range(height)]
min_radiance = 1e9
max_radiance = -1e9
with open(file, 'rb') as f:
    for i in range(width * height):
        x = i % width
        y = i // width
        p = struct.unpack('H', f.read(2))[0]
        radiance = p * scale_factor + add_offset
        radiances[y][x] = radiance
        min_radiance = min(min_radiance, radiance)
        max_radiance = max(max_radiance, radiance)
image = Image.new('RGB', (width, height))
data = image.load()
for y, rs in enumerate(radiances):
    for x, r in enumerate(rs):
        data[x, y] = rgb(min_radiance, max_radiance, r)
image.save(file[:-3] + 'png')

北大日立マラソン第1回

Hokkaido Univ.& Hitachi 1st New-concept Computing Contest 2017 - AtCoder

スタートダッシュ芸人してました

初日

焼きなましはすぐにわかったので軽く高速化・温度調整したやつを出した(CodinGameにも出たかったので巻いてた(結局出なかったが

初日にやったこと

  • 初期解はランダム
  • 近傍は正の辺の端点をもう一点に隣接させる(隣接先が空ならMove、他の点があるならSwap)(他の人と同じ)
  • 近傍は一様ランダムセレクト
  • 温度は5度から1.5度に線形に下げる(12ケースで調整)
  • スコア変化量の計算は重みを32回足し引きすると思いますが、うち16回は事前に計算して持って遷移時に更新することで16回に減らせる

正の辺の端点をもう一点に隣接させる近傍なんですが、少なくとも一辺の得点がもらえるため、点のかたまりの遠くに飛ぶなどの明らかに無駄な近傍を除けて遷移効率が良くなります。こういう無駄な近傍を考えて除いたり、最適解ないし良い解を想像して、その形から離れるような近傍を除くというのは焼きなましではわりと頻出でとても効果が大きい。

その後

焼きなまし過程のVisualizerをつくった。赤がWeight=15、青がWeight=1、白線が近傍

f:id:hakomof:20171130175210g:plain

↑最初から最後までのダイジェスト(飛び飛び)。

  • 存外ふらふらするので初期解は中央にかためてランダム(壁にひっつくと遷移の自由度が下がって良くないので
  • 良い解は円に近そうに見える(正方形や長方形よりも円のほうが辺数が多いことは確認した(yowaさんのtweetによると正八角形が最大らしい?
  • 良い解は赤い(得点をもらえる辺はWeightが大きい辺に偏る)。ので近傍を一様ランダムセレクトではなく、round(sqrt(Weight))で重み付けランダムセレクトした

f:id:hakomof:20171130175401g:plain

↑真ん中らへんの遷移を連続で

  • 実際の遷移(白線)はかたまりの端と端が多い(かたまりの内側を動かすとスコアが大きく下がりやすく、焼きなましの遷移確率はスコアが大きく下がるときは低いのでそれはそう)。なのでこれをうまく使おうとしたけど難しかった。

その他

  • GCCよりClangのほうが1.25倍速かった
  • 他の人がやっているような高速化はだいたいやった
  • 温度を再調整

↓初日submit

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
#define U(v) cerr << #v << ": " << (v) << endl
 
constexpr int dx[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
constexpr int dy[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
 
class timer {
    vector<timer> timers;
    int n = 0;
public:
    double limit = 9.9;
    double t = 0;
    timer() {}
    timer(int size) : timers(size) {}
    bool elapses() const {
        return time() - t > limit;
    }
    void measure() {
        t = time() - t;
        ++n;
    }
    void measure(char id) {
        timers[id].measure();
    }
    void print() {
        if (n % 2)
            measure();
        for (int i = 0; i < 128; ++i) {
            if (timers[i].n)
                cerr << (char)i << ' ' << timers[i].t << 's' << endl;
        }
        cerr << "  " << t << 's' << endl;
    }
    static double time() {
#ifdef LOCAL
        return __rdtsc() / 3.3e9;
#else
        unsigned long long a, d;
        __asm__ volatile ("rdtsc" : "=a" (a), "=d" (d));
        return (d << 32 | a) / 2.8e9;
#endif
    }
} timer(128);
 
#include <ctime>
class {
    unsigned y = time(0);
    //unsigned y = 2463534242;
public:
    unsigned next() {
        return y ^= (y ^= (y ^= y << 13) >> 17) << 5;
    }
    int next(int b) {
        return next() % b;
    }
    int next(int a, int b) {
        return next(b - a) + a;
    }
    double nextDouble(double b = 1) {
        return b * next() / 4294967296.0;
    }
    double nextDouble(double a, double b) {
        return nextDouble(b - a) + a;
    }
    int operator() (int b) {
        return next(b);
    }
} rando;
 
struct P {
    int x, y;
    P() {}
    P(int x, int y) : x(x), y(y) {}
};
 
int V, E, S;
vector<pair<int, int>> edges;
char weight[501][501];
int vs[62][62];
char scores[501];
P ps[500];
P bestPs[500];
 
int eval() {
    int score = 0;
    for (auto& e : edges) {
        auto& a = ps[e.first];
        auto& b = ps[e.second];
        if (max(abs(a.x - b.x), abs(a.y - b.y)) == 1)
            score += weight[e.first][e.second];
    }
    return score;
}
 
void init() {
    vector<int> a;
    for (int i = 0; i < S * S; ++i)
        a.emplace_back(i);
    random_shuffle(a.begin(), a.end(), rando);
    for (int i = 0; i < V; ++i) {
        auto& p = ps[i];
        p.x = a[i] % S + 1;
        p.y = a[i] / S + 1;
        vs[p.y][p.x] = i;
    }
}
 
void solve() {
    init();
    copy_n(ps, V, bestPs);
    int score = eval();
    int bestScore = score;
    for (int i = 0; i < V; ++i) {
        auto& p = ps[i];
        for (int d = 0; d < 8; ++d)
            scores[i] += weight[i][vs[p.y + dy[d]][p.x + dx[d]]];
    }
    double heat = 0;
    for (int iter = -1; ; ) {
        if ((++iter & 0xfff) == 0) {
            //double p = 1 - iter / 100000000.0;
            double p = 1 - (timer.time() - timer.t) / timer.limit;
            if (p < 0) {
                U(iter);
                break;
            }
            constexpr double InitialHeat = 5;
            constexpr double FinalHeat = 1.5;
            heat = 1 / (p * (InitialHeat - FinalHeat) + FinalHeat);
        }
        int i, j, x, y;
        {
            unsigned r = rando.next();
            auto& e = edges[(r >> 4) % edges.size()];
            if (r & 8) {
                i = e.first;
                j = e.second;
            } else {
                j = e.first;
                i = e.second;
            }
            x = ps[j].x + dx[r & 7];
            y = ps[j].y + dy[r & 7];
            j = vs[y][x];
        }
        if (i == j || x == 0 || x == S + 1 || y == 0 || y == S + 1) continue;
        auto& p = ps[i];
        if (j == V) {
            int diff = - scores[i];
            for (int d = 0; d < 8; ++d)
                diff += weight[i][vs[y + dy[d]][x + dx[d]]];
            if (rando.nextDouble() < exp(diff * heat)) {
                score += diff;
                swap(vs[p.y][p.x], vs[y][x]);
                for (int d = 0; d < 8; ++d) {
                    int v = vs[p.y + dy[d]][p.x + dx[d]];
                    scores[v] -= weight[i][v];
                    v = vs[y + dy[d]][x + dx[d]];
                    scores[v] += weight[i][v];
                }
                scores[i] += diff;
                p = { x, y };
                if (bestScore < score) {
                    bestScore = score;
                    copy_n(ps, V, bestPs);
                }
            }
        } else {
            int diff = - scores[i] - scores[j];
            if (max(abs(x - p.x), abs(y - p.y)) == 1)
                diff += weight[i][j];
            vs[p.y][p.x] = vs[y][x] = V;
            for (int d = 0; d < 8; ++d)
                diff += weight[j][vs[p.y + dy[d]][p.x + dx[d]]];
            vs[p.y][p.x] = j;
            for (int d = 0; d < 8; ++d)
                diff += weight[i][vs[y + dy[d]][x + dx[d]]];
            vs[y][x] = i;
            if (rando.nextDouble() < exp(diff * heat)) {
                score += diff;
                for (int d = 0; d < 8; ++d) {
                    int v = vs[p.y + dy[d]][p.x + dx[d]];
                    scores[v] -= weight[i][v] - weight[j][v];
                    v = vs[y + dy[d]][x + dx[d]];
                    scores[v] += weight[i][v] - weight[j][v];
                }
                scores[i] = scores[j] = 0;
                for (int d = 0; d < 8; ++d) {
                    scores[i] += weight[i][vs[y + dy[d]][x + dx[d]]];
                    scores[j] += weight[j][vs[p.y + dy[d]][p.x + dx[d]]];
                }
                swap(p, ps[j]);
                if (bestScore < score) {
                    bestScore = score;
                    copy_n(ps, V, bestPs);
                }
            } else {
                swap(vs[p.y][p.x], vs[y][x]);
            }
        }
    }
    copy_n(bestPs, V, ps);
    timer.print();
}
 
int main() {
    timer.measure();
#ifdef LOCAL
    int type, seed;
    cin >> type >> seed;
#endif
    cin >> V >> E;
    for (int i = 0; i < E; ++i) {
        int a, b, w;
        cin >> a >> b >> w;
        --a;
        --b;
        if (w != 0) {
            edges.emplace_back(a, b);
            weight[a][b] = weight[b][a] = w;
        }
    }
    cin >> S;
    S = (int)sqrt(S);
    {
        int E;
        cin >> E;
        for (int i = 0; i < E; ++i) {
            int a, b;
            cin >> a >> b;
        }
    }
    for (int i = 0; i < S + 2; ++i)
        fill_n(vs[i], S + 2, V);
    solve();
    //cerr << "var d" << type * 6 + seed << " = [" << endl;
    //cerr << "[" << V << ',' << edges.size() << ',' << S << "]," << endl;
    //cerr << "[";
    //for (auto& e : edges)
    //    cerr << e.first << ',' << e.second << ',' << (int)weight[e.first][e.second] << ',';
    //cerr << "]," << endl;
    //cerr << "[";
    //for (int i = 0; i < V; ++i)
    //    cerr << i << ',' << ps[i].x << ',' << ps[i].y << ',';
    //cerr << "]," << endl;
    //cerr << "]" << endl;
#ifdef LOCAL
    int score = 0;
    int esum = 0;
    int wsum = 0;
    for (auto& e : edges) {
        auto& a = ps[e.first];
        auto& b = ps[e.second];
        if (max(abs(a.x - b.x), abs(a.y - b.y)) == 1) {
            score += weight[e.first][e.second];
            ++esum;
        }
        wsum += weight[e.first][e.second];
    }
    cerr << type * 6 + seed << "\t" << score << "\t" << wsum << "\t" << esum << "\t" << edges.size() << "\t" << V << "\t" << S << endl;
#else
    for (int i = 0; i < V; ++i) {
        auto& p = ps[i];
        cout << i + 1 << ' ' << (p.y - 1) * S + p.x << endl;
    }
#endif
    return 0;
}

↓最終submit

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
#define U(v) cerr << #v << ": " << (v) << endl
 
constexpr int dx[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
constexpr int dy[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
 
class timer {
    vector<timer> timers;
    int n = 0;
public:
    double limit = 9.95;
    double t = 0;
    timer() {}
    timer(int size) : timers(size) {}
    bool elapses() const {
        return time() - t > limit;
    }
    void measure() {
        t = time() - t;
        ++n;
    }
    void measure(char id) {
        timers[id].measure();
    }
    void print() {
        if (n % 2)
            measure();
        for (int i = 0; i < 128; ++i) {
            if (timers[i].n)
                cerr << (char)i << ' ' << timers[i].t << 's' << endl;
        }
        cerr << "  " << t << 's' << endl;
    }
    static double time() {
#ifdef LOCAL
        return __rdtsc() / 3.3e9;
#else
        unsigned long long a, d;
        __asm__ volatile ("rdtsc" : "=a" (a), "=d" (d));
        return (d << 32 | a) / 2.8e9;
#endif
    }
} timer(128);
 
#include <ctime>
class {
    unsigned y = time(0);
    //unsigned y = 2463534242;
public:
    unsigned next() {
        return y ^= (y ^= (y ^= y << 13) >> 17) << 5;
    }
    int next(int b) {
        return next() % b;
    }
    int next(int a, int b) {
        return next(b - a) + a;
    }
    double nextDouble(double b = 1) {
        return b * next() / 4294967296.0;
    }
    double nextDouble(double a, double b) {
        return nextDouble(b - a) + a;
    }
    int operator() (int b) {
        return next(b);
    }
} rando;
 
struct P {
    int x, y;
    char score;
    P() {}
    P(int x, int y) : x(x), y(y) {}
};
 
int V, E, S;
int neighborsSize;
pair<pair<short, short>, pair<char, char>> neighbors[20000 * 64];
vector<pair<short, short>> edges;
char weight[501][501];
short vs[62][62];
P ps[501];
P bestPs[501];
 
int eval() {
    int score = 0;
    for (auto& e : edges) {
        auto& a = ps[e.first];
        auto& b = ps[e.second];
        if (max(abs(a.x - b.x), abs(a.y - b.y)) == 1)
            score += weight[e.first][e.second];
    }
    return score;
}
 
void init() {
    vector<int> a(S * S);
    for (int i = 0; i < S * S; ++i)
        a[i] = i;
    sort(a.begin(), a.end(), [](int i, int j) {
        return max(abs(i % S - (S - 1) / 2.0), abs(i / S - (S - 1) / 2.0))
            < max(abs(j % S - (S - 1) / 2.0), abs(j / S - (S - 1) / 2.0));
    });
    random_shuffle(a.begin(), a.begin() + V, rando);
    for (int i = 0; i < S + 2; ++i)
        fill_n(vs[i], S + 2, V);
    for (int i = 0; i < V; ++i) {
        auto& p = ps[i];
        p = { a[i] % S + 1, a[i] / S + 1 };
        vs[p.y][p.x] = i;
    }
    for (int i = 0; i < V; ++i) {
        auto& p = ps[i];
        p.score = 0;
        for (int d = 0; d < 8; ++d)
            p.score += weight[i][vs[p.y + dy[d]][p.x + dx[d]]];
    }
}
 
void solve() {
    init();
    copy_n(ps, V, bestPs);
    int score = eval();
    int bestScore = score;
    int ni = -1;
    const double InitialHeat = edges.size() / (double)V < 3 ? 2.5 : V <= 200 ? 3.5 : 5;
    const double FinalHeat = edges.size() / (double)V < 3 ? 0.5 : 2;
    double heat = 0;
    for (int iter = -1; ; ) {
        if ((++iter & 0xffff) == 0) {
            //double p = 1 - iter / 200000000.0;
            double p = 1 - (timer.time() - timer.t) / timer.limit;
            if (p < 0) {
                U(iter);
                break;
            }
            heat = 1 / (p * (InitialHeat - FinalHeat) + FinalHeat);
        }
        short i, j;
        unsigned x, y;
        {
            if (++ni == neighborsSize) ni = 0;
            auto& n = neighbors[ni];
            i = n.first.first;
            j = n.first.second;
            x = ps[j].x + n.second.first;
            y = ps[j].y + n.second.second;
            j = vs[y][x];
        }
        if (i == j || max(x - 1, y - 1) >= (unsigned)S) continue; 
        auto& p = ps[i];
        if (j == V) {
            int diff = - ps[i].score;
            for (int d = 0; d < 8; ++d)
                diff += weight[i][vs[y + dy[d]][x + dx[d]]];
            if (rando.nextDouble() < exp(diff * heat)) {
                score += diff;
                swap(vs[p.y][p.x], vs[y][x]);
                for (int d = 0; d < 8; ++d) {
                    short v = vs[p.y + dy[d]][p.x + dx[d]];
                    ps[v].score -= weight[i][v];
                    v = vs[y + dy[d]][x + dx[d]];
                    ps[v].score += weight[i][v];
                }
                p.score += diff;
                p.x = x;
                p.y = y;
                if (bestScore < score) {
                    bestScore = score;
                    copy_n(ps, V, bestPs);
                }
            }
        } else {
            vs[p.y][p.x] = j;
            vs[y][x] = i;
            int diff = - ps[i].score - ps[j].score;
            for (int d = 0; d < 8; ++d)
                diff += weight[j][vs[p.y + dy[d]][p.x + dx[d]]];
            for (int d = 0; d < 8; ++d)
                diff += weight[i][vs[y + dy[d]][x + dx[d]]];
            if (rando.nextDouble() < exp(diff * heat)) {
                score += diff;
                for (int d = 0; d < 8; ++d) {
                    short v = vs[p.y + dy[d]][p.x + dx[d]];
                    ps[v].score -= weight[i][v] - weight[j][v];
                    v = vs[y + dy[d]][x + dx[d]];
                    ps[v].score += weight[i][v] - weight[j][v];
                }
                ps[i].score = ps[j].score = 0;
                for (int d = 0; d < 8; ++d) {
                    ps[i].score += weight[i][vs[y + dy[d]][x + dx[d]]];
                    ps[j].score += weight[j][vs[p.y + dy[d]][p.x + dx[d]]];
                }
                swap(p.x, ps[j].x);
                swap(p.y, ps[j].y);
                if (bestScore < score) {
                    bestScore = score;
                    copy_n(ps, V, bestPs);
                }
            } else {
                vs[p.y][p.x] = i;
                vs[y][x] = j;
            }
        }
    }
    copy_n(bestPs, V, ps);
    //timer.print();
}
 
int main() {
    timer.measure();
#ifdef LOCAL
    int type, seed;
    cin >> type >> seed;
#endif
    cin >> V >> E;
    for (int i = 0; i < E; ++i) {
        int a, b, w;
        cin >> a >> b >> w;
        --a;
        --b;
        if (w != 0) {
            edges.emplace_back(a, b);
            for (int i = 0; i < (int)round(sqrt(w)); ++i) {
                for (int d = 0; d < 8; ++d) {
                    neighbors[neighborsSize++] = { { a, b }, { (char)dx[d], (char)dy[d] } };
                    neighbors[neighborsSize++] = { { b, a }, { (char)dx[d], (char)dy[d] } };
                }
            }
            weight[a][b] = weight[b][a] = w;
        }
    }
    random_shuffle(neighbors, neighbors + neighborsSize, rando);
    cin >> S;
    S = (int)sqrt(S);
    {
        int E;
        cin >> E;
        for (int i = 0; i < E; ++i) {
            int a, b;
            cin >> a >> b;
        }
    }
    solve();
#ifdef LOCAL
    int score = 0;
    int esum = 0;
    int wsum = 0;
    for (auto& e : edges) {
        auto& a = ps[e.first];
        auto& b = ps[e.second];
        if (max(abs(a.x - b.x), abs(a.y - b.y)) == 1) {
            score += weight[e.first][e.second];
            ++esum;
        }
        wsum += weight[e.first][e.second];
    }
    cerr << type * 500 + seed << "\t" << score << "\t" << wsum << "\t" << esum << "\t" << edges.size() << "\t" << V << "\t" << S << endl;
#else
    for (int i = 0; i < V; ++i) {
        auto& p = ps[i];
        cout << i + 1 << ' ' << (p.y - 1) * S + p.x << endl;
    }
#endif
    return 0;
}