Topcoder の Marathon Match 127 に出走しました。
問題はCarRacing。インタラクティブな、ソート手順を短縮する問題です。
事前テストは62人中3位、システス結果は2位でした。
レート：2039(黄)→2229(赤)
問題
N台の車があり、これらの速度は車ごとに別々の値で固定です。
K台ずつレースさせて、その結果を順位だけ知ることができます。
より少ないレース数で、全ての車を速い順に並べてください。
考察
やることはソート。
既存のソートアルゴリズムを使うなら、クイックソート（＋選択ソート）が良さそう。選択ソートは上位n個の選択、クイックソートはpivot n個によるn+1分割とすると、(基準となる車の数 n) * (基準と比べる車の数)で二重に並列化出来るので効率が良い。*1
これらのアルゴリズムではKが2→4になると基準値との比較を+2回可能(効率3倍)ということになるが、実際にはAB,AC,AD,BC,BD,CDで6組という風に、総当たりでより多くの組の大小関係を比較することが出来る。(効率6倍)
また、AがBより速い場合、[A,Aより速い車の全て]は[B,Bより遅い車の全て]より速いと言える。この点を踏まえて、どのK個を組み合わせると最も情報が増えるかという観点で出走する車を選ぶのが良さそう。下手にやると計算量が爆発するし、オーダーも安定しないので難しい。
最終的にやったこと
全体方針
クイックソートでざっくり振り分けた後、考察後半の方法でソート(便宜上、関係性ソートと呼ぶ)して順位を確定させた。
構造としては、木構造で分割統治。
クイックソート
選択ソートの処理コストを基準として、台数が少ない方からDPで処理コストを求め、そこからクイックソートの最適なpivot数を決定した。
選択ソートなんて使っていないので、根拠の無い値になっている…。*2
関係性ソート
これは固定のロジックがあるソートアルゴリズムではなく、確定情報による順位確定をするために出走管理を行うロジック。出走する車は貪欲で以下のルールで選んだ。
・グループ内の既に大小関係がついている車の数ごとに1ペナルティ
・既に大小関係がついている車と同時出走するたびに10ペナルティ
・既に出走決定した車の平均期待順位と離れるほどペナルティ(0～グループ内の台数)
やったこと時系列
・サンプル確認(0.4点)
車2台だけ使う選択ソートらしい。
クイックソート＋選択ソートを目標にして、ボトムアップで選択ソートから作るかな。
・K台出走する選択ソート(2点)
・上位n台を抽出する選択ソート(20点)
O(N^2)だからこんなもんかな。（震え声）
・pivotが1件のクイックソート(50点)
・pivotがn件のクイックソート(75点)
この辺に人が固まっていて、多分みんな同じ方針かな。
・既についた大小関係で分割可能ならする(80点)
・余った幅で他のグループのソートもできるように(80点)
・選択ソートを関係性ソートに差し替え(85点)
グループ（分割統治）の単位で出走させていたので、枠が余るともったいない。複数グループを同時に出走できるようにした。
また、大小関係の情報保持を、グループ内の最小や最大が運良く判明したら嬉しいな、くらいの気持ちで始める。しかしここで、基準値を使わずに要素同士で大小関係を付け合った方が効率が良いことに気づく。
ここから深い闇へ。
・各種調整(89点)
大小関係は連鎖的に増えていくので、より効率の良い手順を模索。
情報が少ない車同士で出走したり、(1,2) > (3,4,5) > (6, 7) のような複数台の大小確定情報も利用できるようにしたり。
しかしこの辺りは手順数が多いものを短縮できても、元々手順数の少ないものはほぼ短縮できず、絶対スコアは改善しても相対スコアがあまり変わらなかった。
・期待順位が近いやつ同士で出走(94点)
これがかなり大きかった。何故これが効くかというと、どちらが勝ってもその上位/下位にいる車の情報を与えることができるため。期待順位が離れていると、高確率で1対1の分しか情報が増えないということもある。
実装方法がなかなか浮かばなかったが、自分より速い車の数、遅い車の数から上位何%くらいにいるかあたりを付けて、出走する車がこの全台平均から離れるとペナルティを付けるようにした。
ここでコンテスト終了。
ビジュアライザ関連
MM127はビジュアライザが無かったので、開催中または終了後にビジュアライザを作る人がいたようです。
もおあきさん
総当たり
エスケープシーケンスで対戦表を表示してたんだけど、スマホにC++コンパイラ入れたらそのまま動きました。これでいつでもどこでもマラソン出来る！？（危険なのでオススメはしない） pic.twitter.com/3db8kpKYLQ
— もおあき (@moooaki) 2021年6月17日
yowaさん
@yowa マージソート風: 長さKの列に分割→それぞれをソート→順位確定してないヤツを小さい方からK個選んでソート pic.twitter.com/cqNbC3OxYQ
— yowa (@yowa) 2021年6月17日
MM 127、勝敗表の埋まる様子を動画にしてみた。緑が勝ち、赤が負け。灰色は未対戦（白に近いほど予想勝率が高い）。見やすいように真の順位でソートして表示。 pic.twitter.com/YcQDl0UsxW
— yowa (@yowa) 2021年6月19日
私
クイックソート、総当たり
pivot複数版（9位と13位で3分割） pic.twitter.com/uquKEHjqdV
— いなにわ (@inani_waon) 2021年6月19日
感想
コンセプトはソートというシンプルな題材なものの、複数の車同士に大小関係が付いたり、並列化のような処理を書いたりとなかなかにハードで面白かったです。複数のソートアルゴリズムを操るということでinterfaceも使ってみたけど、マラソンでinterfaceを使ったのは初めてじゃないかな…。*3
ビジュアライザが無いのに加えて、車の数が多く情報が複雑なので、考察＆デバッグは大変でした。結構ゴリゴリの実装コンテストだったのでは？
終盤の見通しを立てて上手く設計するというのも時には必要になりそうですね。
