参加しながら考えたこと試したことの源泉かけ流し。
最終的な方針は まとめ にまとめてあります。
問題概要
https://www.topcoder.com/challenges/43ad7e8d-8d90-4404-8a34-d1d36012a51c?tab=details
N 台の車があり、それぞれの車には distinct な速度が設定されている。あなたは最大 K 台の車を選びそれらを走らせ、速度の順序関係を調べることができる。できるだけ少ない比較回数ですべての車の速度の順序関係を特定せよ。
1 日目
問題を読む。かなりシンプル…というかこれシンプルすぎないか！？あまりにシンプルすぎて先行研究とかありそうだが…と思いながら「topological sort online」とかでググるもさすがに同じような問題設定のものは見つからず（さすがに topcoder をナメ過ぎか）。"Online Topological Ordering" とやらに関する研究は結構見つかるけど、これは順序関係の情報が順番にやってくる場合にどうトポソするかの話であって、どの順序関係を調べるかという今回の問題とは直接の関係はなさそう。トポソ部分を高速化したくなったりしたら読んでみるのもありかもしれない。
とりあえず解法について考えてみる。
- ベースはやはりクイックソート？
- どれか一つの車について他の車との順序関係を全て調べて、それより遅いやつと速いやつの 2 グループに対し再帰的に同じことをやる。
- ピボットの車として集団の端っこに位置する車を選んでしまうと後々比較回数が多くなっちゃいそうなので、適度に真ん中くらいの車をピボットとして選んであげたい。
- K が十分に大きければ、一度適当な車を選んで比較したあと、その中心に位置した車をピボットとして採用するということができそう。
- K が小さいときは、適当にピボットを選んだあと何回か比較を進めて、あまりにダメそうだったら変更？
- ピボットの選び方についてググって median of medians という概念を知った。これに則って K2 個の中から median of medians を選ぶというのも良いかもしれない。
- K が偶数（特に K=2）のときは…？
- マージソートは？
- ソートアルゴリズムに基づかない方法は？
- 具体的な方法はパッと思いつかないが、ここの K 個の比較したら順序関係が一番クリアになっていきそうみたいなのを計算する？
- クイックソートベースが K 個の車の順序関係を一発で特定できるポテンシャルを持ってるのと比べると、どうしても不利に見える。
- 小さいケースは少しの差が命取り。詰めきれる？
ひとまずこんなところか。
まずは直感に従ってクイックソートベースのアルゴリズムを実装してみる。
一発でバグなく動いた。こわ。
さておき、N=6, K=2 の seed=1 を 9 回のクエリでソートできてるので、選択ソートよりは優秀らしい。それはそう。
後はピボットの選び方の工夫かな。今は適当に先頭の車をピボットにしてたけど、「一度適当な車を選んで比較したあと、その中心に位置した車をピボットとして採用する」をやってみる。
引くほど改善された…。前は 100 回以内でソート完了してるのなんか 7% くらいだったのが、8 割方 100 回以内で終わるようになった。ほげ〜。
ソートアルゴリズムって知識としては当然知ってるんだけど、実際書いてみてこうしたら速くなるね〜みたいなのはやったことなかったので、これは結構楽しいかもしれない。
seed=1~100 での最悪ケースは seed=74 の N=899, K=4 でスコアは 2846。うーん、いつもは 100 ケースくらいで雑にスコア見てるんだけど、ちょっと K=2 のケースが少ないのでもうちょっと多めのケースで試すようにするか。
で、seed=500 まで見て K=2 のケースが 11 個。まぁ当然小さい K ほどレアなんだけど、思ったより少ないな。K=2 のケースについては余裕があったら別途考えるくらいで良いかも。
ところでマージソートの場合は K=2 のケースの比較回数がかなりちゃんと出せるはずで、例えば seed=402 の N=554 のケースだと… 4770 回くらい？多分…。今のクイックソートが 5144 回なのでピボットの選び方工夫すればマージソートの勝ち目はなさそうだな。クイックと呼ばれるだけのことはあるなあ。
まぁぼちぼち良さそうなスコアに見えるし様子見で提出してみる。52.47388。52.47388！？思ったより渋いな…。
トップが 84 点とかだから、K が小さいケースを改善しなきゃとかじゃなく、全体的に改善する必要がありそうだなあ。ふーむ。
ピボットとの比較を行う際、ピボット以外の車のペアについてもついでに順序関係が分かるので、この情報は活かしたい。
ひとまずピボットとの比較をする際、それより以前にそのペアについて順序関係が明らかになっていた場合は新たに比較するのを端折るようにして、お気持ち程度改善した。
…ああいや、そのペアについて直接比較が行われていなくても、トポソ的に順序関係を繋げば分かることも増えるはずで、ピボットとの比較はもっとサボれそうだな。
あとピボットとの比較を始める前にソート前の車の id 列をランダムに並べ替えておけば、既に比較済みの id たちが全体にバラけて、再度直接比較される回数が減って嬉しそう。
ど深夜なので実装はまた明日。
2 日目
マージソートについて思いを馳せてたんだけど、やっぱりアルゴリズムの仕組み上既に比較済みのペアを何度も比較することになるので、改めて若干弱い気がするということを思った。
で、クイックソートの改良だけど、昨日の最後のアイデアは一旦置いといて、K がデカいケースではピボットを 2 個以上用意してあげて、分割数を増やすという手はどうだろう？ 2 分割した後またそれぞれでピボットを決めて全なめする必要があるのだから、それなら分割前に複数個のピボット使ってまとめて全なめした方がお得だよねと。これなら大多数のケースで改善が期待できそうな気がする。
とりあえず K >= 10 なら 3 分割、そうでないならそのまま 2 分割でやってみる。
うん、しっかり全体的に改善した。期待を込めて submit。61.46804。ほえ〜。
よく考えたら 1.5*K 個くらいの車を 3 分割するのは無駄なので、そこらへんを調整しつつ最大 7 分割までやるようにしてみたらまた結構良くなった。submit。73.98255。あ、これパラメータ調整中の最大 5 分割のやつ間違って出しちゃってるな…伸びてはいるけど。提出制限無いから気が緩んでいる。
最大 7 分割を提出し直して 78.32872。いいですね。
小さい K のときたくさん分割しすぎないように、分割数が K/3 を超えないよう調整した。78.75268。今日のところは満足。今暫定 9 位なので T シャツ貰うためにも今の順位をキープできるよう踏ん張っていきたい。
3 日目
K = 2 の場合くらい先行研究ないかな〜と思いながら "sort comparison minimum" とかでググってたら「sleep sort なら比較回数ゼロだよ」みたいな意見を見つけて不覚にも笑ってしまった。
どんな具合に分割されてるのか見てみたかったので、雑に出力してみる。
N=306 K=20
-> 306
-> 46
-> 13
-> 10
-> 21
-> 10
-> 10
-> 62
-> 16
-> 17
-> 11
-> 15
-> 8
-> 50
-> 15
-> 9
-> 10
-> 13
-> 40
-> 9
-> 14
-> 15
-> 95
-> 12
-> 3
-> 16
-> 21
-> 10
-> 10
-> 20
-> 18
結構良い感じに見える。
パラメータ調整（最大 7 分割 -> 最大 9 分割）をして 76.53462 -> 78.59139。最大 15 分割で 79.01888。
上のビジュアライズ結果を眺めていると、K=20 で 21 個の車を 10, 10 に分割してるところはもう少し改善できるような気がしてきた。これだと分割に 2 回、分割後のもののソートで 2 回の計 4 回比較してるわけだけど、分解せずとも適当に 20 個比較して、そのうち連続する 19 個と残りの 1 個を比較すればほぼほぼ 2 回、運が悪くても 3 回で順序関係は特定できるはず。もうちょっと踏み込むと、1.5K 個の車までなら最悪でも 3 回で特定できるはず。
実装すると全体的に良くなった。うむうむ。提出して 77.24136 -> 80.89584。
湯船で閃いた！分割した結果細切れになっちゃった区間はまとめて一度にクエリを投げることが可能なので、それをやるとそれなりに改善できそう。
遅延処理書くの、だり〜〜〜！！完全に実装力が落ちている。
やっと書けた〜〜！！80.52735 -> 86.21043。
ちなみに 1.5K 個までの車の順序関係を最悪 3 回で特定する部分の遅延処理は実装する元気がなかったのでサボっている。明日のお楽しみということで。まぁそんなには伸びないだろうけど…。
よく考えたらそんなに難しい実装でもなかったので書いた。88.37724。思ったより伸びた。
なんか分割数のパラメータ弄って気持ち多めに分割するようにしたら少し良くなったように見える。提出して 91.36313。ほっほ。
分割数は今こんな感じ。
divideNum = max(2, min({20, (int) ((1.9 * carIds.size() + K - 1) / K), K / 3}));
4 日目
1 日目にやったこれ、
ひとまずピボットとの比較をする際、それより以前にそのペアについて順序関係が明らかになっていた場合は新たに比較するのを端折るようにして
実は 2 つ以上のピボットを使うようにする改修中に実装がめんどくて消しちゃってたんだけど、復活させて全体で 0.1% くらい伸びた。
あと、今実は細切れ区間のマッチングってかなり雑にやっていて、全ての区間のペアについてその長さの和が K 以下で最大になるペアを選ぶみたいな感じだったので、これを真面目に DP 書いて全ての区間の組み合わせから最適なものを探すようにした。手元で 0.8% 改善。スコアは↑の改善と合わせて 90.49733 -> 91.43657。
あとピボットとの比較を始める前にソート前の車の id 列をランダムに並べ替えておけば、既に比較済みの id たちが全体にバラけて、再度直接比較される回数が減って嬉しそう。
これ忘れてた。実装して 91.93942。
手持ちのアイデアが付きたので、K が小さいケースでのピボットの選び方について考えてみる。例えば K=3 だと最初に比較した 3 個の真ん中をピボットとしてるんだけど、如何せん比較対象が少ないだけに結構偏るケースがあるんじゃないかしら。ということでどのくらいの割合で分割されてるのか出力させてみる。
見ると、やっぱり結構 25% / 75% とかに分割されてるケースは多い。これが初っ端とかで発生するとちょっと手痛い気がするので、3 個の比較を 3 回やってそれらの真ん中の真ん中を選ぶみたいなことをした方が安定するのでは。
とはいえ、これが効きそうなケースはかなりレアだから試しに実装するモチベも低いんだよな〜〜。うーん…。
車の id 列のシャッフルに何も考えずに std::random_shuffle を使ってたけどこれだと実行毎に結果が変わって嫌な気持ちになるので、自家製 xorshift に切り替えた。…と書きながら本当に random_shuffle ってシード固定されてないのか？と思って調べたら固定されてた。ごめん random_shuffle。でもイマドキじゃないしもう使うのはやめようね。
…ああいや、そのペアについて直接比較が行われていなくても、トポソ的に順序関係を繋げば分かることも増えるはずで、ピボットとの比較はもっとサボれそうだな。
これ忘れてた。特定可能な順序を全部はちょっと頭使いそうなので、とりあえずさっとサボれる部分だけ実装してみると、1% くらい改善した。いいね！スコアは 92.74678。
頑張ったらもう少し厳密にやれるんだけど、愚直に書いて時間で殴ってみたところそれほど大きな効果はなかったので、やることがなくなったら考えることにする。
バグみっけた〜〜〜！Yay!! 1% 改善。
スピード比較のクエリを出力する前に、それもう順序関係判明してない？というのを確認して、もし判明済みならクエリを出力せず自前で答えを構築して使うようにしてみたら 0.3% くらい改善した。もしやと思ったけど意外と無駄無駄してた。バグ修正と合わせて 93.74267。
5 日目
ピボットとの順序関係が既知のときにクエリ省略するやつをもうちょっと正確にやって 0.1% 改善。
トポソ的順序関係の特定をもう少し正確にやって 0.03% 改善。
1.5K 個までの車の順序関係を最悪 3 回で特定する部分は、下記の手順でやっている。
N=9, K=6 の場合 1. 先頭 6 個を比較 : |〇〇〇〇〇〇|△△△ 2. 〇のうち速かった 3 個と残り 3 個を比較 : |①②③④⑤⑥|△△△ -> |①②③△△△|④⑤⑥ 3a. 2.の結果の最も遅かった車が〇であれば、ソート完了 : |△①②△△③|④⑤⑥ 3b. 2.の結果の最も遅かった車が△であれば、③より後を比較 : |①△△②③△|④⑤⑥ -> ①△△②③|△④⑤⑥|
つまり、△の部分に速そうな車を集めておけば、つまり既知の順序関係から車を遅そうな順であらかじめソートしておけば、2 回の比較で終わる可能性が上がるということではないか？
-> なぜか速そうな順でソートした方がスコアが良くなった。何か勘違いしてる…？
あと奇妙なのが、速そうな順のソートに std::stable_sort 使ってるんだけど、なんか実行ごとにスコアが変わる…。なぜ？
-> comparator の実装をバグらせていた。ですよねー。結局期待通り遅そうな順でソートしたほうがスコアは良くなって、0.75% くらいの改善。提出して 93.64142 -> 94.50457。
…既知の順序関係のうち速そうな車が分かっていれば↑の手順で良いんだけど、遅そうな車の方がより確証を持って分かっていたなら↑の手順の比較箇所を変えたほうが 2 回で特定できる確率が上がりそう？余裕があればやってみよう。
-> 逆効果だった。もしくはなんかバグらせてたのかな？いずれにせよ爆上がりはしなそうなので放置で。
やっぱり K=2 のときはマージソートが強い気がしてきた。同じペアを何回も比較するデメリットも無いし、変なピボット選ぶリスクも無いし。
書いてみたら N が大きいケースだと当然マージソートの圧勝なんだけど、N=6 ですら 100 ケースの平均取るとクイックソート 10.26 手に対しマージソート 9.97 手なので K=2 ならマージソート決め打ちで良さそう。
seed=1~500 全体では 0.08% の改善。
後は車の数が多い間はシードを軽く吟味したクイックソートで、少なくなってきたらマージソートに切り替えるという手はどうだろう…と思ったけど、N=1000 のマージソートが 8682 手に対し N=500 が 3854 手で、3854 * 2 + 999 > 8682 なのでおとなしくマージソートの方が良さそう。
ピボットとの比較を始める前にソート前の車の id 列シャッフルしてる部分、ランダムにするよりは同じクエリ内の順序関係が未知の id のペア数が最大になるように並べ替えるほうが良さそうな気がする。ただし、クエリを出力せずとも既知の順序関係から答えを構築できるような集合を作れるなら、そちらを優先したほうが良さそう。 ピボットとの順序が既知の車は分割フェーズではクエリから省いてるので、それは気にしなくて良い。
やろうとしたんだけど、比較を始める前にこれの最適化をするのは難しいことが分かった。なぜならピボットとの順序が既知の要素はクエリから外すんだけど、比較を進める中で間接的にピボットとの順序が既知になる要素があるので。
ということで、次投げるクエリについて適宜順序未知の id ペア数が最大になるよう貪欲に入れ替えるようにしてみた。これは K が大きい場合に計算が重いしそもそもスコア的にも逆効果なようで、K=10 以下の場合のみ適用するようにするとかろうじて 0.1% 改善した。うーんそんなもんか…。
あ、入れ替えた後の車がピボットとの順序既知かどうかチェックしてないな。チェックして弾くようにして K=30 以下の場合に適用にしたら追加で 0.14% 改善した。
ピボットを増やしすぎると分割中のクエリのうちピボットが占める割合が大きくなってクエリ数が増えそうなので分割数の上限は K/3 にしてるんだけど、別にピボットを 2 つのグループに分けて 2 周するということもできるので、この上限はあまり重要ではない気がしてきた。
…本当か？全体を 2 周するくらいなら分割した後それぞれの区間で個別にやる方が良いのでは？これは後回しかなー。
そろそろ K が小さいときにピボットを吟味するやつをやりたい。
とりあえず K が小さいかつ車の台数が K の 10 倍以上あるときは先頭から 3 回分クエリを投げて、その中央値 3 つでもっかいクエリを投げて、その中央値をピボットとするやつをやってみた。結果は K=3 に絞ると 2% くらい改善、K=4 はトントンくらい、K=5 以上で悪化傾向という感じ。ひとまず K=3 の場合だけ適用して全体としては 0.04% の改善。
K=4 のときをもうちょっと何とかしてあげたいが、偶数なだけに中央値取りづらいんだよな…。どうするのがいいんだろう。
6 日目
今は例えば分割数 2 でピボットを決める際、基本的に適当に頭から K 個選んでその中央値をピボットにしてるけど、ある程度順序関係のペアが出揃ってきたらその情報を基にピボットを決めても良さそう。
分割数が 2 かつ今のノードの深さが 2 以上のとき、各車についてその区間内で既知の自分より速い車と遅い車の台数を数えて、それらがバランスするかつ既知の台数が多い車をピボットにするようにしてみた。これはぼちぼち効いて 0.38% 改善。
拾えてない順序関係回収できればと思って時折ワーシャルフロイド的なループを走らせてみたものの、微妙にスコアが下がった。順序関係明らかにしてるだけなのにスコア下がるの…？？
分割数のパラメータをより分割する方に調節したら 0.56% 改善した。儲け。
車の id 列をランダムにシャッフルしてた部分を、既知の結果から速そうな順に並べ替えるよう変更したら 0.6% の改善。提出したら 93.63266 -> 93.28669 に下がったけど流石に手元の 500 ケースの方が信頼できるはず…。
…もしかして TLE してたりする？手元だと最大でも 300ms とかなんで大丈夫だと思うんだけど…。example の出力を落として見ると seed=3 とかで 1000ms くらいかかってるので、雑に見積もって手元の 5 倍くらいにはなる可能性がある？だとしても間に合うけど。少なくとも今追加したロジックがボトルネックになるとはあまり思えないので放置。
ある区間のある車について、その区間内の他の全ての車との順序関係が分かっていれば、クエリから省いたほうが良い。調べてみた感じそういう車はぼちぼち発生するみたいなので、スコア改善できる余地はありそう。
実装して 0.9% の改善。Yay!
スコアの稼ぎどころを整理しよう。
- 分割数の最適化
- ピボット選択の最適化
- 既知の順序関係の有効活用
で、今計算時間が 9000ms くらい余ってるので、これを何かに使ってあげたい。計算時間を使うといえば、例えばモンテカルロとかのプレイアウト系？分割数とかピボットの選択をシミュレーションして、一番平均手数の少なかったものを実際に使うとか？悪くはなさそう。
分割も終盤になってきたら、既知の情報に矛盾しない仮の答えをたくさん用意して、それに対し各車をピボットとしたときの挙動をシミュレートして平均手数を計算し、一番手数の小さかったものをピボットとして採用する。これで行こう。
-> ちょっと手数だと正確なシミュレーションを実装できそうな気がしないので、どれだけ均等に分割できるかに焦点を絞ってみる。
-> 効果はなかった…。まぁ、そんな気はしていた。
というか今さら気付いたんだけど、今の分割数はこんな感じになっていて、
divideNum = max(2, min((int) (2.5 * carIds.size() / K), K / 3));
これってかなり過剰めに分割する感じなんよね。例えば N=400, K=100 だと 10 分割。で、なんでそれで上手くいくかというと、細切れになった区間をうまくまとめてクエリを投げてるから。なので、実はかなりのテストケースで分割は 1 回のみで後は細切れ区間を処理して終わりみたいな感じなわけで。それなら、初っ端の分割数についてシミュレーションしてみた方が良いんじゃないかなあ。初っ端からまるごとシミュレーションなら既存の実装を使い回しやすいし、かなり正確な挙動を再現できるはず。これは伸びる！！！
しかしそれやるとなると本番サーバで 1000ms かかってるのは致命的だな…。うーん。
7 日目
とりあえず、今までの分割数から -1, ±0, +1 したものの 3 通りを時間いっぱい試して、一番良かったもので本番に臨むようにしてみる。-1 と +1 にしたのは、今までの分割数だと K の値との関係的にピボットが少し偏って一番最後の塊だけが異常に大きくなるみたいなケースがちらほらあって、そういうのはひとつ分割数をズラすだけで改善できたりするため。実際これを実装するとポツポツと改善するケースが見つかり全体で 0.65% 改善。うーむ、欲を言うともう少し改善して欲しかったけど、結構安定して良くなったので良し。というか一発で動いてびっくりした。今回は丁寧にコード書くよう心掛けてたんだけど、こんなにバグなく実装進められるならいつもやるべきだ。
さて、これで 1 回の分割で終わるケースはほぼ最善を尽くせたはずなので、今度はピボット選択に戻ろうか。
適当にピボットを選んだあと何回か比較を進めて、あまりにダメそうだったら変更？
そういえばまだやってなかったけどこれ有効なんじゃない？
-> 少し試した感じだとあまり有効ではなかった…。
分割中の awaiting ノードは細切れクエリマッチングの際に優先的に使うようにしたら、その子供が早めに awaiting のキューに突っ込まれてマッチングが少し最適化されそう。
実装して 0.01% 改善。
ピボット数弄ってたらバグを見つけた。クエリ投げてソートされた id 列からピボットを均等に抽出して決める際、
rep(i, divideNum - 1) { pivotCarIds.push_back(sortedIds[sortedIds.size() / divideNum * (i + 1)]); }
divideNum で割った後に i+1 掛けるのだと切り捨ての関係で一番後ろの区間だけ広めになっちゃうことが気がする。計算の順序を逆にして 0.2% 改善。あぶね〜。
残り 2 時間切ったしアイデアもちょうど尽きたので終わり！
まとめ
暫定順位 / スコア
4 位 / 94.28737
方針
- ベースはクイックソート。1 個以上のピボットを選び、2 つ以上の集合に車を分割して再帰的にソートを行う。
- ピボットの数は
max(1, min(2.5 * 車の数 / K, K / 3) - 1 + a)。- α の値は -1, 0, +1 の 3 通りを決め打ちして頭からシミュレーションし、一番平均手数の少なかったものを採用する。
- 細切れになった集合は 1 つのクエリにまとめて出力する。
- 車の数が 1.5*K 個以下になった集合は高々 3 回のクエリでアドホックに順序を特定する。
- 適宜ワーシャルフロイドっぽいことをして既知の順序関係から導出可能な順序関係を特定しておく。
- 既知の順序関係の情報を活用する。
- ピボットとの比較時、順序関係が既知の車はサボれる。
- あの車が集合内の他の全ての車と順序関係が既知の場合、その車はクエリに含めない。
- 既知の順序関係からピボットとして有用そうな車を選ぶ。
- 集合内の車を既知の順序関係から推定される速度順に事前にソートしてから処理することで、必要なクエリ回数の期待値が下がることがある。
- K=2 の場合は例外的にマージソートで解く。
