この記事はKobe University Advent Calendar 2017の3日目の記事です．

CodeThanksFestival 2017 に参加してきた．

Code Festival とは？

Advent Calendar から見た人向けに．（Advent Calendar 見ている人がいるのか？）

リクルート（とindeed）が主催する，競技プログラミングの大会．

予選・本選・Thanks があり，予選はオンラインで，本選とThanksはオンサイトで行われる．

今年は本選100人，Thanks 100人だった．去年までは本選200人で，Thanksは公式アナウンスが弱めだったが，今年は人数が減って，Thanksのアナウンスが強めだった．

Kobe University からは 5人参加したと思う．

コンテストはすべて Atcoder で行われており，すべての問題が見られる．

なお，神戸大学コンピュータ部の競技プログラミング関連の活動は２日目のうさぎさんの記事をご覧ください．活動は基本的に（部の活動というわけでは無い気がする）slack 上でしているので物理的に部に来る気はないけど競プロには興味がある人・部に入る気は無いけど競プロには興味がある人なども大歓迎です．twitterなどで部員らしき人に話しかけてください．競プロ以外のことで slack を荒らしたい人も歓迎されると思います．

予選

Thanksはまあ行けそう，と言う気分で本選を狙って参加していたけどA,B,Cと順位が単調に下がってだめだった．予選Aが悪かったらThanksも厳しかったかもしれない？

結果

1900点で23位だった．なんとかパーカーを確保した（1800点以上）．

解けないような問題はなかったので全完したかった…

本番で解いた/解こうとした順に問題について軽く書いておく．

A

はい

C

heap に入れるだけ

B

やるだけだけど，実装が面倒そうだったので C を先に解いた．

結局本番では少し面倒な実装をしてしまったので反省．

H

D, E, F, G と読んで，D, F はわからない，E は考えればいけそう，G はとりあえずスルーした．

H は Union-find をいじってマージテクをすればいけそうだったのでやった．（QuickFind という名前がついてるらしい？）

グローバル変数初期化問題で 1RE するが，AC．これでだいぶ精神的に落ち着いた．

E

D に戻るも，全然わからないので E を考えた．

最初はよくあるクイズ的な方向で考えたけど１０回では不可能そうだったので考え直す．

$13^n$ でずらしてやれば良さそうとなるが，コインの数が足りなくて焦った．

結局，全部 -7 すれば良いことに気づいて $6^n$ でやった．

D

これを解けばパーカーだった．結構な人数解かれていて，残り時間も十分あったので解けると信じてもう一度取り掛かる．

１から冷静に考えたらなんか普通に解けた．つらい．

G

全完ワンチャンくらいの残り時間だったので F を考えるが，まったくわからない（制約の+見逃し）ので G を考えた．

グラフの独立集合と言う認識まではできていたが，グラフ理論弱者なので検索すればアルゴリズムが出てくるとか知らない…

制約的には半分全列挙で，DPっぽさも感じたのでその方向で考える．

いけそうな気分になったので実装して，残り５分くらいで提出するが，辺をmapで持ってbit dpの中で非効率な扱い方をしていたので TLE (+WA)．

結局解けずに終了．

その後辺の持ち方を直して TLE は回避したが，WAが取れない．

原因はオーバーフローだった．半分にしたので $2^{20}$で大丈夫とか思っていたけど，辺は $2^{40}$ で持っていたのでそこで死んでいた．

あと，1 << 39 みたいなやつでもオーバーフローする…

rep が int なので i << 20 とかするとオーバーフローする…

等々オーバーフローバグだらけだった．

同じ過ちを繰り返してはいけない．とりあえず one_hot 関数を作った．

int の使用を停止することも要検討．

F

本番中何度も考えたが解けなかった．

制約の+は自分にはまったく見えていなかった．（各要素が$10^5$以下だと勝手に脳内変換されていた）

制約をまったく見てなかったとか言うミスは最近していないけど，同様の見間違いミスは今年のICPC予選でもやっている…

今回は G をやっていてしっかり見直す時間がなかったのでまあ仕方ないという感じもあるが，57人も解いてたので解けるべきだった．

問題の感想

ちょっとがんばれば気持ちよく解ける（ただし脳内AC），ちょうど良い感じのレベルだったと感じた．もう一段上のレベルの問題をなんとか解けるように精進が必要ですね…

その他

本番後にコネクションハントとかいうイベントがあった．質問を考えて，他の参加者の回答を集めるやつ．集めた数に応じて先着で景品がもらえる感じだった．

ポイントが10,20,30,40,50で，景品の数が100,80,7,4,1,1$だったので20が身の丈にあってそうとかいう消極的姿勢で参加した．

よくわからないが，気づいたら30人集まっていたので30点の景品と交換した．後からみると，40人集めても時間的に十分そうだったので40を狙うべきだったかなという気分になった．（後から考えただけ..）30点はタンブラーで40点はトートバッグで，トートバッグの方が質的に実用性が高い気がするので．

他の参加者と話す良い企画だったと思うけど，誰なのかよくわからず話して適当にもらう状況は半分くらい発生したのでその点が残念だった．名札に twitter icon がなかったのも原因の一つ．

本選との規模の違いはあったけど楽しかった．（今年は本選も人数半減なので縮小されていた？）

ありがとうございました．

来年も開催よろしくお願いします / 来年は本選に出られるようにがんばりたい．

写真

そういえば写真撮ってない

今年のパーカーは内側が少しふわふわで暖かい．