この記事は Jij Inc. Advent Calendar 2023 の 19 日目の記事です．
はじめまして．Jij Inc. の坂井です．
Topcoder Marathon Match 150 にザックリ参加した体験をザックリまとめます．
この記事の執筆時点 (12/18 午後) ではまだ 1 回も提出していないので凄惨な結果になりそうですが，強くない参加者の思考・行動パターンとしてザックリ読んでいただけたら幸いです．
問題
-
N \times N C - グリッド上には
C N - グリッド上には壁も配置され，クイーンは壁や他のクイーンが置かれたセルを通過できない．
- クイーンを動かして，同色のクイーンが同じ行，列，斜め方向にできるだけ並ばないようにしたい．
- 具体的には，ある行か列か斜め方向に同色のクイーンが
n N \times {}_{n}C_{2}
- 具体的には，ある行か列か斜め方向に同色のクイーンが
- また，クイーンの移動にもペナルティがかかり，セル
(r_{1},c_{1}) (r_{2},c_{2}) \sqrt{\max(|r_{1}-r_{2}|, |c_{1}-c_{2}|)} - 合計のペナルティが最小になるようにクイーンを動かす．
-
2N^{3}
-
考えたこと (時系列)
12/12 (火)
3:00
アドベントカレンダーの題材の候補と思っていたので，公開と同時に問題を見る．
各クイーンの目的地を乱択に決めてから順番に放り込んでいくというシンプルな作戦をまず試そうと思った．
12/13 (水)
良い日だった．
12/14 (木)
何気なく順位表を見たら 1 位の方が 90 点台で 2 位の方が 75 点だった．
この得点は全ての問題シードに渡って (その問題で出ている最小スコア)/(自分のスコア) の和をとって規格化した相対スコアである．
12/15 (金)
良い日だった．
12/16 (土)
0:00
あと 3 日である．やるしかない．
とりあえず各クイーンの目的地を乱択的に決めることを試みる．
ここで注意するべきなのは，同色のクイーンが利き合っていることにではなく，あくまで同じ列，行，斜め方向に存在することがペナルティになるということだ．
各行・列・斜め方向に対して同じ色のクイーンがいくつあるかということを各色について覚えておいて，問題ママのエラーペナルティを最小化することを試みた．
移動ペナルティについても考えておくと，これは盤上の端から端まで，角から角まで移動しても
その一方で，エラーペナルティはクイーンを 2 個並んでいる中から 1 つ除くと
したがって，
また，あるクイーンを同じ場所に動かすのでも移動ペナルティは盤面の状況で大きく変わるので，これを SA 中に考慮するのは難しく思われた．
なので移動ペナルティの優先度はあまり高くなかったが，とりあえずあるクイーンを別のある場所に移すためのペナルティは 2 点間の Manhattan 距離の平方根くらいでザックリ近似することにした．
これはあってもなくても変わらないかもしれないと思っていたが，なくすと到達の難しい盤面ができやすくなってしまったので入れることにした．
15:30
以上の考え方で SA したら，seed 1 (
一方で，seed 2 (
クイーンを選んで初期位置に関係なくどこにでも置いて良いようにすると 10 組くらいに減らせたが，到達不可能な場所に置いてしまいそうだったのでやめた．
19:30
SA は一旦置き，クイーンを次々目的地に放り込む部分を作りはじめる．
処理するクイーンの順番によって得をしたり損をしたりするはずである．
このような問題はいっぱいありそうだが，自分はなんとなく実際に参加した TCO19 MM Round 3 を思い出した．
これは特殊な移動ルールがある駒をそれぞれ目的地に動かす問題で，自分は処理順をシャッフルして試すことを時間いっぱい繰り返すというヤケクソなものを提出した記憶がある．
上記の SA で決めた目的地がどれだけ実現の難しい盤面になっているか見たかったので，とりあえず左上から順番にクイーンを選んで目的地に動かすという実験をすると，seed によらず意外と 8 割くらいのクイーンは目的地に行けた．
クイーンは斜め移動ができるので到達力が高い．
12/17 (日)
16:30
(自分は 1 回も提出していないのに) なんとなく順位表を見たら 6.12831 点で 4 人縮退している (1 位は 95.66062 点) ので，サンプルコードを投げたらその点になるのだろうと分かる．
(他に考えるべきことが多くあるはずだが，) 全てのクイーンを目的地に渡すためには邪魔なクイーンを退かして目当てのクイーンを通すということも必要なのだろうかと思いはじめた．
それを狙って行なうのは難しいので，クイーンたちを目的地に動かしはじめる前にグリッドの連結性を上げるための処理をしても良いかもしれないと思った．
たとえば縦か横に隣接しているクイーンやブロックの数を最小化すると，盤面はチェッカーボードに近い感じになる．
縦横に X ステップ移動するのと斜めに X ステップ移動するのは移動ペナルティは同じだが後者の方が距離的には得なので，斜め移動を強いつつ連結性が上がるような上記の変形は利益が大きいかもしれないという発想である．
これは結局試す時間がなかった．
20:00
valid な解が出るようになったからテスターを見始める．
テスターは見栄えが良くて何が起きているか分かりやすいが，意味もなく見惚れて時間が流れたりするので適切に使うべきである．
ここで，移動ペナルティよりもエラーペナルティの方が大きい解がよく出ていることに気付いた．
上述のように，エラーペナルティを 1 準位減らすために少なくとも
つまり，エラーペナルティと移動ペナルティが同じくらいの大きさになるまでは積極的にクイーンを動かして良いはずである．
順番をシャッフルし続けるだけでは限界があるかもしれないと思い，移動パートの改善を始める．
最終的に，「次に目的地に移動させるクイーン」を複数試し，良いものを上位いくつかだけ残してまた次のクイーンを選ぶという考えに落ち着いた．
12/18 (月)
13:00
最終日である．
クイーンを目的地に動かすパートの改善が思い付かなかったので，目的地を決めるパートのコスト関数を改めて考えはじめる．
初期位置から一〜二発で移動できる場所に加点する等考えていたが，試すには至らなかった．
この時点で未提出で，競うというよりは完走を目指した営みになっている．(走る方のマラソンもそうやって楽しむ人が多い．)
この時点でローカルで動かした seed 1 から 10 のスコアは以下のようになる．低いほど良い．
| seed | サンプルコード | 順番シャッフル | 最終 |
|---|---|---|---|
| 1 | 220.0 | 27.095647359318303 | 24.21075947218795 |
| 2 | 8060.0 | 1664.195384608476 | 1013.597289797381 |
| 3 | 911.0 | 72.86977332395305 | 69.3708794657963 |
| 4 | 1644.0 | 76.04127316263003 | 69.48371029566187 |
| 5 | 5648.0 | 406.9586017008212 | 383.2077431678649 |
| 6 | 2015.0 | 308.5603324312002 | 255.2577268706432 |
| 7 | 1978.0 | 216.17249123630833 | 202.1325632940000 |
| 8 | 628.0 | 53.339286873363164 | 47.52786293665145 |
| 9 | 3745.0 | 466.4381347638413 | 463.5514480550459 |
| 10 | 3779.0 | 609.1289019549808 | 411.3935893207731 |
18:00
順位表を見たら 1 位の方が 99.4 点を出していた．
とりあえず提出してみたら構造化束縛が使えずエラーになった．
(サーバでは g++ --std=gnu++11 -O3 でコンパイルされる．)
修正して再アップロードすると 34 点で 24/53 位ということで，動いたことを祝福しようという気になった．
23:00
根本的に正しい方を向いていないかもしれないということは置いておくと，改善できそうなところは目的地に辿り着けなかったクイーンたちの扱いである．
現行の実装では目的地に到達不可能だったクイーンは初期位置でじっとしていることになっているので，最後にこれらをマシな位置に動かすということを試みても良い．
12/19 (火)
3:00
3:01 くらいまで提出ボタンが開いていたが，3:00 以降に提出した方はいなかった．
自分は結局時間やメモリをオーバーしないことのチェックと微調整だけして再提出し，38 点に微妙に伸びた．
4:55
フォーラムに「Post your approach」というスレッドが立ったことでこの記事を投稿して良いことを確認した．
結果
- seed 2 (
N=30 C=6 - ビジュアライザは公式から提供されている．ファンシーなビジュアライザを自作している方たちもいる．
- 最終盤面ではエラーペナルティは
18 \times 30
- 最初に思っていたことはできているが，早々提出して他の方針も検討するということをするべきである．
感想
- 振るわなかったがまた出たい．
- N クイーン問題はよく研究されているが，ヒントを得る目的でそういうものを勉強しても良かった．
- 一部不可能な問題があるのは別として，他の方はエラーペナルティがゼロな盤面を作れていたのだろうか．
- 今回のように上位と大きな差があるときは別のゲームをやってしまっている可能性が高いように思う．
- 皆さんの解法を見るのが楽しみである．
- 目的の盤面は乱択で構築する必要がないような気がしている．
- 知っているパターンに最初から当てはめて考えるより，問題をより良く読解する努力をしようと思った．
- 上の「考えたこと」の大部分が主観に基いているが，本当は短い開発サイクルでデータを見ながら考えていくべきことである．
- 日常生活でもよくある反省である．
募集
最後に
＼Rustエンジニア・数理最適化エンジニア募集中！／
株式会社Jijでは、数学や物理学のバックグラウンドを活かし、量子計算と数理最適化のフロンティアで活躍するRustエンジニア、数理最適化エンジニアを募集しています！
詳細は下記のリンクからご覧ください。皆さんのご応募をお待ちしております！
Rustエンジニア: https://open.talentio.com/r/1/c/j-ij.com/pages/51062
数理最適化エンジニア: https://open.talentio.com/r/1/c/j-ij.com/pages/75132
ところで，Topcoder Marathon Match では Rust は使えない．
Discussion