CODE FESTIVAL 2016 参加
タイトルの通り、CODE FESTIVAL 2016参加してきました。
まずは予選の話から。の前にCODE FESTIVALに参加するまでのあらましを。
・CODE FESTIVALに参加するまで
7月くらいに何か新しいこと始めようと思って、競技プログラミングを始める。
C言語を学科に入って少し触った程度からのスタート。
とりあえずAtcoderのコンテストに参加してみるという一環でCODE FESTIVAL予選も参加。
・予選A
最早大分前すぎて何も覚えていません。
今確認したところC問題でドハマリしてたみたいです。文字列の扱いをググりながらやっていた模様。
結果余裕の予選落ち(688位)。
・予選B
これももはや曖昧ですが、C問題で道の対応関係を間違えて時間が吸われていった記憶。
326位でこれも通過できず。
・予選C
実装が重いとかデータ構造を知らないとかそういう問題がなく、かなり嬉しいタイプのセットだった。
C問題のデバッグで結構時間を食い、C問題を解いた時点で200位くらいでワンチャンあるか???と思いD問題へ。
まず2列で実験し、これは隣り合う2列ごとに見れば操作組み込めるじゃん!と気づき、やったか!?という感じに。
とりあえず部分点に飛び込む。5回目のsubmissionで部分点成功。
同じ方向性で行けるっしょwと提出してみるもTLEで終了(累積和という考えが頭になし)。
結果151位。まさかの本戦へ。かなり問題セットとの相性が良かった(sigma君に大感謝)。
・CODE FESTIVAL 1日目
知り合いと思われる人が3,4人くらいしかいなく、顔を知ってる人は5,6人というかなり戦々恐々とした面持ちで会場へ。周りみんな強そう~~~ 周りみんな知り合いっぽい~~~と思いながら席に着く。参加番号って学年順だったみたいですね。
朝兼昼ご飯を食べていったら昼ご飯が置いてあったので、まあとりあえず食べてお腹いっぱいに(昼ご飯あるのはうれしかったけど、昼ご飯あること教えてほしかった)。
住建を見つけて色々聞く。パーカー1600点以上は厳しいねぇ~~という感じに。
始まってみると周りのカタカタ音でかなり焦る。途中から音無しイヤホンをつけていたけど最初からつけていた方が良かったかも。
A問題 Where's Snuke?
cinして判定を繰り返して見つけたら出力(なお、行と列を間違えた模様)
B問題 Exactly N points
m(m+1)/2 >= N となるような最小のmを見つけて、m(m+1)/2-Nを除いて1~mまで出力。
多分これで必ず上手くいくだろと確信したので、とりあえず提出。AC
C問題 Interpretation
400点問題だし解けるかなと思って問題を見てみるも見た瞬間にかなり険しい表情に。グラフ問題をほとんど通したことがなく、CODE FESTIVALまでにどうにかしようと思っていたが結局何も手を付けられずに来てしまったのでかなり絶望感が漂う。
連結性判定だしUnion-Findっぽいよなぁと感じ、とりあえずUnion-FindでググってヒットしたAtcoderのスライドを読むも要領をつかめず。そもそも今回の問題でどうUnion-Findすればいいのかも分からず。3,40分くらいずっと色々試行錯誤してみるも何も得られずD問題へ。(その後何回か戻ってみるも全く分からず考えるだけ無駄だった)
D問題 Pair Cards
700点問題だったので結構身構えて問題を読み始めるも意外とあっさり解法が思いついた(似たような問題をどっかで見たことがあったけど、その問題の方が注意しなきゃいけないことが多かったような)。
カードの枚数を普通に管理する配列とmod Mでグループ分けした時の枚数を管理する配列を用意して、Mの偶奇で場合分け。0,M/2 mod Mは枚数/2のペアを作れる。i,M-i mod M について枚数が多い方に対してどれだけ同じカードがあるかをチェックしてペアの数を計算。これでAC。
E問題 Cookies
問題名見た瞬間にCookie Clickerを想起したのは自分だけではないと思いたい。0枚所持で1秒間にN枚焼ける状態になるまでにかかる最小時間をdp[n]とかにして1次元の動的計画法を行った。それを利用して最小値を求めた。
N(1+1/2+1/3+...)とかの計算量なので途中で止めればO(Nlogm)とかで部分点くらいなら間に合うという算段。何回かバグらせて部分点。H問題へ。
H問題 Tokaido
部分点にアタックしようとした。i,i+1の状況は常に保たれるだろうからdpだろうなーというところまでは分かったが、O(N^2)とかになっちゃいそうだし、条件分岐よくわかんねーという感じで思考を打ち切る。終了。(C問題にかけた時間をこっちに費やしたほうが良かったなぁという気持ち)
そんなこんなで1600点。残り30分くらいからは、パーカーって2000点だったよなぁ~みたいな謎の勘違いをしてました。なぜかパーカーゲット!
700点問題と500点部分点が考察でどうにかなる系の問題で助かりました。Union-Findすら碌に知らず行ったのはアレでしたが。
本選終了後はtouristさんのインタビューをボーっと聞いていて、強い人は強いんだなぁという感想を抱きました。
食事はたらふく食べました(食べ過ぎた)。何名か知りあいと話したり、学科の上の人を認識したり。(二日間通じてそうですが、競プロ界隈に疎くてずーっとぶらぶらあてもなく歩いたりしてました)
エキシビションを見てほげーっとして1日目は終了。近くのホテルに泊まる権利を有してはいましたが、家に帰りたかったのでそのまま帰宅。
・CODE FESTIVAL 2日目
寝坊して朝トナメに遅刻する気しかしていませんでしたが、意外と早く起床。余裕をもって会場に。
この日も朝食を食べていったらお弁当が置いてあったパターン。
Tournament round1
まず2問とも見て、これはヤバいと感じる。
graphはダメだし、文字列もアレだし・・・
とりあえずB問題100点を取ってお茶を濁しにいこうとする。なんかバグったりしたけどとりあえず100点。
A問題に取り掛かるも完全な誤読。終了。(Bの部分点をもうちょっとやるべきだった)
まさかの100点で通過。ダメもとでやってみるもんだね。
Tournament round2
同様の作戦で200点部分点を2つ取りに行こうとする。
A問題の200点を取った後B問題の200点へ。バグらせる。2次元配列の引数を間違えました。以上200点、通過ならず。
A問題が考察すればという問題だったようなので全力で取り組むのが正解だったかもしれない。まあB問題バグらせたのが最大のアレ。
短時間トーナメントはコーディングの遅さが如実に現れることを実感しました。もっと量やらないとダメですね。
Tournament round3は適当に眺めていましたがB問題の最初の部分点は取れそうかな?という感じでした。まあ書いてないからどうせバグらせるんだけど。
そんなこんなでその後は適当に過ごし、チームリレーへ。
・Relay
チームKでした。京大の人が多かったです。問題は下から順番に割り振っていったので、僕は最初はE問題担当に。
問題を一読して、ユークリッドの互除法でgcd求めて後はちょちょいで終わりとはすぐに分かる。
D問題の方と隣り合ってやっていたのですが、Dが魔法陣で手元で計算すれば実装なしなのに気づく。
コーディングが遅いし、あの環境で実装にもたつくのが目に見えていたので、D問題の方と交渉。実装できないんでお願いします!と言ったけど、流石にユークリッドの互除法でそんなこと言うのはアレだったかなと反省。まあ、任せた方が早いのは明白だったので許してください。
(魔法陣計算で一度計算ミスしたのは完全な失態。申し訳なさしかない。)
その後はひたすら掃除と応援。結構止めどなくやっていたように感じましたが、トップチームが早すぎてビックリ。
自分たちのチームも後半の問題で一発通しが多く追い上げていたようには思いましたが、ラストの問題を残してタイムアップ。
ほとんど貢献できませんでしたが、チームリレーのあの雰囲気は楽しかったです。
表彰式で宇都鬼が現れた時はちょっと笑ってしまいました。
なんやかんや楽しかったです。来年もあったら出れるといいな。
・翌日
Union-Findを学びました。おしまい。