CODE FESTIVAL 2016 参加記 - CTFとか競プロについて書いていきたいブログ

11/26-27にあったCODE FESTIVAL 2016に参加してきました。

予選

ABは参加するつもりだったものの気づいたら終わっていた。

なので、Cに参加したところ2xx位だったが通過。

一日目

新橋駅到着後、マクドナルドの隣のエスカレータを上った先の道が分からず迷子になった。他の人についていった結果、無事到着。

到着すると机に軽食があった。

本選

CODE FESTIVAL 2016 Final - CODE FESTIVAL 2016 Final | AtCoder

A: "snuke"を見つける

B: 小さいほうからiを足していって、N以上になったらiを引けるなら引いていく

C: Union-Find木で要素が二つ以上ある木が一つになれば良いと勘違い。普通にやった部分点はなんとか取れた

D: 解説通りの方法だったはずだけども、通らなかった。

Submission #993871 - CODE FESTIVAL 2016 Final | AtCoder

E: DPで使う値が分からなかった

F~ 知らず

結果ABとCの部分点で500点でした。

本選後

ハイパーロボットなるボードゲームやってました。

一手のやつでUFO券もらってしまい申し訳なかった。

その後、夕食取りに行ったらほとんど尽きてました。

エキシビジョン

CODE FESTIVAL 2016 Exhibition(Parallel) - CODE FESTIVAL 2016 Exhibition(Parallel) | AtCoder

パンフだと任意参加ぽかったのが、実は全員参加だった。

まったく分からかったが、Openで通している人がいてびっくりした。あとタイピング速度も。

0点で6位タイですね。

二日目

前日と同じ道なので迷わずに到着。

机の上に鮭のおにぎりと角煮か何かのおにぎりがあった。

トーナメント

前日の順位が近い人同士のトーナメント

R1

Round1Group27 - Round1Group27 | AtCoder

Aはグラフだしよくわからないと思ったので、Bに挑戦。

Bで400点がDPよくわからないと思ったので、200点に挑むもよく分からず、100点のコードを書く。結果的に100点ボーダーだったのでさっさと取れる部分点を取るべきだった。

結果、100点で6位。

R2 (Open)

CODE FESTIVAL 2016 Elimination Tournament Round 2 (Parallel) - CODE FESTIVAL 2016 Elimination Tournament Round 2 (Parallel) | AtCoder

AのほうがBより分かりそうだったので、Aに挑戦。

期待値問題はよく知らないので計算した結果、一回ごとに2p距離が縮まることが分かった。

距離が奇数の場合、1回使ってX-1かX+1に移動するのでそこも書いて提出したら29分で満点が取れた。よく計算すると、(int)((x+1)/2)/pで偶奇関係なく出せるみたいだ。

R3 (Open)

CODE FESTIVAL 2016 Tournament Round 3 (Parallel) - CODE FESTIVAL 2016 Tournament Round 3 (Parallel) | AtCoder

さっぱりだったので途中でボドゲを遊びに

トーナメント後~リレー前

宝石の煌き(Splendor)というボードゲームをプレイした。

ルールは簡単だけど、他プレイヤーとの駆け引きが難しく非常に面白かった。

その結果、またも食事に出遅れて弁当が四つのうち二つ無くなっていた。

その後再びボドゲとUFOキャッチャーを遊んだ。UFOキャッチャーは二回分券があったが何も得られなかった。

チームリレー

CODE FESTIVAL 2016 Relay (Parallel) - CODE FESTIVAL 2016 Relay (Parallel) | AtCoder

海外勢1と国内勢10でチームを組んで11問で競う。解放は協力できるが一人一問コーディング必須。チーム内で本選ランキングが最下位だったので6位の方とペア？になりA問題を担当。

A問題は並列の合成抵抗の計算をするだけだったが、テストした結果C++で小数の表示桁数がデフォルトで足りないのを忘れていたので、とりあえずprintfで出力しAC。コーディングスペースから戻ると問題がどんどん解けていたらしく、プロのすごさを感じた。

その後、残ってたI問題を何人かで考えていた。偶数の場合に対角線が鬼門だという雰囲気だったが、複数人が同じ相手を見ていてもいいということをチームメンバーが発見し、実際に4人の場合のパターンも見つかった。

その後ずっと考えていた結果、n人を1人とn-1人に分けて解くアルゴリズムを思いついた。

すでにI問題の解法はチーム内で発見されていたらしいが、こちらのほうが実装が楽らしいので自分の方式が採用されたらしい。

Submission #1001309 - CODE FESTIVAL 2016 Relay (Parallel) | AtCoder

後日実装してみたところ、無事ACできた。奇数人の場合の解法はずらしていくだけの解法が出ているので、n-1人はn-2回の間に全員を見ることができる。1人の方もn-2回の間は同様に誰でも好きに見られる。これを改良して初回にn-1人のうち一人が1人の方を向き、最後にそいつ以外が1人の方を向き、そいつは最初に見るはずだった相手を見て、1人の方がそいつを見るようにすると、全員を見ることができる。

チームは最終的に9問正解でに12，3位だった。

その後のイベントでは見たことのあるようなおさるのような書道家がでてきたり、集合写真を撮ったりした。