この記事はtraP Advent Calendar201711/26の記事です。
こんにちは、17のxxkiritoxxです。昨日と今日の2日間CODE FESTIVAL（通称コドフェス）という競技プログラミングのオンサイトイベントに出ておりました。本記事はその参加記になります。何でAdvent Calendarで参加記を書いているんだろう・・・・・・。ちなみに私は競プロ歴半年とかそこいらの青コーダーなので温かい目で見てください。
そもそも競プロとは何かについてはココを見てください。

登場人物

我らがtraPは4人が見事予選通過しました！！！！！！！！！！！！
括弧外はtraPでのID,括弧内はatcoder IDです
nari(rickytheta) : 15の現B3。全強
s_cyan(saharan) : 15の現B3。全強
baton(goodbaton) : 17の現B1。全強
xxkiritoxx(xxkiritoxx) : 17の現B1。カス

予選

去年と比べて枠が半分ぐらいになってて今の実力だと本戦突破は厳しいかなァ～～～～～と思った。

予選A

#traP合宿2017 #変態のXD #総受けのハミング #全強のoZee #Hi_Daddy_Just_missed_sending_massage_U_can_fuck_my_accountのOzeeOzee pic.twitter.com/SWk4mSnBmD

— ✞キリト✞ (@unko08658932) 2017年9月23日

なんとこの日はtraP夏合宿2017の最終日だった。絶好調でも厳しいのに果たして遊び疲れた後のコンディションで予選A通過出来るのだろうか。

はい俺は全強

— ✞キリト✞ (@unko08658932) 2017年9月23日

なんかD問題まで解けてしまった

pic.twitter.com/W5cjlBUu4Q

— ✞キリト✞ (@unko08658932) 2017年9月27日

なんか通過出来てしまった
というわけで問題との相性が良かったお陰か予選Aで通過出来てしまった。むっちゃ嬉しかった。

予選B

@_n_ari ┗('o'≡'o')┛ウワアアアアアアアアアアアアア！！！！！！！！┗('o'≡'o')┛予選Bが始まる┗('o'≡'o')┛ウワアアアアアアアアアアアアア！！！！！！！！┗('o'≡'o')┛

— ✞キリト✞ (@unko08658932) 2017年10月8日

とりあえず開始前にnariさんにクソリプを送る

あのですね、早いですが諦めます

— ✞キリト✞ (@unko08658932) 2017年10月8日

5分で諦めた。
寝不足で頭が全然働いてなかったのとそもそも問題との相性が悪かった。
予選Aで通ってて本当によかった・・・

予選C

@_n_ari ┗('o'≡'o')┛ウワアアアアアアアアアアアアア！！！！！！！！┗('o'≡'o')┛予選Cが始まる┗('o'≡'o')┛ウワアアアアアアアアアアアアア！！！！！！！！┗('o'≡'o')┛

— ✞キリト✞ (@unko08658932) 2017年10月22日

とりあえずnariさんにクソリプを送る

無理

— ✞キリト✞ (@unko08658932) 2017年10月22日

D問題が無理だった
本当に予選Aで通っててよかった・・・

本戦前

本戦参加は初めてなので（それはそう）本戦の流れを過去の参加者のブログなどを見て学んだ。
てっきり1日目の夕食と2日目の昼食しか出ないものと思っていたが、どうやら1日目は昼食も出るし2日目は朝食も出るらしい。学生の身としては大変嬉しい。
コンテストページが公開されたのでパーカーのボーダーを調べてみると、なんと1000点とのことだ。過去のボーダーを考えると異例の低さだが、私にもチャンスがあるということだろうか。
そしてbetaの順位表で参加者リストが見られるようになっていたので覗いてみると、どうも私のレートは参加者100人中90位ぐらいのようだ。なんかとんでもない大会の本戦に出場するんだなあ・・・

本戦初日

会場に着いた。参加するだけでTシャツとボールペンとトートバッグと考察用紙やクリアファイルなどなど色々貰えるわ昼食あるしジュースとお菓子食べ放題だわで（運営は金があるなあ・・・）って思った。絶対にパーカーをゲットしてやるからな～～～～～～待ってろ～～～～～～～～
ちなみに昼食はカツサンド+コロッケバーガーでした。超おいしい。

pic.twitter.com/FF8t3wz9Hx

— ✞キリト✞ (@unko08658932) 2017年11月25日

一応クソリプも送っとくか

@_n_ari ┗('o'≡'o')┛ウワアアアアアアアアアアアアア！！！！！！！！┗('o'≡'o')┛本戦が始まる┗('o'≡'o')┛ウワアアアアアアアアアアアアア！！！！！！！！┗('o'≡'o')┛

— ✞キリト✞ (@unko08658932) 2017年11月25日

コンテスト開始。落ち着いてA問題を開く。ちょっと面倒くさそうだなあと思いつつ落ち着いて場合分けをして提出。WA。誤読していることに気付いたが面倒なので一旦飛ばしてB問題を開く。これはa,b,cの数だけ数えれば十分、思考実験すればabcabc....という順に並べればいいことにすぐ気付く。提出。無事AC。A問題に戻って面倒ながら16通り全部ベタ打ちしてAC。ここまでで30分ぐらい経過してしまった。
C問題を開く。ここを突破すればパーカー確定だ。パッと見面倒くさそうだけど、$2^{50}$をわざわざ全探索する必要はなく時差がD時間の人がそれぞれ何人かというのを記録して全探索すれば高々$2^{12}(=4096)$通りで済むことが分かる。それが分かったらあとはやるだけ。意外と面倒だったけど20分ぐらいかけてAC。ここでパーカーが確定する。

ぱーかーとった

— ✞キリト✞ (@unko08658932) 2017年11月25日

ここからの2時間ほどが辛かった(csenryu)。D問題を開いても方針がサッパリ見えず、E問題は何となく方針っぽいのを思いつくも実装が出来ず断念。F問題はもう少し考察を練れば解けそうだったが前日の睡眠不足がたたって頭が働かない。G以降もダメ元で開いてみるがこれは当然厳しい。その後はD問題とF問題を同時に考えながら交互に実装してみたり、ランキングを開いてみたり（ここで全員パーカー入手が確定していて驚いた）、諦めモードで今日のその後の予定を確認してみたりと、結局1つもACすること無く3完で本戦は終了。本戦100人中89位と、ほぼレート通りの結果に。パーカーは手に入れたので良しかな。

交通費精算しようと四苦八苦してたらパーカーのLが無くなった（かなしい）

— ✞キリト✞ (@unko08658932) 2017年11月25日

パーカーが小さい。これは予想外だった。みんなも来年のコドフェスに出場してパーカーLサイズが欲しい人は早目に確保しよう。

それと交通費申請の時は印鑑と銀行の通帳があるとスムーズに進むので持ってきたほうがいい。メールのどこかに書いてあったらしいが、私は見落としていたので当日は非常に苦労してしまった。

その後に表彰式でtouristが優勝し、間もなく大陸対抗トークライブが開始。実は眠気が結構キててあんまり真面目に聞いてませんでした・・・・ごめんなさい・・・・・・・・・
国内外のトップ競プロerは今まで競プロで累計ウン百万も稼いでいるらしいというのが面白かった。俺も競プロで一生遊べるほど稼ぎてえ（？）

これの終了後に自由時間が開始。参加者は太鼓の達人をやったり、今年から新登場のコネクションハンティングをしたり、お待ちかねの夕飯を食いまくったりと思い思いのことをしていた。ちなみに私は夕飯を無限に食っていました。

pic.twitter.com/CKdfWFH5Uv

— ✞キリト✞ (@unko08658932) 2017年11月25日

🍣🍕🍖あたりはもちろん、ラザニア、デザート、焼きそばなどなど大量に振る舞われた。マジな話私はコレのために本戦に来ているといっても過言ではない。学生の身だと🍣🍕🍖なんて滅多に食えないし、親の金や自分の金で食うよりも企業の金で食う方が何倍もウマく感じる。

ここでコネクションハンティングをすっかり忘れていたことに気付く。これはどういうものかというと、参加者が他の参加者にする簡単な質問を考え、その答えを専用の紙に書いてもらい、一定人数分の回答を集めると豪華賞品と交換してくれるというものだ。ちなみに今年の商品は以下のようなものであった。

10人分・・・オリジナルステッカー（対象者全員）
20人分・・・オリジナルタンブラー（先着30人）
30人分・・・オリジナルヘッドフォン（先着5人）
40人分・・・オリジナルバックパック（先着3人）
50人分・・・？？？（先着1人）（これは後にセグウェイであることが判明）

ハンティングはかなり出遅れていたので18:30の時点で30人分以降の商品は無くなってしまったようだ。どうにか今から追いついてタンブラーを確保したい。とりあえずnari,s_cyan,batonと交換。その後彼らと繋がりのありそうな人何人かと交換。nariさんらと一緒にコネクションハントしたそうな人を囲い込んでハント。合間にちょくだいさんの本戦解説を聞いてまたハント。とりあえず1日目で16人分集め終わった。

ここでエキシビジョンマッチが始まる。一応問題を開くが案の定サッパリ分からなかったのでこのブログを書きながら観戦。結論を言うとtouristのいるチームが優勝した。

ここで明日のチームリレーのチーム表が配られる。nariさんとyosupoさんが同じチームだ・・・。そして今日はこのまま解散。明日のトーナメントは勝てる気がしないのでまあ良しとして、リレーでお荷物にならないこと、コネクションハントを続けて明日はタンブラーを手に入れることを願って本日は解散。

ちなみに家が会場から遠い人は運営がとったホテルに泊まれるらしい。私は中途半端に家が近いので自宅に帰ることとなった。残念。

本戦2日目

pic.twitter.com/Vgo9qqkqSU

— ✞キリト✞ (@unko08658932) 2017年11月26日

今回の朝食はサンドイッチだ。朝食を何も食べていなかったので到着してすぐにがっつく。予想はしていたが、かなり美味しい。ちなみにホテル勢はそっちの朝食を食べていたのでサンドイッチはしばらく後で食べたようだ。

@_n_ari ┗('o'≡'o')┛ウワアアアアアアアアアアアアア！！！！！！！！┗('o'≡'o')┛開会式が始まる┗('o'≡'o')┛ウワアアアアアアアアアアアアア！！！！！！！！┗('o'≡'o')┛

— ✞キリト✞ (@unko08658932) 2017年11月26日

しばらくして、トーナメントが開始した。このトーナメントとは以下のようなルールである。本戦順位の近い人同士で18人ほどのグループを作り、その中で問題を解く。問題は30分で2題という分量なので早解き勝負に見える（実際上位陣はそうである）が、実際は各問題とも30分で解くには中々歯ごたえのある問題であり、部分点をいかに早く、いかに多くもぎ取れるか、という一面もある。
こうして問題を解き、第1ラウンドは上位10人が勝ち上がる。同様に第2ラウンドでは上位5人が勝ち上がり、第3ラウンドでの上位3人が最終的な勝者である。勝者には特製フリスクケースが与えられる。

さて第1ラウンドだ。2つの問題を見てみる。C問題はちょっと何言ってるかよく分からない。200点分の部分点は全探索でも書けば通りそうだが、正直30分で問題を理解して書くまで終わらせる自信が無い。D問題を見よう。こっちの200点分の部分点はすぐに方針が分かった。このときは頂点1からそれ以外の全ての頂点に辺が伸びているようなグラフである。面倒なので結論だけ言うが、辺$i$のコストを$c_i$とすると、

$$\sum _{i=1}^{N-1}{c}_i=\frac{1}{2(N-1)}\sum _{i=1}^N{s}_i$$

$$c_i=\frac{1}{N-2}(s_{i+1}-\sum _{j=1}^{N-1}{c}_j)$$

となる。とりあえずこれを書くが、${\sum }_{i=1}^N{s}_i$を一気に計算してから2(N-1)で割ろうとするとlong longでも明らかにオーバーフローすることに気をつける。木の辺の数はN-1本のはずなのになぜかN本と勘違いして闇になったりしていたが何とか終了6分前に提出。200点ゲット。最終的な順位は8位で何とか第2ラウンドに進出することが出来た。
ちなみにこの記事を書いている最中に気付いたことなんですが、${\sum }_{i=1}^{N-1}{c}_i=s_1$ですね・・・・・・・・・・・・・・・・・・・

続いて第2ラウンド。A問題を見てみる。うわあ面倒くさい。さっきと同様の理由でとりあえず飛ばす。B問題を見てみる。うわあこっちも面倒くさい。・・・・・・ん？待てよ？

k=1のとき、この操作は「先頭の数字を一番後ろに持ってくる」という操作に等しい。k=N-1のとき、この操作は「先頭の数字と最後尾の数字を交換する」という操作に等しい。これを使えばバブルソートの要領で並び替えることが可能なんじゃないか？

とりあえず書いてみた。「先頭の数字を一番後ろに持ってくる」という操作でわざわざN-1回swapしているのでNが十分大きいとTLEするかとも思ったし、バブルソートの要領だったら$O(N^2)$回swapすることになるので定数倍次第でNが大きいときWAになりそうだと思った。しかし部分点で300でも取れればよかったのでこのまま提出。

なんとWAにもTLEにもならずどんどんジャッジが進む。そのままなんとACしてしまった。AC出来てしまうとは流石にたまげた。そのまま堂々2位でラウンド3進出決定。ちなみに1位はロシア人の激強レッドコーダーだった。なんでここのグループにいるんだ。

いよいよラウンド3だ。問題Eと問題Fを落ち着いて読んでみる・・・全然分からない。とりあえずE問題の200点はDFSをN回すれば$O(N^2)$で良さそうなのでDFSを書いてみる。なんと盛大にバグる。競プロ経験値の無さから起きた悲劇である。F問題に行こうかとも思ったが、問題の意味すら分からないのでE問題に戻ってDFSの実装を続ける。結局バグったまま終わってしまった。肝心要のところで0完0点。完敗である。

DFS 無限にバグらせ 競プロ引退 #csenryu

— ✞キリト✞ (@unko08658932) 2017年11月26日

ここで昼食タイム。

pic.twitter.com/sH2AvSrl5h

— ✞キリト✞ (@unko08658932) 2017年11月26日

私はすき焼き弁当を選んだ。他にはちらし寿司弁当、カツ丼弁当があり、3種類から選べた。どれも非常に美味しそうである。私の語彙力が稚拙過ぎて「美味しい」という感想しか伝えられないのが非常に残念だ。

ここで三宅陽一郎氏のトークライブが始まった。その時のスライドはこことここにある。感想は、「ハァ～～～～～なるほどなぁ～～～～～」（感動している）という状態が初めから終わりまで延々続いていた。ちょっとそれ以上の感想は語彙力が無さ過ぎて出てきません・・・・・・・上に貼ったスライドを読んでください・・・・・・・・・マジで良い話だから・・・・・・・・

トークライブ終了後、コネクションハントを忘れていたことに気付き、急いでその辺の人何人かに答えて貰って提出。TLEかと思ったが無事ACしてタンブラーを獲得。意外と提出時点でも沢山残っていた。ひょっとしてタンブラーは最終的に余ったのではないだろうか。

間もなくrngさんのトークライブ（というか強い競プロer同士の競プロほとんど関係ないクイズ大会）が始まった。正直なところ、前述のコネハンをしている間に席が無くなってしまったので後ろの方での立ち見になってしまい、よく見えなかった。強い人達がしょうもない事を延々とやっているのが面白かった。

楽しい時はあっという間に終わってしまい、次は最後のコンテンツ、リレーコーディングだ。チームメイトにはnariさんもいるし赤い人が何人もいるし大丈夫だろう。yosupoさんが海外の人に英語で話しかけられてたけど私より語学力が低そうな返答をしていたのが印象的だった（失礼）。ちなみにここではレッドブルの大きい奴が1人1本貰えたのとチームカラーと同じ色のTシャツがまた貰えたのでビックリした。この2日間だけで衣類を3枚も貰ってるなあ・・・

Buli(@_n_ari) pic.twitter.com/zvi4XCGXpl

— ✞キリト✞ (@unko08658932) 2017年11月26日

リレーコーディングが開始した。私の担当はB問題。完全N分木の最小共通祖先を考える問題なのだが、どうもこの問題は前に似たようなのを見た気がする。vとwが一致するまで「vとwのうち大きい方をその親に置き換える」という操作をするんだったな。以下、説明のためv>wとするが、この置き換えに対応する操作は当初「v=(v+1)/N」かな～と思った。しかし、これはN=3の時にしか実験をしなかったための勘違いであり、実際は「v=(v+N-2)/N」であった。脚を引っ張ってしまった・・・・・・。nariさんからN=1のときは例外処理としてmin(v,w)を出力するようにとの助言を貰い、提出。一発AC。後は申し訳程度に考察に参加したり、参加したところで解けなさそうなのでお菓子をひたすら貪ったりしていた。

我々のチームは惜しくも優勝を逃したが、見事全完することが出来た。赤い人達が束になるとあんなに早く解けるんだなあ・・・。優勝チームには景品としてモバイルバッテリーが贈られた。ちなみに優勝チームはtouristのいるチーム ではない 。

最後に様々な表彰があり（生憎私は縁が無かったが）、CODE FESTIVAL 2017は幕を下ろした。コード川柳にクソ川柳しか来なかったので表彰者無しになったのは面白かった。

総評

最高の プログラミング コンテスト (csenryu)

たまたま予選突破出来ただけで服を何枚も貰え、記念品も沢山貰え、美味しい物を腹いっぱい食べられたので本当に出てよかったと思う。コンテストfinalとトーナメントでは少々残念な結果に終わってしまったが、来年は賞金が貰えるぐらい頑張りたい（厳しい）。

こんな駄記事、もとい駄参加記を読んで頂きありがとうございました。この記事は「来年初めて参加する人に向けての有益な情報を含めよう」と思って書いたため、途中冗長に思えた点があるかもしれません。申し訳ありません。全強赤コーダーが問題を解きまくるのを想定していた方もごめんなさい。「弱小青コーダーでも実際出場してみたらかなり楽しかった」というのが伝われば幸いです。

明日の担当はAltair626さん、HARUKAさんです。お楽しみに！