Hatena::Grouptopcoder

yowa の TopCoder 日記

TopCoder yowa / twitter: @yowa

2014-12-07

マラソンマッチで1位になる方法(最終順位とは言ってない)

00:04 | マラソンマッチで1位になる方法(最終順位とは言ってない) - yowa の TopCoder 日記 を含むブックマーク はてなブックマーク - マラソンマッチで1位になる方法(最終順位とは言ってない) - yowa の TopCoder 日記

この記事は Competitive Programming Advent Calendar 2014(マラソン系) の 7日目です。

おことわり

この文章は筆者がいま書きながら思いついたことを並べてる部分がほとんどであり、筆者が実践しているわけでも、確かな効果が得られることを保証するものではありません。

本文

競技プログラミングに参加する以上、だれしも「ランキング上位に入りたい」「できれば1位になりたい」と思うものです。思わない人も思うことにしておきましょう。

「とは言っても、上位に入るには相応の実力がなければ……」、そんな風に思ってませんか? でも、ちょっとしたコツで(暫定)1位が取れるんです。

そう、マラソンマッチならね。

目指すもの

1位は1位でも、暫定1位です。しかも最終暫定順位(締め切りの後、システムテストが終わるまで表示されている順位)ではなく、ほんとうに暫定的な順位の話です。

マラソンマッチは期間中、常に(暫定)順位表が公開されています。その順位表で一瞬でも1位になったら、素早く順位表のスクリーンショットを取るなり 「暫定1位だよー」とつぶやくなりして悦に入りましょう。

(SRM と比較した場合の) Marathon Match の特徴

  • 期間が長い(2週間前後)。
  • 解けた/解けなかった、ではなくスコアの良さを競う
  • 同じスコアになっても、「提出が早いほうが勝ち」などということはなく、同着扱い
  • 提出回数によるペナルティも無い*1

以上の特徴をまとめると「急ぐ必要はない」といったところでしょうか。実際に、マラソン上位常連の人たちでも最初のコード提出がマラソン開始の2,3日後というのもよくあります。

取るべき戦略

ここまでくれば簡単ですね。

「開始直後の、まだ参加者が少ないタイミングを狙う」、これです。

以下では具体的な戦略を紹介していきましょう。

戦略1. First Submit ≒ First Accept = 1位/(参加者全1人)

スコアボードの一番上に燦然と輝く自分のID。そしてそこには、自分以外の誰もいない……。美しいですね。

この戦略を取るならば当然、純粋なスピード勝負になります。

マラソンマッチはスコアを競うという性質上、WA という概念はありません。また TLE や MLE などが起きた場合でも「そのテストケースのスコアは 0 点と見做す」という扱いになることがほとんどです。

ですから、コンパイルさえ通ればそのコードは Accept されてスコアボードに乗ると思っていいでしょう。

実践例

Marathon Match 82: ColorLinker を例にとると(C++ の場合)、

  • 問題文をひらく(この時点で、問題文を読む必要はありません)
  • 「signature」でページ内検索する

以下のような部分が見つかります。

Class:  ColorLinker
Method: link
Parameters: vector <string>, int
Returns: vector <int>
Method signature: vector <int> link(vector <string> grid, int penalty)
(be sure your method is public)
  • この仕様に合うコードを書く

仕様に合ってさえすれば、返す値の中身は何でも問題ありません。

#include <vector>
#include <string>
using namespace std;
class ColorLinker {
public:
  vector <int> link(vector <string> grid, int penalty) {
    return vector<int>();
  }
};
  • 提出する
  • いそいで順位表を確認する
  • (たぶん)1位になってる

以上です。

いま挑んでいるのが何をする問題でどんな入出力が行われるのか、それさえも知らないままでのコード提出。そしてそのコードが(運が良ければ)暫定1位。背徳感でゾクゾクしますね。

勝負は試合開始前から始まっている

「運が良ければ」と書いたのには理由があります。

(以前は違ったのですが、)最近のマラソンマッチは、開始する日時が正式に予告されることは少なく、多くの人にとって「気付いたら始まってる」ものなのです。

それは、普通に参加するだけなら大した問題ではないのですが*2、今回の First Submit 戦略を取る上では大問題です。「気付いたらマラソン始まってて、他の人が既に提出してた」は、戦略の失敗を意味するのですから。

そこで、マラソンが始まりそう・始まったことにいち早く気付けるよう、常にアンテナを立てておくことが重要だと言えます。

マラソンマッチ開催を知ることができる主な情報源としては以下があげられます。

  • 開催中のマラソンマッチ一覧のページ: マラソンマッチは(日本時間)午前2時か3時*3に始まることが多いので、そのタイミングでチェックするようにしましょう。
  • マラソンマッチのフォーラム。
  • Upcoming Contests のページに、稀にマラソンの予告が(日時つきで)出ていることがあります。しかし指定された日を過ぎても音沙汰が無かったり、あるいはいつの間にか日付が変わったり、はたまた消滅していたりと、あまり信用できない感じです。
  • マラソン常連の人の TwitterTogetter のマラソンマッチまとめ*4に登場するアカウントをフォローしておけば、誰かが「マラソン始まってる!」とつぶやくのに気付けるかもしれません。ただし、目にしたそのつぶやきは、その人がすでに最初の提出を済ませた後のものだった、というのもよくある話です。

この戦略の欠点

  • 開始に出遅れたら負け
  • 仮に1位を取れても(たいてい)スコアは 0 になるのがカッコ悪い
  • というか明らかに邪道

おわりに

開幕ぶっぱ戦略、いかがでしたか?

この戦略はマラソンだけでなく、SRM にも使えるのではないでしょうか(再提出のペナルティが痛い、1位になったところで中間の順位表に注目してる人はほとんどいない、などのデメリットに目をつぶれば)。

今回紹介できた戦略は1つだけでしたが、機会があれば次なる戦略「スコア満点での暫定1位も夢じゃない? ~ちゃんとした解を提出して正のスコアを取ろう(ただし問題文はやっぱり読まない)~」を紹介できたらと思います。

ありがとうございました。

*1:一度提出したら2時間は再提出できない、みたいな制限はある

*2:それでもちゃんと告知しといて欲しい

*3:アメリカ東海岸時間(EST/EDT)の13:00。サマータイムでズレる

*4:agw さん、毎度のまとめ、お疲れさまです&ありがとう!

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/yowa/20141207