JSC2019決勝参戦記

はじめに

この記事はへっぽこ水色コーダーによる AtCoder 第一回日本最強プログラマー学生選手権決勝 (JSC2019) の参加記です。 当日の出来事を時系列順に思い出すままを綴った散(らかった)文という捉え方もあります。そういうわけなので文章まとまってません悪しからず。

なお、戦績だけ先に書いておくと、196人中183位でほぼドベ、正のスコアを得た人のうち下から2番目です。 予選通過ボーダーギリギリだったことを考えると順当ではあるものの、もう少し頑張れた気もして悔しい。

時系列順振り返り

会場まで

会場は新橋の電通ホール。駅から徒歩4分だそうだが、絶対迷子になるという確信めいた予感があったので早出することに。

京浜東北線が遅れていて朝から幸先が悪い。重ねて腹を下して途中下車。受付TLE*1あるぞこれ。

早出が功を奏して受付に間に合うが、代償に昼飯の時間を失う。食後は頭回らなそうだしまあいいか……

会場着から開会式前まで

受付で名札を受け取り、ユーザネームを書き込んで首から下げる。オフ会みたいだなあ。

受付を抜けて競技会場までの僅かな距離の間に、にっこにこしたスポンサーの人事の方？に拉致られてスポンサーブースに引きずられてしまった。各社担当者さんから大量の資料、特に VOYAGE さんからは社名ロゴの入ったチロルチョコを頂いた。昼飯！！

やっぱり学生を釣るなら飯ですよ。そういうわけなので社会人各位は焼き肉を奢ってください。

競技会場に入る。ホールであって前方にステージとスクリーンがあるということを除けば TOEIC の試験会場のようなレイアウトだった。長机が並んでいて競技者はそこに座る。試験会場と言うには前後左右の人が近すぎるかなあ。「すいません後ろ失礼します」って10回は言った。

初めてのオンサイトコンテスト*2なので、もう少しそわそわしてしまうかなと思っていたのだが、妙な安心感がある。これあれだ、abc *3の空気感に似すぎている。周りの人間全員僕より強いんだろうなーみたいなところが特に似てる(クイズよわよわ勢並感)。違うところと言えば、机が用意されていて、周りの人間がみんな TweetDeck かエディタを開いてることくらいだ。というか、プレスのカメラが周りにあるのに Deck 開いてるの度胸がすごいな。

PC 開いて電源(会場に用意されていた)繋いで、Wi-Fi(これも会場に用意されていた)のセットアップして、コンテストのために適当にディレクトリを掘って、で、何もすることがなくなったので TweetDeck を開いた。

開会式

10分ほど #jsc2019 のカラムをほげーっと眺めていたら、周りが急に静かになった。開会式が始まったらしい。

と、めっちゃテンション高い人が前で何か喋り始めた。もしかしてあの人は chokudai *4さんでは？

「わー生 chokudai 初めて見たー」「ところで開会式の BGM めっちゃエモいなサントラ欲しい*5」以外に感情がなかったため、何を喋っていらしたのか全く記憶にない。各位頑張ってくださいとか言っていたと思う。

大会前にかっこよさげな BGM かかってるとことか完全に abc やんけ。

コンテスト本戦

ここで競プロに詳しくない人のためにざっくりとルールを説明しておくと: 競技時間は3時間。問題は A から H まで8問用意されていて、配点は 300-400-700-800-800-800-1200-1400。競技時間中に正しいプログラムを作成して提出すればその場で点数に加算される。順位は点数順、次いで「最後に新規の正答をした時刻」の早い順に決定する……といった感じ。

問題の難しさと配点には強い相関がある(それはそう)ので、配点だけ見れば大雑把な立ち回りの方針が立てられる。ABC *6の問題で言えば、僕は500点以下なら概ね解けて、600点は解けたり解けなかったりして、700点以上はもう無理という感じなので、今回はA問題(300点)とB問題(400点)に全時間をかけることにした。

さて、ほとんど前置きらしい前置きもなく、サクッと本戦が始まった。ところで、コンテスト開始までのカウントダウンするとことか完全に abc だった。やっぱこれ abc だな？

早速A問題に目を通す。数列 A, B が与えられ、 a_i + b_j = a_k + b_l を満たす組 (i, j, k, l) (i \neq k, j \neq l) を2秒以内に探す問題。ただし数列の長さは {10}^5 くらい。

と、右隣の人が驚異的なスピードで打鍵し始める。僕は下手すると非プログラマの人々よりタイピングが遅いので、めちゃ速い人の打鍵音を聞くと気圧されてしまう。というか、タイピングゲームとかと違って打つべきものは自分で考えなくちゃいけないのにその打鍵速度はおかしくない？本当に人か？え？ていうかもうこれわかったんですか？

隣の人の動きで動揺してしまうのとか、オンサイトならではだなあ。それはそれとして、よそはよそ、うちはうちと言い聞かせながら再度問題を眺める。与式は a_i - a_k = b_l - b_j だから、各集合の上で可能な差を全列挙すればいいわけだが、それだと2秒に間に合わない。脳死で半分全列挙では～～～～？？？とか言ってみるが、5秒ほどして冷静に考えて何も半分にならないことに気づく。……は？なんだこれ？

右隣の人のキーボードも静かになった。入力を拾う典型部分だけ先にコーディングするタイプの人だったのかな。やっぱこれ難しいですよね？と勝手に同族意識を持つ。

制約に \forall a \in A, \forall b \in B: 1 \leq a, b \leq {10}^6 とあるので、 |a_i - a_k| の値としてあり得るのは高々 {10}^6 通りしかない。任意の d (0 \leq d \leq {10}^6) に対して |a_i - a_k| = d なる (i, k) を O(\log |A|) くらいで見つけられればいいのか……？そんな方法ある？とか思いながらボールペンをゴリゴリと走らせるが何も得られず。

300点問題を解けないのはやばすぎでは……という考えに後ろ髪を引かれまくってA問題を粘ったが、1時間も過ぎたかというあたりでちょっと頭冷やそうと思ってB問題に移った。後から考えるとAからは即座に撤退すべきだった……。

B問題は x, y, z の3層からなる未知のネットワークに対して、 x- y の隣接行列と x- z の到達性を表す行列が与えられるので y- z の隣接行列を求める問題。ただし、各層のノードは高々 {100} 個。

直感的には正しそうなアルゴリズムがすっと浮かんだのでその通りに書いた。提出。TLE。余計なループが1つあるのに気づいたのでそれを外すと AC*7 できた。っしゃあ地蔵は避けられた。大体40分くらいかかった。

地蔵回避の安堵感から順位表を眺める。Aが解けているのが4割くらい、Bは9割くらいの人が解いていて、C以上を解けている人はほぼ皆無。やっぱA地雷だったんか……みんな見切りを付けるのが早くてすごい……。

赤コーダー*8 がうじゃうじゃいるのにほぼ解かれていないのはヤバすぎるので、当初の予定通りC以上には触らないことにした。残り時間をAにつぎ込む。

しかし何も進展を得られず残り時間10分を宣告される。やけになって謎の枝刈りを始める。 |a_i - a_k| = d なる (i, k) を探すのに O(|A|) かかる*9のはもう諦めて、 d の候補を絞ればいいのでは？ A の要素を数直線上にプロットして……隣接するプロット間の区間をプライオリティキューに突っ込んで……キューの先頭を引っこ抜きながら拡大した区間をぽこぽこ放り込めば……？オラ提出だ食らえ！

びっくりしたことに TLE にならなかった。ならなかったが、1ケースだけ WA*10 した。でももうバグを取る時間は残っていない。

この最後の特攻とほぼ同時にコンテストが終了した。chokudai さんがお疲れさまでしたーみたいなことを言って会場拍手。やっぱこれ abc の 1R でしょ*11。

コンテスト終了後

順位表は終了30分前時点で凍結されたので、最終的な順位は発表を待たないといけない。が、30分前時点でもA問題の AC 率は競技中に一度見たときと大して変わっていなかった。つまり A と B が解けるだけで上位 50% だったということになる。それ以外の人々 は B しか解けていない。世紀末みたいな問題セットだ。

競技終了後に #jsc2019 に流れたツイートを見るに A は鳩の巣により全探索が許されるとかなんとか。……あ？………あああああああ！！！！！

内心絶叫しているうちに順位発表が始まる。上位20位は前で表彰されて賞金も出る。僕でも名前は知っているようなつよい人々が順当に表彰されていった。C以上の問題を2つ正解できれば大体20位以上だったっぽい。表彰された人も全員がAを解けたわけではないようだが、赤コーダーが解けない300点問題って何？？？？？

続いて関係各位から短めのお話が何本か、そしてトークセッションがあって、色々とぶっちゃけたお話を聞けたりした。「競プロができれば就活は無敵みたいに思ってる人いますけど、まずみなさんは会話ができるようになりましょうね」みたいな。耳が痛すぎてもげた。他にも面白い話題は多くあったが、詳細は割愛する。

その後、懇親会まで1時間強の休憩が入り、会場設営のためにみんな外に出された。昼飯がまだだったのもあって、行きに見つけた怪しい蕎麦屋で腹ごしらえ。結構美味しかったのでおすすめ。

会場に戻るとあちこちに人の輪ができてたので、適当なところに入れてもらう。「オンサイトだと参加者を予選か何かで絞らねばならず、結果として毎度同じ面子になってしまう」みたいな話*12がちょっと印象に残った。確かに上位陣には身内ノリらしいものが存在したように見受けられたし。これ、競技クイズ界隈の文脈にもそのまま当てはまる話だよなあ。

懇親会は身内がひとりもいないので厳しいかと思われたが、たまたま同じ大学のはじめましてな人がいたのでずっと喋ってた。実質身内で話していたようなもんだ。会話ができねえんだなあ……。

ところで、懇親会めちゃ豪華な料理が出たんですよ。知ってたら蕎麦食わなかったのになあ！

雑感

学生限定で、しかも予選通過枠200人という大規模な大会で、加えて予選でたまたま運が良かったからオンサイトコンテストなんてものに出られたわけで、貴重な経験だったなあという。

最近しみじみと感じていることに、わりとしょぼいことでも評価してもらえているのは、評価の先頭に「まだ学生なのに」が付くからなんだよなあというものがあって、今回のもそのひとつだと感じている。学生の紋所も来年度からはもう使えないわけだし、素の腕力を鍛えていかないとなあ。

*1:制限時間に間に合わないことを表す競プロ用語

*2:自宅から参加するオンラインコンテストに対して、物理的な会場に集まって行うコンテストのこと。

*3:競技クイズの学生大会。AtCoder Beginners Contest とは無関係。

*4:AtCoder の社長。

*5:大会通して随所で BGM が挿入されていたが、どれもこれも非常に好みだった。かっこいい。

*6:オンラインコンテストの AtCoder Beginners Contest のこと。競技クイズの学生大会とは無関係。

*7:正解することを表す競プロ用語。

*8:要するに競プロのランカー。

*9:愚直にやれば O(|A|^2) だが、長さ {10}^6 の配列を用意して A を埋め込めば O(|A|) になる。

*10:誤答を表す競プロ用語。

*11:abc の最初のラウンドでは全員が一斉に黙々とペーパークイズを解く。で、終わった瞬間にみんなで拍手する文化がある。

*12:話の主旨からは外れた抜粋ではあるが。