概要

諸々の小道具やメタ戦略に関する話をまとめました。 プログラミング言語や関連する道具や手法であれば特別な才能がなくても習得できます。 素手でも赤になれるほどの才能があるなら別ですが、そうでないならとりあえずすべて抑えておくとよいです。

その他の話はほぼすべて マラソンマッチにおける精神論 - chokudaiのブログ か Topcoderマラソンマッチの探索問題で重要なこと - Qiita に書いてあるので省略します。

なお、マラソンマッチで最も重要なのは才能でも道具でもなく「根性」とか「覚悟」のような何かだと思っています。

競技の流れを踏まえて動く

競技はたいてい以下のように進行します。 最終日にやるべき作業を3日目にやるなどは避けましょう。

  1. 問題を読む
  2. 解法を考える
    • 実装を始めてしまうとその方針以外のことが思い付きにくくなるため重要
    • ここで思い付いた案はすべて書き残しておく
  3. 貪欲解の実装
    • 目的は誤読の洗い出し。すべての要素を使うようにする
  4. testerを読む
    • テストケース生成の手順をちゃんと読む
  5. 提出して退路を断つ
  6. 必要そうなら可視化などの準備
  7. 焼き鈍し/ビームサーチ解などの実装
    • ただし途中に乱択繰り返しや山登りを実装し、段階的にきちんと点数が改善することを確認する
    • 良い貪欲解が書ければ良い焼き鈍し/ビームサーチ解に繋がる
    • だいたいここまでが1,2日目
  8. 実装の改善
    • ひたすら観察と実装を繰り返す
    • 荒いパラメタ調整は随時やっていく
  9. 実装の仕上げ
    • 最終日にのみやる
    • ひたすら実行してエラーを吐かないことを確認
    • 細かいパラメタ調整と定数倍高速化

日記を書く

日記 (例: diary.md) を書きながら進めるのがおすすめです。 コンテスト中で詰まったときに見返して観察/試行の漏れを潰すために書きます。

一発で正解を引く能力がない以上は網羅的な試行で強引に正解を探索するしかなく、その漏れを防ぐためにこれは重要です。 成功も失敗もすべて記録します。 特に失敗を記録しておくのは重要で、状況が変わった際には過去の失敗をすべて検証しなおします。 例えば「失敗したがそれは隠れていた別のバグに邪魔されたため」のような状況は多いですが、失敗をきちんと記録していなければそのバグが修正された後でも「失敗であった」と思い込んだままになりがちです。

時系列順にtwitter感覚ですべて投げ込んでいくようにしましょう。 下手に整理をしようとするとその枠に収まらなかった事項の記録漏れが起こりやすく、また変に構造化しようとしてページが分割されると見返し忘れが発生しやすいです。 この意味で「日記」と呼んでいます。 例えば GitHub Issues (使用例) などは使いたくなりますがおすすめしません。 単一のissueにすべてまとめるのならありかもしれません (例)。 gitのtag機能で点数を管理するのはありかもしれませんが、しなくてもよいです。

git と GitHub を使う

gitはバージョン管理システムであり、GitHubはそのホスティングサービスです。 適切にcommitやbranchingを行なっておけば、例えば「3日前に試してだめだったので消したあの修正をもう一度試したいんだけど」が1コマンドでできます。

GitHubのprivate repositoryとして公開しておくと家の外でスマホから日記やコードが読めるようになるのも嬉しいです。 repositoryは問題ごとに切りましょう。 日記もgitで管理するとよいですが、日記単体で管理するbranchを切っておくのがおすすめです。

シェルスクリプトを書き自動化をする

Unix系環境を導入しterminalに慣れましょう。 algoならVisual StudioのためだけにWindowsを使うという選択肢もありですが、マラソンマッチでは推奨できません。 黙って仮想環境を入れてください。 最近は Windows Subsystem for Linux があるので(Unix系の環境に慣れている人なら)混用も可能でしょう。

bashのman pageを1度は通読しておくべきです。 諸々のentry pointとして簡単なMakefileも書けるようにしておきたいです。 GNU paralelは並列実行をするときに便利です。 クラウド環境への接続のためsshも理解しておきましょう。

とりあえずなんでも自動化しておくとよいです。 多くの場合で単に手間が省ける以上の利点があります。 例えば、自動提出スクリプト (kmyk/online-judge-tools) があれば夜寝ている間でも提出ができます。

性能評価をきちんと行い、改善の方針を立てる

「なんとなく改善された気がする」ではなく定量的に評価をしましょう。 どういうときに点数がどう変化するのかが分かれば改善の方針に繋がります。 解法の良さの指標としては2000ケースの正規化点数の算術平均を基本にし、最大/最小/中央値/四分位数も確認するのがよいでしょう。

環境変数経由でseed値を渡してプログラム側から統計用の情報をjsonなどで吐くようにします (例)。 これを pandas や seaborn などに投げ込んで整形し眺めます。

必要なら点数の正規化を忘れないようにしましょう。 例えば、盤面の大きさに生の点数が比例するような問題で相対scoringなら、全テストケースの点数の算術平均を基準にするのは明らかに間違いです。 適当な上限や貪欲解の点数からの差分や比率を用いて正規化された点数で考えましょう。

高度な統計処理はあまり重要ではありませんが、変数間の相関を見るぐらいはしておきましょう。 点数と他の変数の間の相関を見付けられれば改善の方向の検討が付きます。 例えば盤面の大きさと点数の間に強い負の相関があれば、分割してそれぞれで解いてみることを思い付けます。

また、あと何点上げればよいのかは常に確認しておきましょう。 入力データの生成過程から逆算すると理論上限が分かり、順位表の1位の点数と比較するなどすると現在の目標が分かります。

同じケースを複数回実行してみる + 制限時間を伸ばして実行してみる

性能評価においては普通に実行するだけでは不足で「同じケースを複数回実行してみる」「制限時間を伸ばして実行してみる」も必要です。 これらにより探索の性質が掴めます。

同じケースを複数回実行してみて点数が大きく揺れるなら、局所解からの脱出力不足が考えられます。 Boltzmann定数の調整や多点スタートなどを試すべきでしょう。

制限時間を伸ばしても実行しても点数が改善するなら定数倍高速化が重要であることが分かります。 点数が変化しないなら時間を上手く使えていないことが言えます。

クラウド環境などを使って高速に性能評価をする

十分な回数のテストを行なうには高速な計算環境が必要です。 クラウド環境を利用しましょう。 テストが爆速になるので開発サイクルを回す速度が大きく改善されます。 例として制限時間10秒の2000ケース実行を1セット行うことを考えたとき、普通に直列で実行すると5時間半かかりますが、これを10分で終わらせることができます。 いくらか費用はかかりますが、例えば上の例だと8円程度と十分に安いです。

具体的にはAmazon EC2がおすすめです。 spot instanceとして借りれば適当な32vCPUの環境が1時間あたり \($0.3 \sim $0.5\) 程度で借りられます。 計算能力と使用時間の積に対して課金が発生するので、並列度を上げれば費用は変わらずにlatencyだけを下げられます。 私はまだ整備できていませんが、理論的には、10000ケースだろうと10秒で実行が終わる環境が作れるはずです。

可視化をやる

綺麗に可視化できるとデバッグ効率の上昇が見込めます。 さらにやる気にも影響するので有用です。 配られたvisualizerに甘えず、必要そうなら自分で書きましょう。 単純にはPythonからmatplotlib系を使い、少し複雑にはJavaScriptでcanvasを叩き、重たい処理が必要ならC++でGUIをすることになります。

単に解を見やすく表示するだけでなく「各点を使ったときの点数の差分をヒートマップにする (例)」「焼き鈍しの過程の点数の変化をグラフにする (例)」などの可視化も有用です。

パラメタ調整は必要だが時間を使いすぎてはいけない

パラメタ調整は重要です。 細かな定数倍最適化などとは違って予想以上に大きく変化することがあるため、序盤中盤から簡単に調整を試していきましょう。 しかし安易にパラメタ調整に時間を使うのはだめです。

自動化は多く試されています (例) が、私はまだ成功させられていません。 現状では爆速テスト環境を用いて手動で調整しています。

バグをすべて検出する

バグのない実装をし、バグが発生したらすぐに検出される環境を作りましょう。 システムテストで0点を出すのは論外です。

特に終了間際にはバグがないことを確認しましょう。 可読性と相談しつつ積極的に assert を書く、プログラム側から予想される点数をtester側へ渡して一致することを確認させるなどをして、その上でとにかく実行をすればよいです。 ランタイムエラーにはならないが点数が落ちる場合にも注意しましょう。 およそ \(10^5\) ケースほど実行して一度もエラーが出なければ(実行環境依存のものを除いて)安心してよいでしょう。 実際のところ、この回数は最終日にパラメタ調整をしていれば自然に達成できます。

定期的に再検証をする

過去に試して失敗した案でも、コードが変化してから再び試すと成功することがあります。 過去に試して成功した案についても同様です。 これを定期的に再検証しましょう。

特に、バグが発覚した場合は関連する案をすべて試し直しましょう。 バグがある状態で行なった実験の結果はほぼ無価値となります。

定数倍高速化をできるようにしておく

自分の使うプログラミング言語は十分に理解しておき、最適な実装をしましょう。 ただし実質的に言語はC++の一択で、C#やJavaも良い言語ですがマラソンマッチの用途には勧めません。 言語仕様の重箱の隅をつつく能力は不要ですが、標準ライブラリの内容はできるだけすべて確認し、可能ならコンパイラやCPUごとの特性も把握しておくべきです。 とりあえずパタヘネを一読しておくとよいでしょう。 その上で、できるだけ最後まで定数倍高速化は控えましょう。

どのような最適化がどれくらいの効果を持つかを経験として持っておきましょう。 TopCoder固有でかつ覚えておくべき代表的なものに絞って以下に挙げました。

  • 時間計測問題
    • gettimeofday や clock は避け rdtsc を叩く
    • snippet
  • TopCoder上のg++だとポインタ操作 (つまり std::vector) は最適化されづらいので配列にする
    • 上手くSIMDが刺さった場合はさらに効く
  • pragmaを付ける
    • #pragma GCC optimize "O3"
    • #pragma GCC target "sse4.2"
    • このとき #include <bits/stdc++.h> してるとcompile時TLEしうるので注意

上手くやらないとただコードを汚なくするのみに終わるので十分に注意してください。

順位表はまじめには見ない

順位表はあまりまじめに見ない方がよいです。 順位表の用途は見落しの検出と1位の点数の把握のみです。 モチベーション維持にもなるかもしれません。 provisionalのケース数は少ないので、順位表を根拠に改善量を判断するのは間違いです。 他人の順位からのメタ推論はほぼ役に立ちません。

提出は定期的にしましょう。 順位が予想よりかなり低い場合はなにか重大な見落しがある可能性があります。 鯖上でのみ再現するバグの検査にもなります。

順位が荒れている不穏な空気がある場合は自分を信じることも大切です。 適切な集計の下で、順位表上の100ケースより手元の2000ケースを信用しましょう。

時間を作る

大学生なら授業に出席する回数を最小にしましょう。 社会人や高校生は上手くやってください。

退路を断つ

あなたがもしratingを気にする人なら、早期に提出して退路を断ちましょう。 撤退の余地を残した中途半端な状態で参加するのはおすすめできません。 潜伏は1位争いをしているのでもなければ無駄です。 rating変化予測器 kmyk/topcoder-marathon-match-rating-predictor もモチベーションの維持に有用です。

ライバルはいるとよい

実力が同程度の相手と順位を交換しあうのは楽しいです。 楽しいと点数が伸びます。 私の場合は kurenai3110, kosakkun のふたりをこの用途に使っていました。

forumはきちんと確認しよう

問題の修正などの告知があります。 forum以外での告知は基本的にありません。 list (例: https://twitter.com/iwashi31/lists/tco18mmr2) を作ってtwitterを監視するのもよいでしょう。