競技プログラミングにおけるマラソン系コンテストの楽しみ方

競技プログラミング

Last updated at 2018-12-24Posted at 2018-12-24

フューチャーアーキテクト Advent Calendar 2018の21日目¹の記事です。

競技プログラミングにおける所謂マラソン系のコンテストについて、弊社主催のコンテストを例にその楽しみ方について紹介します²。

マラソン系コンテストに肩まで浸かったことのないあなたへ

　本記事は、AtCoderを始めとする競技プログラミングがどんなものか知っている/やったことがあるが、マラソン形式をやったことがない/何が面白いのかわからなかったという人に向けた記事です。「そもそも競技プログラミング…とは？」という方は、弊社の競技プログラミング部メンバーが書いた記事³を一読下さい。

社会人からはじめる競技プログラミング

　なお、この記事ではマラソン系コンテストの楽しみ方に焦点を当ててます。本来成績を追い求める場合には悪手と考えられるポイントについても積極的に触れ、ハマってる人が何にハマっているのかその魅力が伝われば幸いです。さぁ、どっぷり浸かりましょう。

マラソン系コンテストって何するの？

　一般的な競技プログラミングでは、与えられた制約を満たす出力を行うプログラムを作成し、オンラインジャッジのテストケースを全てクリア(AC)すれば、決められた点数を得られます。その制約では、もっとも小さい/大きい値等、解が一意に絞られるよう厳密なものが多くなります。また、同点者も多数出るため、基本的には早いもの勝ちのルールです。
　一方、マラソン系コンテストでは制約に遊びがあり、また得られる点数も可変です。可変の点数のため同点者が出ることは少なく、なるべく高い点数を取る部分に競争ポイントが集約されています。また、基本的にコンテスト時間が長めのものが多く、一定の実装量も求められるため、コーディング以外のスキル（データ分析・スケジューリング・開発環境整備等）も鍛えられます。
　出される問題も難易度の高低があるわけではありません。もちろん、とっつきやすい/にくい問題はありますが、競プロerであればACを取ることには苦労しないため、幅広い方が同じ問題に挑戦できることもマラソンの魅力です。具体的な問題内容を知りたい方は下記コンテストをご覧下さい。

　本記事では、そんなマラソン系コンテストの楽しみ方を下記のポイントに絞ってお伝えします。

点数を楽しむ
visualizerを楽しむ
感想戦を楽しむ

点数を楽しむ

　より高い点数を取るコンテストなので、点数に関して楽しむポイントはたくさんありますが、次の3つの視点から紹介します。

1. 自身の点数を楽しむ

　競プロerである以上、自身の点数を少しでも上げようともがきます。作成した以前のプログラムを改良するアイディアはないか頭をひねり、思いついたアイディアを実装、より高い点数を取れるようになったか手元で検証して、確認が取れたらsubmit、順位表を変動をドキドキしながら待つ、この一連のサイクルをコンテスト中は繰り返すことになります。手元検証時に明らかに高い点数が取れることがわかりニヤニヤが止まらなくなり、submit後に大きく点数が改善し順位表から自分の名前を見失う、そんな経験も味わえます。
　また、厳密解を求める形式ではないことから、ヒューリスティックなアルゴリズムを採用することも多く、プログラム中に指定したパラメータ値によって結果変わる時も多々あります。そのパラメータを変えるだけで点数が上下し、ある程度運要素も絡むため、パラメータを少し変えては点数を確認、またパラメータを少し変えては点数を確認、…という行動で多くの時間を溶かしてしまうこともよくあります。（私も数十のコンテストに取り組んで来ましたが、未だにパラメータ調整にハマってしまいます。）

2. 他の参加者の点数を楽しむ

　他の参加者、特にライバル視している人の点数は気になる所です。点数自体もそうですが、その人の提出回数・提出時間も表示されているため、細かい変更を何度も繰り返しているのか、随分前に提出したきりなので何か大きな変更を加えているのか等々、早く自分のプログラムを改良しないといけないのに、順位表をじっくり見てしまうこともしばしばあります。
　時には、順位表から方針が読み取れることもあります。下記のように同一点数が並んでいる場合、単純な方法で一定の点数が取れる方法があると考えられます。もし、自分がまだそれに気づいていないのであれば、例えより高い点数が取れていたとしても、その方法を知ることで新たな気付きを得られます。もちろん、当然トップとの点数の差は大きな情報です。

　また、弊社主催のコンテストではなぜか最低点勝負が盛り上がる文化があり、こちらも楽しみのひとつとなっています。

3. コンテスト後の点数を楽しむ

　AtCoderのシステム上、開催の終わったコンテストでもチャレンジすることが可能です。順位表は変化しませんが、コンテスト開催期間に試せなかったことを試している人も多いです。HTTF2018予選では、コンテスト中の最高点が約9.998×10^9だったこともあり、コンテスト後に9.999×10^9超えを目指す参加者が何人かいました。まさにエンドレスでコンテストができますね。

visualizerを楽しむ

　次はvisualizerの楽しみ方を紹介します。一般的な短時間で複数問の厳密解を求めるアルゴ形式ではあまり見ない仕組ですが、マラソン形式では公式が簡易なものを用意していたり、競技者が独自で作成したりします。これは、そもそもの問題内容について気付きを得たり、最適化の余地を探るために用いられます。コンテスト中にアイディアが枯渇してしまった時、じっくりとvisualizerを眺めてアイディアの種を探すことも多いです。

　文字情報中心の競技プログラミングでは、その楽しさをなかなか伝えられないと悩まれている方も多いかと思いますが、visualizerはゲームのような見た目も多く、見るだけでなんとなく楽しいものです。さらに、実際の問題を理解した上で見ると、そのプログラムの方針や差異が見えてくるため、問題理解や復習にも役立ちます⁴。

感想戦を楽しむ

　アルゴ形式のコンテストでも盛んですが、コンテスト終了後にその解法について情報交換や所感をつぶやく、感想戦が始まります。先の通り、マラソン形式ではその制約の緩さから様々な解法が可能で、各人の気付きや試したもの・捨てたもの等、有益な情報を得ることができます。また、コンテスト中は一定の長さがあるため、心情の吐露が行われることもしばしばあるのですが、その内情が判明するためドラマ性があります。「マラソン何もわからん。」はマラソンランナーであれば一度は思ったことでしょう。
　リアルタイムならではの醍醐味ではありますが、下記のようにtogetterにまとめて下さる方⁵もおられます。マラソンの雰囲気に触れたい方は覗いてみて下さい。

最後に

　ここまで読んで頂きありがとうございました。競技プログラミングがメジャーになる中、まだまだ少ないマラソン形式のコンテストの楽しみ方について少しでも伝わり、一人でも多くの仲間ができれば嬉しいです。そしていつか、AtCoderでratedのマラソン形式コンテストが開かれる日を心待ちにしています。

筆者の年齢++。投稿遅れて本当に申し訳ありませんでした。 ↩
マラソン問題の解説記事を上げておきながら、紹介記事を上げていないことに今更気づいた…。 ↩
こういった記事は何度読んでもいいですね。 ↩
SNS映えするので、みんな大好きTwitterでもいいねが稼ぎやすいです。
　HTTF2018本線のvisualizerでは特に方針の差異が現れやすい問題でした。興味のある方は、上位者の出力結果を上げているため是非動かして見て下さい。 ↩
agwさんまとめて頂き大変感謝です。 ↩

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up