こんにちは、NOSSです。
この度、卒業されるM2の方の追いコンを開催しましたのでその様子を紹介します。

追い出しコンテストとは

世間一般では「追いコン」は「追い出しコンパ」(いわゆる飲み会)のことを指します。

しかし、誰かが「追い出しコンテストでは？」と発言したのをきっかけにコンテストが開催されることになりました。
とても競技プログラミング部らしくて僕は好きです。

会場

貸会議室を借りてそこでオンサイト的に集まってコンテストをしました。

追いコン(テスト)会場です pic.twitter.com/yxJLy1ZP4c

— 横浜国大 競技プログラミング部 (@ynu_cpc) March 17, 2019

コンテスト

コンテストへのリンクはこちら

コンテスト時間は2.5h。

問題セットはOBの方に組んでいただきました。

コンテスト開始

A問題は約数の個数を数えるような問題でした。制約がとても小さいので全探索ができます。FA¹はpuniさん(00:04)

B問題は与えられた文字列に目的の文字列が含まれているかどうか検索するような問題でした。全探索ができる制約なので落ち着いて実装します。FAはpuniさん(00:11)

C問題。ここで手が止まりました…

15分経過

C問題はいわゆる「素数砂漠」を求める問題でした。長さ$N$以上の素数の存在しない区間を探す問題なのですが制約の$N \le 1500$が大変で$10^7$程度まで実験しても長さ$100$程度の素数砂漠しか見つかりません。制約に__値は5000桁を超えていけない__と書いてある時点で相当大きい数にならないと解がなさそうと見て僕はCを諦めました。

D問題を見てみるとそれらしい貪欲解法が思いついたので投げてみます。すると…WA。 いくら考えても貪欲の反例が見つからなかったので順位表を眺めていると、

WA

WA

WA

…

他のCを飛ばしてDを解いていた方の提出がことごとくはじかれている光景がありました。

これはDも罠だなと思いDも一旦諦めることにしました。

30分経過

ここで突然、F問題が追加されます。E問題もZ問題も解けそうになかったので一応Fを確認します。

F問題は数直線上をある制約下で0からxまで移動するときの最小コストを求める問題でした。
グラフの最短経路問題のような見た目をしているなと思い、うまく落としこめないかなと考察するといけそうだったので実装を始めます。

(この間にもDのWAが大量に提出されていました…)

1時間経過

なんとC問題の解答者が現れます。FAはニクローさん(00:51)。
正直のところ解けない問題だと思っていたのでかなり驚きました。会場全員がざわつきます。
曰く、「これはGoogle力が必要」²。僕はすべてを察しました。

ようやくFの実装が終わったので提出するとAC！ FAはNOSS(01:02)

さすがにDの嘘が提出され過ぎてhackケースが全体共有される案件が発生しました(非公式の身内コンテストならではのことです)。hack解を聞くと天才だったのでやっぱりDは無理かなという気持ちになりました。

1時間半経過

mhrbさんがFを通して全体がおお、みたいな感じになっていると、
「これは順位表から得られる情報なのですが、Aを通していません」と言って、え？
ほんとにAが通していなかったのでF解けてA解けないことあるのかと。
10分後にはちゃんとAを通していました。(無限ループでバグっていたそうです)

僕は「素数砂漠 検索」をしてこのサイトを見つけたのでこれを埋め込むかなあという気持ちになっていました。あとは多倍長が使えるpythonで答えを書き出すだけだなと思いバックグラウンドで実行させます。

この間にmhrbさんがCを通して1位に浮上しました。僕はまだpythonの実行が終わっていなかったので意味が分からず何もわからないという気持ちでした。

2時間経過

なかなかpythonの実行が終わらないので高速化できないかなと思いました。そこで安易な気持ちでエラトステネスの篩を$10^9$オーダーの配列で実行しようとしたらPCが固まりました。10GBオーダーのメモリが必要なのでたぶんメモリを食いつぶしてしまったんだと思います。泣く泣く再起動しました…

コンテスト終了

結果はmhrbさんがABCFの4完で一位でした。

結局Dは誰も正答できず全体で10WA以上吐くという虐殺問題でした。

コンテスト後は解法を話し合ったりしていました。D問題がそれぞれ思い思いの貪欲をしていて面白いなあと思いました。全体のいいとこどりの解法でACできたらしいのでチーム戦ならワンチャン解けてたかな？
あとmhrbさんのCの非埋め込み解法が天才だったので負けです。

追い出しコンパ

そのあとしっかりコンパのほうも行いました。競プロerの飲み会すごく平和で楽しいのでいいですね。先輩方の研究室の話が聞けたりTeXはいいぞと勧められたりしました。totoさんが突然「D問題の証明を思いついたかもしれない」と言って紙に数式を書き出したのは流石だと思いました。

総評

部として初めての追いコンでしたが僕はとても楽しめました。
追い出しコンテストという概念、広がってほしいです。