目次
はじめに
皆さんこんにちは。
この記事は、下記のイベントの一環として書かれたものです。
Competitive Programming Advent Calendar
http://partake.in/events/ee35b200-e151-44c1-b123-482d0a7447b5
マラソンマッチ上位者と言えば @chokudai さんや @wata_orz さんが有名ですが、二人に比べれば多少劣るものの、私もマラソンレッドコーダー保持者の一人です。
マラソンレッドコーダー保持者は今の所、日本に５人６人しかいない様です。
実は、私の実力を客観的に見ると、マラソンマッチのレーティングで言うと1500〜1700ぐらいが妥当な線だという自覚があります（私より明らかに実力が上の方々が1700付近でとどまっていますので）。
ところがどういうわけか、2200以上のレッドコーダーを保持できています。
そして、今後も定期的にマラソンマッチに参加するつもりですが、レッドコーダーを保持し続けるのは難しくないように感じています。
私より実力が上なのに1700付近の方々と、私と、一体何が違うのでしょうか？
１つはマラソンにかけられる時間量かもしれません。
でも時間がたっぷりあれば、本当にマラソン上位は取れるのでしょうか？
頭脳勝負なら勝てない方々に、頭脳だけの勝負じゃないから、マラソンで勝負になるわけです。
SRMが頭の回転の速さや知識量や練習量を競うものであるのに対して、マラソンは総合力で競います。
マネジメントスキルなどによって、頭の善し悪しを補って戦う事ができます。
また、SRMの様な単純な繰り返しトレーニングでは、レーティングが思う様に伸びないはずです。（たぶん）
ハッキリ言って、SRMは若い方が有利ですが、マラソンマッチは年老いても不利になりません。シニア向けの競技です。
こうした性質は、マラソンマッチの最大の魅力であると言えます。
本記事では、マラソンマッチに対してどのように取り組めば成果を出せるのかということについて、主に説明をしていきたいと思います。
また、この記事を読むことによって、社会人プログラマの方々が、「会社で身につけてきたノウハウと同じじゃないか。自分だってマラソンマッチで上位が狙えるんじゃないか？」という実感を持って頂けたら、嬉しく思います。
なお、本記事には、一部の技術的背景などについての説明不足が多々存在します。
私が今回論じたいのは取り組み方についてなので、その辺をご理解頂いた上で、分からない部分は調べつつ読んで頂けたらと思います。
マラソンのノウハウは、たった３つ
私が思うに、たった３つです。以下に挙げます。
１．問題をしっかり把握する
２．判断基準を明確にする
３．反復期間を短くする
あれ？ なんか、会社でやってることと似てませんか？
１．問題をしっかり把握する
開発するときも、問題をしっかり把握することは重要ですよね。
最初にお客様相手にしっかりとヒアリングを行うと思います。
ヒアリングでつまずくと、その後の開発が台無しになりかねません。
何を解決すべきなのかを、しっかり要件として定義し、把握する必要があります。
ドメイン駆動設計では、ドメイン言語を用いて、システムの専門家もドメイン（問題）に対しての理解を深めていきますよね。
貴方が開発者ではなく、トラブルシューティング部隊に所属していたとしても、問題をしっかり把握することがどれだけ大切なことかについて、既に分かっていることと思います。
不具合の症状は何であるのか？ その症状に対して、お客様はなぜ困っているのか？
バグの修正だけが本当に問題の解決であるのか？ 何が満たされれば、問題の解決と定義できるのか？
不具合の再現する条件はなんだろうか？ 正常に動いていた時は、今と何が違ったのか？
そんな感じで、資料を最初に集め、調査を進めていくことと思います。また、お客様に、何が満たされれば解決であるのかについて、訊ねることもあるでしょう。
これらは全て、問題に対しての理解を深める行為です。
マラソンでも、これが最初に要求されます。
もちろん、問題文は最初に読みます。でも、それだけを言っているわけではありません。
問題文を読んだだけの段階では、問題への理解は不完全なものです。
その不完全な理解を、少しずつ完全なものに近付けていく必要があります。
ここにどれだけの時間を費やせるかが、間違わずに正しい方針を選べるかにかかっています。
正しい方針は、正しい設計へと繋がっていき、下流工程の大幅な工数削減へと繋がります。
（ここをサボると、下流工程が増えて、２週間では上位を目指せなくなります）
ノウハウとして３つあげましたが、３つの中でも本項はダントツに分量が多いです。
それは、３つの中でダントツに本項の重要度が高いことを示しています。
それでは１つ１つ見て行きましょう。
問題をちゃんと読む
問題を読むだけでは不完全ですが、問題を読まなければ始まりません。
出題は英語です。マラソンマッチは２週間程度の期間が与えられていますので、丸１日を英文読みに費やしても、バチは当らないのではないかと思います。
英和翻訳サイトは、Yahoo翻訳やGoogle翻訳などがオススメです。
この２つは翻訳方式として全く異なるものを採用しているので、翻訳させる英文によって、得手不得手が分かれることも多いです。
片方でちゃんと翻訳されない場合は、もう片方も使ってみてはいかがでしょうか。
私の場合、マラソンマッチを始めたばかりの頃は、プライベートwikiに英語のマラソン文を貼付けて、それを１行１行、翻訳サイトを使いながらの半手動翻訳していき、wiki上に日本語の問題文が完成してから、マラソンを開始していました。英語が苦手だった私でも、だいたい半日ぐらいあれば、翻訳できていました。
テスタを読む
マラソンマッチでは、テスタのソースコードが公開されています。
試合によって、グラフィカルな表示を行うテスタが付属する場合があり、その時はテスタではなく、ビジュアライザと呼ばれます。
テスタであってもビジュアライザであっても、ソースコードは公開されていますから、ソースコードを必ず読む事をおすすめ致します。
テスタのソースコードに書かれている問題生成手順が、多くの場合、本番でも使われます。
「ランダムに生成」と書かれている部分であっても、ソースコードを読めば、ランダムの分布のニュアンスが分かる場合もあります。問題文から読み取れなかった部分であっても、ソースコードを読めば一目瞭然なことは多いのです。
問題文の英語の細かなニュアンスが分からない場合も、テスタのソースコードが解決に繋がることは多々あります。
テスタのソースコードを読むことで、問題の定義について、分からないことがなくなるのではないでしょうか。
（賞金ありコンテストの一部では、稀に問題生成手順が隠蔽されることがあります）
なお、探索問題の場合、問題入力と解出力のみから点数を計算する方法がテスタに埋め込まれている場合があります。
これをほぼそのまま流用することで、探索問題の評価関数は完成したも同然の場合が少なからずあります。
（実際には、MM70等、速度面を大幅に調整する必要がある場合もあります）
問題を理解するために回答プログラムを書く
問題をいかに解いて、より高得点を取るかということは、この段階ではあまり重要ではありません。
それよりも、出題された問題の傾向などを解析するプログラムを、回答プログラムとして作っていきます。
たとえばMM68（美しいクロスワード）ではクロスワードに使うことができる単語一覧が問題入力として与えられます。
これに対して、aで始まる単語がいくつあるか、bで始まる単語がいくつあるか、、、zで始まる単語がいくつあるか？
それから、aで終わる単語はいくつ？ bで終わる単語はいくつ？ と、それらを統計して表示するプログラムを書くなどしました。
問題の解としては、この段階では空っぽを返して良いのです。点数は重要ではありません。
そうそう、マラソンマッチでは標準出力はテスタとの通信を行うために使われるので、リポート出力には標準エラー出力を使うと良いかと思います。
もしくは、問題番号をどこかから抜く様にするなどしておいて、問題番号.txtや、問題番号.htmlのファイルを生成して、そこに書き込んでも良いでしょう。（問題番号を抜く方法については、後述します）
ビジュアライザの自作
付属のテスタがビジュアライザ機能を持っている場合であっても、ビジュアライザが不十分な場合が多々あります。
そういう場合に、ビジュアライザを自作するという方法が有効な場合があります。
といっても、そんなに時間が取れない場合も多いので、htmlリポート機能を付けたり、あるいは既存のビジュアライザに表示を付け足して使うという方法もあります。
実際、ビジュアライザはとても重要です。
問題文とテスタソースコードを全て読み終えて、問題の方程式が全て頭の中に入ったとしても、それらの方程式からなる問題空間がどういう形をしているのかについて、実感が湧く段階には、なかなか至ることができません。
付属のビジュアライザを通して実感を得手も、実感が充分かどうかは分かりません。
何より、他のライバル達は、同じ段階の実感を得ているのです。
同じ段階の実感を得ているもの同士が戦えば、より能力が高い方が勝ってしまいます。
それは、低い能力を補って戦うマラソンマッチ本来の戦い方ではありません。
能力が低くても有利に戦える第一歩目が、ビジュアライザの自作（もしくは改造）です。
何を表示すれば、問題空間に対しての理解がより深まるのか？ それをよく考えることです。
そうして、ビジュアライザへと少しずつ表示を追加していきます。場合によっては、新しい表示項目のために、古くて理解し終えた表示を消すこともあるかと思います。
ビジュアライザへの表示の追加は、それ以降のあらゆる段階で行う可能性があります。
ビジュアライザに表示の追加を行うことで考えるための情報が増える場合は、迷わずそれを実行して、問題空間に対しての理解を少しずつでも確実に深めていってください。
なお、ビジュアライザ自作に関しては、私よりも診断人（ @nico_shindannin ）さんの方がより前衛的な取り組みをしています。
回答状況を効果的に表示するだけではなく、ビジュアライザ上で、回答の一部を修正したら点数がどのように変化するのかということを、逐次、GUI操作に合わせてシミュレートするプログラムです。
こういうプログラムを運用できれば、更に問題空間への理解は深まることでしょう。
２．判断基準を明確にする
会社では、上流工程が終わったら、下流の開発に入って行くことと思います。
ところで、マラソンマッチの進捗具合について、どのように評価しますか？
そもそも、マラソンマッチ全体の工数をどうやって見積もりますか？
マラソンマッチでは、期間が定められています。
その期間に間に合わなかった分については、間に合わなかった成果物が最終評価となります。
どうせ時間の全てをマラソンに費やすのだから、工数なんて見積もるだけ無駄無駄？
果たして本当にそうでしょうか？
それでは闇の中でがむしゃらに走っているのと同じではないですか？
典型的なデスマーチなのではないでしょうか？
本項では、AとBの２つの実装がある場合に、どちらがより優れた方法であるのかということを、明確に比較する方法について述べます。
その延長線上として、何位を目指すためにはどのぐらいの工数がかかるのかということについて、大雑把な見積もりを立てる指針を示します。
もしかしたら初期段階では、１位を目指すための工数は見積もれないかもしれません。
それでも多くの場合、この工数の作業をすれば、どのぐらいの順位になるのかの予測が立つことがほとんどです。
その方式の延長線上の方法で、目標順位に届くのか？
届かないのだとすると、根本的な考え方を改めなければならないのだろうか？
そういうことを考える指針になればと思います。
貴方が開発者ではなく、トラブルシューティング部隊に所属していたとすると、本項で行っていることにより近いものを経験済みかもしれません。
問題が起こっているサーバー上などに計測プログラムを導入することがあるのではないでしょうか？
計測プログラムを導入する目的はなんでしょうか？
１つ目は、サーバーで何が起きているのかを調べるためですよね。このこと自体は問題の把握につながります。
しかし計測プログラムの導入は、問題がどの程度解決に近くなったかを数値的に把握するための基準の構築でもあるのではないでしょうか？
その部分が、本項で目指す所に近いものがあります。
テスト環境の構築
付属のテスタをボタン１つで実行可能な環境を構築しましょう。
たいてい、バッチを組むことになると思います。
調査段階では、テストケースは４つぐらいしか使わない、という場合も多いです。
それは、１つ１つのテストケースの問題を解くプロセスを追って行く必要があるからです。
中盤以降では、TopCoderサーバーでの暫定スコアが気になる様になります。
実は、TopCoderサーバーの暫定スコアを基準に解法の改善を行ってはいけません。
暫定スコアで使用される問題と本番で使用される問題は、イコールではないからです。
何らかのテストケースで評価し、その評価に基づいて解法を改善していく時、用いたテストケースに対しての過剰最適化が発生します。
それは、本番評価に対する改悪である場合が多く発生し得ます。
過剰最適化は、テストケース数を増やすことで緩和することが可能です。
さて、多くの場合に、暫定スコアは１００問程度で算出されます。
そして本番スコアは１０００問程度で算出されます。
（試合によって違うことがあるので、よく確認して下さい）
指数的な中間地点である３００問ぐらいが、ローカル環境での評価に用いたいテストケース数の目安となります。
もちろん、３０００問ぐらいのテストケースが使えたなら、それに越した事はありません。
１万問のテストケースを使うのは、ちょっとやり過ぎかなぁという印象です。
なお、CPUが4コア（ハイパースレッディングなし）の場合、テストを同時に動かすプロセス数は３つ程度に留めましょう。（スレッドの連続実行の安定性を保つためです）
また、予め本番環境のCPU性能を確かめておいて、テスト環境ではそれに合わせて制限時間を調整すべきです。（たとえばうちのPCの場合、本番環境の２倍以上の性能が出ている様なので、ローカルテスト環境では制限時間に0.4をかけて実行しています）
部分問題の基準構築
１万問のテストケースはやり過ぎだと書きましたが、そうではない場合があります。
問題のパラメータ範囲によって、問題空間の性質が大きくことなる場合が存在します。
たとえばMM71（上質な多角形）では、空間中の点の数が50から5000となっていました。
点の数が50の場合と5000の場合とでは、用いることのできる解法に差が生じます。
もしもこの問題が50〜5000までの均等分布であったなら、50〜500付近のテストケースは割合的に１割しかないので、ほとんど無視できたでしょう。
しかしMM71では、50〜500の割合と500〜5000の割合が等しくなるように問題生成されることが問題文に明記されていましたので、両方の対応を行う必要が生じました。
こういう場合、解くアルゴリズムを別々に用意することもあります。
こうして独立するアルゴリズムを別々に用いる場合、それぞれの評価も独立して行われるべきです。
では、テストケース数は、どうすれば良いのでしょうか？
全体テストケース数が３００のとき、部分問題のテストケース数は半分の１５０でしょうか？
では、１００個の部分問題に分けることができた場合、各部分問題のテストケース数は３つずつになるのでしょうか？
ここでもまた、過剰最適化の問題が発生することになります。
過剰最適化を回避するためには、部分問題でもそれなりのテストケース数を用意する必要があります。
私はMM69 ( TCO11 Round 1) において、問題空間を27個に分割しました。
同一のアルゴリズムを用いますが、各々に違う初期パラメータを与えることを決定しました。
このとき、各部分問題空間において、300個ずつのテストケースを使いました。
すなわち、8100のテストケースを用いました。
アルゴリズム調整の段階で用いたテストケース400個と、部分問題に対するテストケースには重複がないので、計8500個のテストケースを導入したことになります。
走らせた総テスト回数は、60万回を超えました。
点数モデルの脳内構築
貴方の解は、次の改良を加えたときに、どの程度の点数がアップし、順位的にはどの辺になりますか？
この問いかけに、可能な限り明確な答えを用意できる様にしましょう。
初参加で２位を取ったMM68でも、２度目の参加で１位を取ったMM69（TCO11 Round 1）でも、私は最初の本格的なサブミットを行う前の時点で、かなり上の方の順位を取れることが分かっていました。
パターンとしては３つあります。
１つ目は、本番環境では制限時間内に収まらない解法を、ローカルテスト環境で評価した結果として、何点を獲得可能なのか事前に分かっている状態で高速化を検討している時。
２つ目は、問題に書かれた得点算出式から、どういう解を提出すれば、全体の何割程度の点数が取れるのかが、明白である場合。
３つ目は、何度か重ねた改良結果の点数の上昇具合から、今回の改良がどの程度の点数を上昇させるかの予測が勘で分かる場合。（多くの場合、「これでは足りない！」と予測される改良を、改良候補から除外するのに便利です。この辺については、反復の項でも説明します）
３．反復期間を短くする
前述までの内容で、「どう解くのかをどういう手順で考えれば良いか？」「それを解いた時にどのぐらいの順位になるのかをどう見積もるのか？」について、分かるようになったことと思います。
（前項まででも、具体的なアルゴリズムについては一切述べてないので、そこは各自で勉強してくださいね）
最後に、それらを踏まえてどのように反復を繰り返していくのかについて述べます。
周辺技術の調査
問題空間への理解が深まって来たら、その解法について、自然と思い浮かぶのではないでしょうか？
その解法は、時間内に計算が終わりそうですか？
ぶっちゃけ、ギリギリのラインについては、やってみなきゃ分からない所も多いです。
しかし、明らかに時間内に処理が終了しない解法は、しっかりと把握しておくべきかと思います。
多くの場合にアルゴリズムの計算量（オーダー）の話になることが多いです。
最悪の計算量は無視して、平均の計算量で判断した方が良いかと思います。
（最悪の計算量は、少し工夫を加えることで、平均の計算量と同一にできる場合が多々ある様です）
ネットを検索したり、関連の書籍を図書館から借りて来るなどして、先人の知恵を借りつつ、試合内容に合う様に使うにはどうすれば良いかを考えましょう。（その過程で勉強することは、次回やその更に先のマラソンマッチでも役に立つはずです）
なお、定番探索で解ける問題も数多く存在します。
定番の探索法については、他の人の記事を探してみてください。
プロトタイピング
ようやく実装に入ります。
試合期間は２週間ですが、だいたい１回の反復は４時間以内に収まることを目標にすべきです。
新しい案を試したら、どのぐらいの順位が狙えるのか？
前述の点数予測だけでは細かく分からない場合に実施するのが、プロトタイピングです。
与えられた時間は４時間程度と仮定しましょう。
４時間で、そのプログラムの点数算出に最も関連する部分だけを実装するのです。
できませんか？
できなかったら、もっと実装案を簡略化してください。
大枠の点数の方向性が失われない範囲で実装案を簡略化していきます。
プロトタイピング段階では、処理時間は別に１００倍ぐらいは普通にかかっても良いものとします。
本番環境で反復をしなくても良いのです。そのために、ローカルにテスト環境を構築しているのですから。
あるいは、部分問題についてのみの解法であっても構いません。
（点の数が50〜500なら時間内に計算可能。しかし点の数が5000になると一生待っても結果が出ない……とかであっても構いません）
そういう風に、条件を緩和することで、視野の外だった解法が視野の内側に入ってくることが多々あります。
それらの中で、将来性が高そうなものから順に、実装してみましょう。
なお、プロトタイピングではあまり速度にこだわった実装は行わなくて構いません。
後述の高速化の手順を実施する際に、オーダーミスは必ず浮き彫りになって改善することになります。
また、定数倍的な遅いコードも、高速化の後半で改善することになるので、あまり神経質にならなくて良いのです。
解法の構成
解法って、１アイデアで解けるものでしょうか？
実は、色々な解法を試すにしても、どの解法を使っても基本構成は同じだよね……というパターンになることが多々あります。
それらは早い段階で意識しておきましょう。
構成が固まれば、プログラム全体の差し替えではなく、一部分の差し替えで色々な解法を試すことができる様になります。
寄せて行くノウハウ
さて、上位は狙えそうでしょうか？
簡単に狙えそうにない間は、プロトタイピングを延々繰り返していくことになります。
狙えそうになってきたら、本当に狙えそうかどうかをきちんと評価して、これで勝てると思ったら、後は寄せていくだけです。
寄せは２種類あります。
速度面の寄せと、精度面の寄せです。
速度面の寄せとは、制限時間をオーバーしてしまうけど、そこから予測される順位に満足している場合に行う高速化です。
高速化については付録の別項を設けましたので、そちらを参考にして下さい。
単純な高速化では、とても制限時間内に収まらなさそうな場合は、精度と速度のトレードオフを実施するためのプロトタイピングを行って下さい。
精度面の寄せの場合、大筋では今の解法で良いけど、もうちょっと点数を伸ばしたいという感じでしょうか。
解法の改良については、前述のプロトタイピングでなんとかしてください。
局所解に陥らない様にする様な工夫の多くは追加計算時間を要しますので、プロトタイピングを試した後に、速度面の寄せに入るパターンは良く在ります。
初期パラメータの最適化については、問題空間の分割と、部分問題のテスト環境構築を参考にして下さい。
以上で、マラソンマッチで直面するあらゆる状況に対しての、考え方の指針を網羅できたのではないかと思います。
あとは付録なども参考にしつつ頑張って下さい。
付録 テクニック的なこと
高速化について
ここで取り上げる「高速化」というのは、改良前後のプログラムの結果が完全に一致するものを指します。
貴方のプログラムは、どこを改良すれば、速くなりますか？
試行錯誤してみますか？
よく考えて改良したつもりでも、全然処理時間が縮まらないことはないでしょうか？
まずは、そんなあいまいな方法で高速化に取り組むこと自体が間違いであることを知って下さい。
貴方が高速化しようとしている部分は、１テストケース辺り、0.001秒しかかかっていない箇所かもしれない。
そんな場所をいくら高速化しても、無駄です。
プロファイラを使いましょう。
入手方法や使い方等は、ネットで調べて下さい。
プロファイラを使えば、必ず、その時に最も処理時間がかかっている処理にぶち当ります。
処理に時間がかかっている箇所というのは集中しているもので、それが最頻ループの最下層にあたることが経験的に分かっています。
最頻ループのオーダーを下げる方法を考えて行くことになるでしょう。
序盤は、そういうオーダーミスを直したり、分岐を減らすパターンが多いと思います。
中盤は、コンテナの使い方とメモリの確保と解放を減らしていくことになると思います。
後半になってようやく、割り算を掛け算になおしたり、平方根演算の除去を行ったりすることになります。
ローカルテスト実行時に追加情報を与える
テスト実行時に、解法プログラムに対して、問題番号や問題生成時に使ったパラメータ等を渡す様にします。
バッチで指定したり、あるいはテスタのコードを書き換えることで、これらは可能になります。
問題番号はリポートファイルのファイル名に使うことができます。
問題生成時のパラメータは、問題解決に役立つかもしれません。あるいはリポートへの埋め込みとか。
問題生成時のパラメータは本番時には用いることができませんが、問題空間の解析等を行っている段階では、それらが有用なことが多々あります。
それから……制限時間に関して、本番環境とテスト環境とでプログラムをいじるのは、間違いの元になります。
そこで、制限時間はグローバル変数などで定義しておいて、ローカル環境ではmain関数（プログラムのエントリポイント）付近で、グローバル変数を書き換える様な方法があります。
また、C++等では条件コンパイルを用いる方法もあります。
枝刈りを観測的に行う方法
探索を行っていると、処理時間がかなりオーバーしてしまうことが多々あります。
そういう時に、枝刈りが効果的な場合があります。
枝刈りで精度が落ちることはありますが、それでも速度が大幅に改善されて上位が狙えることもあります。
ところで、精度にほとんど影響を与えない枝刈りって、どうやれば良いんでしょうか？
わりと万能な方法というのは、ネット上を探せばいくらか見つかるかもしれません。
しかしマラソンマッチの場合、問題空間はもう決まっているのですから、その問題空間でだけ使える様な枝刈りを行っても良いはずです。
それを見つけるための、そこそこ万能的な手順があります。
葉ノードまで探索した際に、使い物にならない解だった原因は何でしょうか？
それを、葉ノードで使い物にならない解が分かった時点で、調べます。
（使い物にならない解の定義は、現在の最適解と比べて大幅に劣るもの……などとします）
原因をいくつかの種類に大別しておき、それぞれに対応したカウンタを１つ進める様にします。
複数の要因が重なっている場合は、それら複数要因が重なった場合だけに増やすカウンタを用意し、その条件が当てはまる時には他の個別の要因のカウンタは増やさないことにします。
なお、これらのカウンタは、使い物になる解の場合のカウンタも、同様に用意しておきます。
とても時間のかかる探査を行ったプログラムは、最後に、各カウンタの値を出力します。
何が要因で、使い物にならない解が探索されやすいかが、これで分かるのではないでしょうか？
また、探索時に各ノードは親ノードに対して、使い物になる解が１つでもあったのか否かを報告する様にします。
すると、葉ノードではなく中間ノードでも、上記の計測が可能になります。
そうやって得られた情報を元にして、枝刈り条件を考えてみてはいかがでしょうか？
より複雑な点数モデル
MM71では、各テストケースの点数そのものではなく、各テストケースごとの全体順位の位置が、暫定スコア及び本番スコアでの点数として採用されました。（そのテストケースで1位なら1点、最下位なら0点、真ん中なら0.5点、のような感じです）
MM70及びMM72では、各テストケースごとの全体の最高点を基準としてスケーリングされた点数が、暫定スコア及び本番スコアでの点数として採用されました。（MM70の方は少し特殊なゲーム展開になりましたので、以降、MM72方式と表記します）
MM74では、全体の最高点を基準としてスケーリングされた後に４乗された点数が、暫定スコア及び本番スコアでの点数として採用されました。
MM71方式はちょっと複雑で、初期から参加してこまめに周囲の動向を確認できていなければ、脳内点数モデルを構築するのは難しいです。
かく言う私も、MM71の時は点数予測を大きく見誤りました。
と言っても、各参加者の過去の点数が、現在の分布基準で算出されたものではないということに気付けなかったのが大きな敗因です。
複雑な点数モデルでは、最新の回答は、常に最新の状況によって更新され続けます。
各参加者の過去の点数が、現在の状況によって更新されるものなのか、そうでないのかは、確認しておくべきかと思います。
さて、ちゃんと前提条件が把握できていたとすると、MM71の方式であっても点数予測を行うことは可能です。
私の知る方法としては、現段階の自分の最良解と０点解の提出の比較を行う方法や、部分問題ごとの分割送信での比較などがあげられます。
順位に依存して点数が決まるということは、こちらの回答がAからBへと切り替わった時に、回答Aと回答Bの中間に位置する回答を行っている人達の点数は変動します。
これを利用します。
最適解と０点解を切り替えても、点数の変動が起こらない方々……その方々は、雲の上の人達なので、測定不能です。
点数の変動が起こる方々は、テストケースによっては、こちらの方が上回っているということになります。
全体の競技者人数から、１人の順位の前後が入れ替わった場合に、何点が変動するかは、容易に計算可能です。
その変動が何割のテストケースに対して起こったのかを、各参加者ごとの点数変動から推論することが可能です。
次に、この調査に部分問題解を使うことで、上記をより細かく調査することが可能になります。
特定の部分問題ではちゃんと回答し、それ以外では０点の回答をするプログラムを送ります。
このとき、部分問題に該当するものが、全体の何割程度であるのか、問題生成の分布から計算可能である必要性があります。
それで、自分の部分問題ごとのおおよその順位を知る事ができる様になります。
どの部分問題を改良することで、全体の順位が上がり易いのかが、分かる様になります。
MM72方式及びMM74方式では、テストケースごとの順位制ではないので、少し状況が変わってきます。
点数の切り換えで点数の変動を見るのは、自分だけが最高得点を取っているテストケースが存在する場合にしか使えません。
しかし、部分問題提出法は、依然として有効です。
MM71よりも点数算出方法が明快なので、この辺は自分で考えながらやってください。
なお、MM74方式ではMM72方式に対して４乗の計算が加わります。
これがどういうことかというと、最適解の70%しか取れていない解は、25%程度の点数しか取れないということになります。
つまり、全ての各テストケースで70%ずつを取ると、総計結果としては25%になります。
ところが、半分のテストケースで100%の点数を取り、残りの半分のテストケースで0%を取ると、総計結果としては50%になるのです。
こうした問題では、部分問題ごとに確実に100%近い点数を目指す方が有効な場合もあります。
また、試合の途中段階において、一度、部分問題解を提出しておいて、自分の回答はどの部分問題解が得意で、どの部分問題解は不得意なのかということを、調べておくのが望ましいでしょう。
なお、マラソンマッチでは、１度サブミットすると２時間待たなければ次のサブミットができません。
現に、こういう方法があることを事前に知っている私は、MM74の問題文を読んだのが試合終了2日半前だったため、上記方法を試す事ができず、部分問題の得手不得手を測り間違えて、最後の５時間ぐらいを迷走してしまいました。
（部分問題が２つに分けられる場合、３回のサブミットが必要なので、６時間……更に最終サブミットが必要なので、試合終了８時間前の時点では既に使えない手段になってしまっています）
時間に余裕を持って、自分の現在位置を把握する様にしましょう。
最後に
書きたいことは山ほどあって、それらをがむしゃらに書いた所、こんな長くて締まりのない内容になってしまいました。
本内容は、主に、社会人がエンジニアとして働く上で、自然と身に付いているだろう事柄に対して、焦点を当てて書きました。
従って、社会人プログラマの皆さんに対して、「ほら貴方も、上位が狙えるんじゃない？」ということを全面に押し出しては書きましたが、逆に社会人の方々にとっては当たり前すぎる内容しか書けていないかもしれません。
逆に、あまり対象としたつもりのない学生の競技プログラマの方々に対して、重要なヒントを提供している内容になっているかもしれません。
今の競技プログラマ人口は、学生の方が圧倒的に多く、社会人人口は少なめだと感じています。
実際、社会人になった後にSRMに入門しても、あまり高い成果は望めないのではないかと感じている面もあります。
しかし、プログラミングを競うというのは、面白いものがあります。
実際にはプログラミング自体ではなく、数学的な考え方やマネジメントスキルが大半を占めますが、それでも競争社会というものが私は大好きです。
SRMは社会人向けではないかもしれません。
しかし、マラソンマッチは社会人にとても向いている競技だと感じています。
社会人の競技プログラミングが、もっと市民権を得ることを、切に願っております。 server Longregbiguates .
[…] 今回成績良かったのは、単純に時間を多く割けたこととか、問題と相性が良かったこととか、colunさんの記事等で事前にある程度心構えができてたことが大きかったと思います。方針もちょっとまぐれ当たりっぽかったかな。 一方、反省点としては終了直後に感じたこのへんがメインかなと。 […]