マラソンマッチで誤解してたこと、してなかったこと
前書き
ゆるふわ競技プログラマです。 koyumeishi というアカウントで色々参加させてもらっています。
この記事の執筆時点 (2018/12/28 05:00 AM JST) ではまだ結果が出ていませんが、
先日 topcoder で開催された MM105 でマラソンマッチ(MM)のレッドコーダー*1になれた気がするので*2、
少々気が早いですが記念にポエム記事を。
[2019/01/05 追記] 最終結果が出て 2 位、 レーティングは 2318 に。 無事赤になれました。
僕が MM に初参加したのは 2016 年の TCO らしいですが、既にアルゴリズム系コンテストの方には結構参加していて、
当時もうイエローコーダー*3になっていました(今でもまだ黄色ですが)。
競技プログラマなので当然 twitter をやっていて、TL で chokudai さんや shindannin さん等有名な競技プログラミングの先輩方が MM 談義をしているのを目撃していたため、参加前から MM の脳内イメージみたいなものが形成されていました。
実際赤に届きそうな所まで参加してみて MM のことを 1ミリぐらいは理解できたと思うので、参加前のイメージと実際のところどうだったのかを適当に。
誤解してたこと
❌ どうせ焼き鈍しとかビームサーチをやるだけなんでしょ?
間違ってはいないですが、近傍の選び方、評価関数、探索の工夫等、いくらでも差が付きます。
アルゴで「どうせアルゴリズムを使うんでしょ?」と思うぐらいに無意味。
局所探索による解の改善よりも戦略が重要だったりする回もあります。 良い貪欲に勝てない…。❌ 時間をたくさん使った人が強いんでしょ?
2週間苦しみながら戦っても常人では移動中の飛行機の中だけで参加した Psyho*4 に勝てません。
アルゴで自分だけ10倍の時間貰っても tourist*5 になれないのと同じです。
時間を使いすぎると色々良くないので、僕は最後の二日間ぐらいしか真面目にコード書かないことが多いです。 問題は序盤に読んでおいて脳内で考察・検証はしています。
土日にしかできない人・あえて時間制限を設けて参加する人・休みを取ってフル参加する人、色んなスタイルの人がいるので無理せずマイペースに楽しめたらと思います。△ 計算資源をたくさん使った人が強いんでしょ?
先人のブログを読むと「外出してる間に自動パラメータ調整してた」とか「AWS 課金して N 並列で回してました」とかが見つかります。 何か強そうだしアルゴではそんなことしないのでここが大事なのだと誤解してしまいます。
N 時間計算回して最適化したパラメータよりちょっとした近傍のアイデアの方が改善幅が大きいです。 上位で ε を競う段階になってからじゃないとそんなに意味はない。
アイデアを実験するのに並列環境があるとトライ&エラーが速くなって便利だけどエンジョイ勢*6的には必須って程ではありません。 (実際便利だと思うので、お金が余ってるとか、クーポンが余ってるとか、AWSの練習に、とかは全然アリだと思います。 必須ではないけどあればストレスフリー)
僕は基本的に 1-2 コアしか使ってないです。 2コアで回すと暫くぱそこんが使えなくなって悲しい。△ 黄色のアルゴリズム力があるから有利
TCO MM Finalist のアルゴレーティングを見てみましょう。 特に有利って訳ではないです。 むしろ黄色しかないなら不利です。
実際必要なアルゴリズム力・実装力は青 ( or 経験豊富な緑) ぐらいで十分な気がします。
自分が実装困難だなーと思う手法は他の人も実装困難だと思ってるはず。 妥協も大事。△ 黄色のデータ構造力があるから有利
アルゴでは常に最悪計算量を意識しますが、MMでは平均計算量を意識します。 ちょっと意識を変えないといけないのでアルゴで強かったデータ構造がそのまま使えるとは限りません。
例えば N x M のセルを何色かに塗り分ける問題で、1. 位置 (r, c) を色 C に変更 2. 矩形 (r0, c0, r1, c1) 内に色 C のセルが存在するか判定
を高速に処理出来ると嬉しいとき、アルゴ脳だと何も考えず 2 次元の Segment Tree とか Fenwick Tree を使いたくなります。 MM では基本的に悪意ある入力は与えられなくて、実際に必要な矩形クエリは小さいものがほとんどだったり、 色 C が高確率で存在したりして、愚直に走査する方が速かったりします*7。 あるいは平均計算量が小さくなるように工夫して探索を制限したりもします。
ダイコネ*8も Wavelet Matrix*9 もMMには不要。 多分。❌ 定数倍高速化テクとかSIMD命令を使いこなさないといけない
Java で上位に入ってる人*10がいたら多分不要です。 きっと定数倍より重要なことがあります。*11
問題があまりに典型・単純でアプローチに差が付かない場合必要かもしれません。❌ 赤い人たちはレベルが違い過ぎて勝つことなど不可能
強い人も解法ガチャを外して中位・下位のまま終了することがままあります。 期間が短くてリトライが効かない回だと特に。 毎回強くてどうしようもない人もいますが、神様ではないです。❌ ビジュアライザを頑張って書かないといけないんでしょ?
ビジュアライズすることによって何かが見えたりすることもありますが、なくても / 公式 (+α) でも大丈夫です。 何をビジュアライズすべきかは方針次第で、漠然とビジュアライザ書かなきゃ、と時間を浪費するより解法を考える方が有意義かも。 (でも twitter 映えするので余裕があればビジュアライズして欲しい)
誤解してなかったこと
✔️ 生活リズムが崩壊する
締切日は徹夜。 (初動が遅いせい。自己責任)✔️ つらそう
つらい。✔️ くるしそう
くるしい。✔️ たのしそう
たのしい!
他にもあった気がするけどまぁそんな感じ。
本当はアルゴ青・黄ぐらい*12の方向けのMM入門記事、みたいのを書こうと思ってたのですが、最近はハーフマラソンやらHTTFやらで最適化系問題に触れる機会が増えて既に入門を終えてそうなのでこんな感じに。
誤解が解けたら君も MM に参加しよう!*13
[2019/01/05 追記] 要するに何が言いたかったかと言うと、参加する前のイメージ程ハードルは高くなかったです。 気軽にMM参加してね。
*1:topcoder ではレーティング2200以上の人。 つよい。
*2:暫定順位・スコア的に余程運が悪くなければ大丈夫。もしなれてなかったら木の下に埋めてもらっても構わないよ
*3:topcoderではレーティング1500-2199の人。 わりとつよい。
*4:MM界のtourist
*5:競技プログラミング界のtourist。 TCO18MM覇者
*6:赤に触るぐらい
*7:問題依存。データ構造使った方がいい場合もある
*8:Dynamic Connectivity. グラフの連結性判定ができる
*10:wleite さんとか tomerun さんとか
*11:基本的にC++の方が速いため。Java勢がC++に移植し始めたら要注意?
*12:実装したいものが実装できる/実装困難だと何となくわかる程度