Hack to the Future2020本選参加記

競技プログラミング

この記事は東工プロジェクトアドベントカレンダー12/16分の記事です。目次はこちら(サークル公式ブログに飛びます)

 

こんにちは、やほーbbと申します。12/4に記事を一つ書いているのですが(同上)、個人的に書きたいということで更に書くことにしました。想定読者の都合でこっちに場所を移しました。

 

去る12/8に、Hack to the Future2020の本戦に参加してきましたのでその話をさせていただきます。2回連続東方のとの字も出て来ない記事ですいません。*1

 

 

 

Hack to the Futureとは？

 

知らない人への説明　Future社（ITコンサルなんかをしている）が主催する、競技プログラミング大会（時間内に与えられた問題を解決するプログラムを書く大会）の決勝です。自分は競プロ（今後はこう略します）を今年の四月からやっているのですが（このへんで話をしている）、これが初めてのオンサイト（会場に集まって参加するタイプ）でした。説明多くね？

 

知ってる人への説明　これいる？（アルゴじゃなくてマラソンです）

 

 

 

本選前の話

 

本選というだけあって一ヶ月ほど前に予選が行われたのですが、たまたまその日が完全フリーだったのと、予選のキリ番賞で3000円が貰えるかもということでお金欲しさに参加しました。その際の結果が約800人中166位ということでした。長時間のコンテスト（これは8時間、普段は2時間前後）は初めてだったので上出来過ぎると思います。*2 

本選参加人数は50人程度で、普通なら本選に呼ばれる順位じゃないのですが、就活枠が多く確保されていたのでギリギリで滑り込めました。*3

 

本選前の話終わり。

 

コンテスト開始まで 

 

集合は朝の10時。生活リズムが崩壊しがちな競プロerには厳しい時間ですが、当日の朝は早く起きられました。翌週に学会発表があったり*4、デレステで推している子のイベントの周回をしていた*5割には頑張りました。

 

会場のある大崎までは15分くらいなので雑に行く。実は大崎って降りたことないんですよね笑*6。遠方からの参加者には交通費宿泊費も出してくれたみたいなのでいいイベントだと思います。

 

会場のある大崎ThinkPark Towerに到着。クリスマスイルミネーションで飾り付けられている中、ラウンジ様のスペースにオタクが大集合していたのでここで合っていることを確認。

 

しばらくすると社員さんが来る。受付で名前を伝えると*7入館証を貰い、すごそうなエレベーターで会場の部屋へ。

 

会場でもう一度名前を伝えると、いろいろなものを貰う。

 

・名札*8

・ウィンドブレーカー*9

・メモ帳

・ステッカー

・チラシ

・歯ブラシ

 

歯ブラシ、何？

 

 

席は自由だったので適当に座ると、知っている顔が来る。

deoxyさんと合流。ついったでは前日に相互になったんですが、高校同期かつ大学同期なことを(一方的に)知っていました。ICPC(大学対抗の大会みたいなの)に出てたので名前を知っている。

 

それ以外には知り合いがいないので、オリエンテーションまでなにも起こらない。

 

オリエンテーションでは、会社が闇医者をしているだとか、難題にチャレンジするのが好き♥️だとかいう紹介をされた後、無限コピー用紙や無限お菓子湧きカゴを用意してもらいました。

 

 

 

コンテスト中

ここからコンテスト終了までの殆どがぼくのクソみたいな考察垂れ流しなので、終了後まで飛ばしてもらっても構いません。

 

前半戦

atcoder.jp

10時半に開始。text(cat) 0。 WA。

 

気を取り直してバームロールを食べながら問題を読む。1000個の点でグラフをつくって、与えられる頂点数20個の木をたくさん埋め込む問題っぽい。

 

グラフかぁ～～～～～～～～～～～～～～(クソでかため息)。

ダイクストラとワーシャルフロイドの区別も付かない程度に知識がないので負けです。*10

 

そうは言っても出てしまったものは仕方ないのでカントリーマアムを食べながら構造体を作り、出力形式を合わせる。とりあえず全部1から20でいいか。

 

30分でとりあえずAC*11。0点。緑のマークが点灯してるのに順位表に反映されないの悲しい。

 

他の人を見ると5000点という人がいる。全部のサンプルで一つずつ木を作ったんだなぁとわかるので、根を一つ決めてDFS*12することにする。このとき点は再利用しないことにした。

なんかうまく行かない。というか出力が多すぎて認識できない。この辺でマラソンやったことないのが露骨に響いてくる。いやアルゴもやったことないんですけどね。

海鮮ごのみを食べながらデバッグ作業をしていると、chokudaiさん*13が前でなんか言ってる。

 

満点？？？

 

 

8時間のコンテストなのに2時間足らずで満点が出ました。まだぼくは0点なのに。

どうすんのかなと思ったら、これは4時間で切ってもう一個厳しい条件のコンテストを開くらしいです。スタッフさん大変だなぁ。

 

それと同時にぼくの目標が正の点数を得ることになる。流石に本選0点で最下位は恥ずかしい。

 

一つの木だけDFSしてるのになぜかREが取れないので、方針転換。木の点は20個しかないので根を点1に決めて、そこから繋がっている点をただただ貪欲に置いていくことにする。この方針転換が1時くらい。前半戦終了が2時半なのでちょっと焦っている。

 

しかし実装方針を単純にしたため、15分ほどで出来る。ビジュアライザに投げると形式は合っているみたいなので提出。AC。0点。？？？

 

なんでバグってたかは覚えてないですが、30分ほどがんばったらバグが取れて無事正の点数であるところの5000点が取れました。正直めっちゃ安心しました。

 

で、これは1000個の点のうち20個しか使ってないので、理論上同じ方針で50倍の木を埋め込めるだろという雑な考えのもと、各点の使用済み判定だけして50個埋め込むように書き換えたら24万点になりました。最後の方は埋め込み不可能な場合が出てきてるので1万点少ないんだと思います。

Submission #8818375 - HACK TO THE FUTURE 2020 本選　←最終提出

この時点で2時。もう満足したので少し遅いお弁当タイム。🍤チリでした。

 

 

 最後ちょっと頑張って木のインデックスをシャッフルして最大値を使おうとするけど間に合わず前半終了。同時に後半開始。

後半戦

atcoder.jp

後半も問題の概要は変わらないけど、木の大きさが可変（2~100）になりました。平均の大きさ的には20から50になっているのでたしかに難しそう。

前半で作った木の構造体は大きさが固定だったのでそこから作り直し。というか隣接行列でよくね？

それはともかくまた出力形式合わせて、とりあえずビジュアライザに出して確認……？

 

ビジュアライザないやん！

 

 

 可視化してくれることより出力形式が合ってるかのために使っていたので死ぬ。

 仕方がないのでWA覚悟で提出。WA。500点。

 

 

サンプル一個だけは正しい形式で出せていたみたい。つまりバグったりバグらなかったりする。

いろいろ見ていると、使わなかった木の番号割当で問題が起きているみたい。

ここまでは木の頂点の対応関係は-1で初期化しておいて、-1のままの点には1から順番に適当に振り分けるということをしていたんだけど、木を埋め込む途中で挫折しちゃった子たちがいたときに番号が被っちゃうことがあるらしい。

 

 

 

本質じゃないところで詰まってしまっているので辛くなる。チーズおかき片手に泣きながら実装する。乱数を使うことにする。この頃にはビジュアライザが生えていたので提出形式の確認が楽になる。

 

どうにか直す。前半戦より木が大きくなっているので前から10個だけ作ることにすると31800点。平均6個しか埋め込めてない。後半に大きいものが来るとやっぱり入れられないのかな。

f:id:yahoobb_th:20191211002139p:plain

提出先は確認しよう！

先頭からじゃなくてランダムに取り出してみる。点数が下がる。

ここらへんで木のサイズの小さいものから入れていけばいいのでは？となる。サイズでのソートはすぐにできたのだが、元の順番との対応関係をとっておかなければいけないのでそこで無限にバグらせる。チョコリエールを食べつつ構造体をいじくるもうまく行かず結局一時間が溶ける。

 

残り1時間を切ってそろそろヤバいとなる。この時点で45位くらいだったので、ページ2枚目(40位)に入ることを目標としていたためまともな点数を取らないといけない。確かこのときボーダー20万点程度。

 

ソートを投げ捨て、結局木を全部見ることにする。その際に木のサイズが一定以上なら無視することにすればおおよそ同じようなもんだろうと。

AC。44万点。いいですね。

 

もう残り30分だったので大きな改良はできないと考え、サイズの閾値を微妙に変えて提出しつつ、サイズ2、3のものは木の形が一緒じゃんということに(今更)気づいたのでそこについての埋め込みを考える。が結局間に合わず終了。お疲れさまでした。

 

結果　前半29位・後半39位(52人中)　目標は達成しました。

 

 コンテスト終了後・懇親会

コンテスト後はすぐに隣の部屋に移って懇親会へ。というか既に部屋移動してた人いるな。(後半戦も満点を出していた人と後で知る。キチガイかな？)

 

全員がクタクタerなのでさっさと食糧へ。きれいな料理(語彙がない)と高そうなお酒(同上)を手にするも、ぼっちなので居場所がない。deoxyさんは「料理を食べに来たんだ」と言いつつも別の知り合いのもとへ行ってしまう。

f:id:yahoobb_th:20191212221757j:plain

唯一撮ってあった料理

ふらふらしてると偉い人が音頭を取る。たまたま隣にchokudaiさんが居たタイミングだったので乾杯をした。なお話はしていない模様。

 

cirno3153さんと話をする。東方理學団の方らしい*14。

前半は木の深さが平均5しかないんだから結構雑でも全部埋め込めそうという話をされて確かになぁとなるも、書けないなぁともなる。

いつもは追い込み方タイプを自称していて、時間がそのままだったらもっと良い順位が取れたと言い張っていた。いや4時間で満点取ってる人がたくさん(11人)いるんだからそんなことないだろ。

 

表彰式が始まる。今回突然コンテストが2つになったので、賞金も2倍になった。競プロでお金貰ってる光景見るの不思議だなぁ*15。

 

またぼっちになる。梅酒を飲んでいると社員の方が話しかけてくる。ICPCとか出なかったの？という話の中、うちのバイトの子も出てたんだよって呼ばれた人がdeoxyさんだった。いやお前ここのバイトかい。

もうひとり呼ばれた人がidsigmaさん。いつもkort0nがお世話になってますという挨拶(この二人はチームを組んでいる)をすると、しょっちゅうkort0nにリプライを送っている姿を見られていたらしく、意外にも名前を認知されていた。東大生音ゲーマーだと思われていた。なにかと音ゲーマーと勘違いされがち。

 

ここからはずっとこの辺の人と話をしていた。社員の中になぜか薬剤師免許持ちが居たり、20万円分の計算機代でゴミを作り出したり、ぼくのわからない話をしたりしているのをひたすら聴いていた。話はしてないやん。

 

 話を聴いていたらお開きの時間になってしまった。最後におみやげ(柿の種)を頂いた。美味しかった。

 

打ち上げに行った人もいたみたい(Ti11192916さんが来るみたいな声が聞こえた)だけど、翌々日に学会があるので直帰(これは半分嘘で、話しかける勇気がなかったというのもある)。

 

帰りはなんとなく大崎駅ではなく大崎広小路駅まで歩いてました。この辺りビルとマンションしかないな。

 

感想

 マラソンを完走した感想ですが、めっちゃ楽しかったです*16。

オンサイトコンテスト自体初めてだったのに加えて、普段やってないマラソンマッチだったのでめっちゃ怖がっていたのですが、むしろ新鮮な体験ができたってやつです。情報系の文脈にぼくが参加することはないので場違い感ないかなぁとも思ったけれど場違いでも問題なかったですね。どうせ皆同類だ。

 

 これは開始前の怖がり方。

 

ただどうせならもうちょっとfutureさんが何やってるのか知りたかったなぁというのはあります。せっかく就活枠で行ったので*17。

 

 

頂いたものも美味しかったり使い勝手良かったりで満足しています(歯ブラシは相変わらず何？)。

 

 

 

えっと東方クラスタが想定読者のアドベントカレンダーなことを忘れていたのでちょっと東方クラスタに向けてちょっと話をすると、ぼくは半分くらい東方界隈から競プロ始めたようなものなのですが、東方界隈は広いのであらゆる界隈との積集合があると思います*18。

なので何かしたいなぁと思ったときにこの界隈の中で調べてみると少しは始めるハードルが低くなるんじゃないかなぁとも思っています。そういう意味で懐の広いこの界隈に属していたことはぼくにとって良かったです。

 

 

 

 明日は御神水さんの絵に関する記事です。前回も同じ並びじゃなかった？

*1:実は字だけは出てきます

*2:フルで張り付いていた人が少ないというのもありそう（実際終了直前になって参加し始めた人にめっちゃ抜かされた）

*3:辞退者の繰り上げ枠でした　本選招待や詳細のメールが一生届かないって言っててすいませんでした（迷惑メールだった）（ツカモさんと担当の方ごめんなさい）

*4:今出張先のホテルから書いています

*5:佐城雪美さんすき

*6:実は東方って(ry

*7:本名・ついったID・atcoderIDのどれなのかわからなかったんですけど、前日に本名でお願いしますって連絡があった

*8:ぼくはatcoderIDでした。ついったIDの人もいました

どうでもいいんだけど、本名を開示しておいてハンネで交流する界隈って謎だな(大学東方の記事でそれ言う？)

*9:はじめての競プロ布。

競プロ布ってのはオンサイトなんかで貰う衣類やタオルなどのノベルティらしいんだけど、あまりにも語彙が貧弱だと思う

*10:何が来ても負けます

*11:AC（Accepted）正解　WA（Wrong Answer）不正解　RE（Runtime Error）実行時エラー TLE（Time Limit Exceeded）実行時間制限超過　など

*12:深さ優先探索　とりあえず突き進んで行き止まりになったら戻る手法

*13:AtCoderのえらい人かつ今回の作問者

*14:ほら東方要素(いばるな)

*15:遊びで始めたものなので

*16:翌週の学会中も、事あるごとにHTTF楽しかったなぁ～って呟いてた

*17:自分から積極的に聞きにいけと言われたら泣いてしまう

*18:要出典