こんにちは。部活以外で家から一歩も出ない冨井です。
突然ですが、僕はマラソンが大好きです。
お前はフルマラソン走ったことないしハーフでさえ3月に一度走ったきりじゃないかって？違います。僕がここで言っているのは競技プログラミングの種目、「マラソンマッチ」です。
競技プログラミングについては去年の夏合宿の報告会でも紹介したりしました。1~2時間くらいの時間と数問の問題が与えられ、それらを解くプログラムを出来るだけ早く、多く作成するという競技です。
実はこの説明は不正確なんですよ。というのも、これは競プロの中でも「アルゴリズム系」のコンテストの説明です。対して「マラソン系」コンテストはどのような特徴があるかと言うと……
・コンテスト時間（提出可能期間）は数日～数週間程度
・最適解を求めるのが非常に難しい問題が（大抵は）1問のみ与えられる
・「出来るだけ良い解」ほどスコアが大きい（「〇完」という概念は無く、連続的な点数で評価される）
などなどです。
具体例を挙げてみましょう。
先に、アルゴリズム系の問題の例を見てみます。
ゲームをプレイする気持ちになれば、残っているカードのうち書かれている数字が最も大きいものを選んでいくのが最適なことは分かります。
よって、数列Aを大きい順にソートし、前から奇数番目ならAliceの得点に、偶数番目ならBobの得点に加えれば答えが分かります。
当然ながら、答えが±1でも違っていたらこの問題の得点は0点です。センター試験と同じです。きっちり正確な答えを出さなければ意味がありません。
次に、マラソン系の問題の例を見てみます。
有効な解のひとつをビジュアライズしたものをkosakkunさんより拝借します。イメージが掴みやすいと思います。
ここでは真に最適な解を出すことは求められていません。出来るだけ少なくしたいだけです。でも、いざプログラムを作ると何から手をつければいいのでしょうか？
マラソンに慣れないうちは、まず最初に「正の点数を出す」ことを目標にするとよいです。例えばこの問題であれば、それぞれの点の座標を中心にしてその数だけ円を置きまくってしまえばよいでしょう。これなら確実に漏れなく覆えますね。もちろんたくさん無駄があるので良いスコア、良い順位にはなりませんが、ちゃんと全ての点が覆われてさえいれば、これも確かにこの問題の答えの1つとして認められます。
ここから少し進んだ話をすると、次は「山登り法」という手法が使えます。マラソンだの山登りだの面白いですよね（ちなみに「コードゴルフ」という競技もあって、これも僕は大好きです）。
山登り法は、何かしら正の点数を得るような解が求まっている時に、そこから適当に少しだけ答えを弄ってみて、スコアを計算してみて、弄る前よりスコアが良くなっている（かつ有効な解である）ならそのまま採用、悪化してしまったなら取り消し、という作業を時間いっぱい繰り返す手法です。この問題で言うと、置いた円をランダムに1つ選んで消してみるとか。消したことで覆えない点が生まれてしまったなら無効な解になってしまうので取り消すようにすると、確実にスコアが良くなっていきます。
思想を日本語で表すならまさに「駄目で元々」ってやつです。これを繰り返すと、スコアは良くなっても悪くなることは絶対にあり得ません。やればやるだけ得です。問題にもよりますがこの手法を取り入れるだけで全体の上位になれることもあります。
本当は焼きなまし法とかビームサーチとか面白い手法がまだまだあるのですが、既にだいぶ長くなってしまったのでこれくらいにしておきます。コードも特に示しません。
おまけ
界隈を見ていると、マラソンマッチが好きな人はリアル長距離走が好き/得意な人が明らかに多いように見受けられます。何故でしょうかね？ひとつ考えられる理由としては、コンテスト中ひたすらあくせく手を動かし続けるアルゴリズム系コンテストに比べるとマラソンマッチはのんびり自分の中でペース配分をしながら取り組めるというのが大きそう。
アルゴリズムはいくら考えても脳の回転速度と解法の引き出し（最大筋力）が無ければどうにもなりませんが、点数が連続的なマラソンは基本的に、実力の無い人でも時間を掛ければ掛けるほどそれが順位に反映されます。成績に占める根性の割合がすごく大きいです。世界トップレベルのレッドコーダーに1時間が、青コーダー（数回参加した初心者）に10時間が与えられたら、たぶん後者が勝ちます。これって結構すごいことです。才能が無くても、数倍の努力を注ぎ込むだけで世界のトップと張り合えるのです。ちなみに僕はこの記事の執筆時点でTopcoder Marathon Match 黄コーダーになっています。（activeな中で世界上位100位くらい）
走るだけ強くなれる長距離走そのままですね。陸上競技でも、人並み以上の努力で才能に打ち勝つ選手を目指していきます！
次の記事は主将の荻野先輩どうぞ！
0コメント