MM127参加記

TopcoderのMM127に参加しました。

エンジョイ勢の感想文なので、さほど参考にはならないと思いますが。

問題概要

速さが異なるN台の車をK台以下づつ競走させてその結果から総合順位を求める。

競走回数が少ないほど高スコア。

初めにやったこと

問題ページにgifがない=ビジュアライザーが提供されないことにがっかりしつつ問題を読む。「ソートだな」と思ってまずWikipediaのソートのページでソートアルゴリズムをあれこれ見る。効率のよいソートと言えばクイックソートなんだけど、コムソート（櫛ソート）ってのが知らなかったし計算量NlogNらしいし謎のパラメータ1.3とか気になったので実装してみて提出→結果1.6くらい。最低点争いですか？まあKがいくつでも2要素の比較しかしてないし。250レーンを走る2台の車。

次にやったこと

エスケープシーケンスでビジュアライズしてソートの様子を眺めていたら同じ要素を何度も比較している。そりゃ効率わるいわ。そういえばAHC003でも一度得た結果を保存しておいて何度も使いまわしたらスコア改善したな。比較結果を保存しておこう。配列はN×Nで、自分同志の部分（対角線）はいらなくて…。ハッΣ(ﾟ□ﾟ；)それってリーグ戦の対戦表では？…ということでリーグ戦の表を効率よく埋める問題を考える。

とりあえず対戦は表の空いてる部分からランダムに組んでみる。車の速度は全部異なり固定なので、AがBに勝ちBがCに勝っていれば、A対Cは実際に対戦しなくてもAの方が速いことが推測される。…という感じでプログラム書いてみたものの、ローカルテスタのSEED=2（N=1000）で２０秒弱かかる。制限は１０秒なので当然TLEなのだけど、そこまで大きくないテストケースなら通るので提出してみると40点弱。とりあえず最低点争いは脱する。TLEがあっても点数ほしい人はMMをやろう（？）

まずはTLEを何とかせねば。計算量削減をあれこれ試みるもむしろ実行時間が数倍になったりして、競プロerとしての実力の無さを思い知らされる羽目に。

埒が明かないので、計算量削減はあきらめて効率よい対戦の組み方を考えることにする。全体の対戦数を減らせれば実行時間も減るわけだし。ということでまたエスケープシーケンスでビジュアライズしたリーグ表が埋まっていく様を眺める。最後に残るのは順位が１つ違いの組み合わせであることに気づく。順位が一つ違いということはその対戦以外の勝敗は同じなので、推測では埋められず残っちゃうということかな。順位が近そうな対戦を優先して組めば効率よくなるかも？勝利数の度数分布調べて、多い勝利数の車同士の対戦を優先して組むか、と思ったけど面倒くさいので、とりあえず単純に勝利数でソートして順番に対戦させてみることに…。

ん？N=1000でもTLEどころかあっという間に終了したぞ？スコアは？さっきまで４桁だったのに３桁、４００点弱…？え？え？マジ？

これは順位上がるかもと期待しつつ提出………

え？９位？Σ(ﾟ□ﾟ；)

いやいや、ソートしただけだし、何も探索してないし、こんなプログラムでこんな順位いいんですか？？？

その後の展開

もう少し効率良くならないかと、勝利数の度数分布から対戦組んでみたり、試合数でソートして対戦組んでみたり、まず０番は残り全部と対戦させてみたり、雑に乱択してみたり、思いつくこと試してみたけど、スコア下がったり無限ループにはまったりして、結局最初に何となく書いた勝利数ソートを超えることはできずじまい。その間に、マラソン上位の常連のみなさんに抜かれて暫定１７位で終了。ずっと一つ上にいたkuusoさんが提出ミスで順位下げてしまったようなので、実質１８位かなと思います。

感想

どちらにしろシステスでもこのまま行ければ過去最高順位なのですが、とりあえず書いた解法が奇跡的に刺さっただけで実力を伴ってないので、うーん、喜んでいいのか微妙な気持ち。ま、とりあえずtourist君には勝てそうです。touristに勝ってみたい人はMMをやろう（？）

あとAHC003でもやったエスケープシーケンスを使ったビジュアライズを今回もやって楽しかったです。やってることは文字出力なのでCtrl-Sで一時停止できたり、スマホ上のC++コンパイラでも動かせたりするので、問題にもよるけど今後もやりたいです。スマホでいつでもどこでもマラソンが出来ると生活崩壊に拍車がかかりそうですが。

今回、順位は自分的には良さそうですがマラソンらしい探索は書けてないので、次回は、いや、いずれは「ぼくがかんがえたさいきょうのどんよく」じゃないプログラムを書きたいです。おわり。

（6月29日追記）

MM127 kuusoさんが17位に戻ってきて18位で確定のよう。そもそも勝ててなかったので、提出時間はまあいいんじゃないかな。
そして、12日に提出したきり放置のtouristに勝ちました！（嬉しいか？