CODE THANKS FESTIVAL 2017 参加記

0日目

前日泊で来る人達とボドゲをする会に参加した。not my fault とインサイダーゲーム をやった。その後、東京物価高い！夕飯安いところがない！と探した結果ロイヤルホテルホストが見つかったので夕飯を食べた。オムライスおいしかった。前泊ホテル組が深夜までボドゲやってるのを見て俺も前泊して～～～といいながら帰る。

当日

無事起床AC。ゆりかもめに乗って会場に向かう。初のオンサイトではじめてTシャツをもらう(わーい)。着ようと思ったけどトレーナーの上からTシャツを着るのは不可能だった(それはそう)。コンセントつないでも充電されないと思って運営の人を呼んだら電源タップのスイッチが入ってないだけでとても申し訳なくなった。そうこうしていたらコンテスト開始時間になる。

A問題

maxを取ればいいとわかるので投げると通る。
それにしてもFAは早すぎると思う。

B問題

Sの後ろの方で回文になる最長のものを数えればいい。制約が小さいので全探索ができる。
ここまではすぐわかったが回文判定でindexを考えるのが意外と大変で微妙に手間取った。

C問題

今の時点で一番時間が短い機械を動かす貪欲をすればいい気持ちになったのでpriority_queueをすると通る。ペナルティないしとりあえず出しちゃえ！ｗと思って証明はしてない。

D問題

点数と制約、倍数と書かれた雰囲気からどうせgcdかlcm使うんだろうなーと思う。思うがどこに使うがよくわからなかったので実験する。実験すると互いに素なときとそうじゃないときで場合分けすればよさそうという気持ちになったので提出すると落ちる。
手元の実験でn,mが互いに素なときとn,mが割り切れるときしかつくっていなくて抜けているケースについて無駄にハマっていたが、気づくとm-gcd(n, m)っぽい。投げると通る。
この問題に30分溶かして雲行きが怪しくなってくる。

E問題

インタラクティブでマジかーと思いながら読む。似たような問題をパズルで見たことがあった ので同じように適当に枚数に差をつけて探していくんだろうなーと思ったが何かうまくいく解法が思いつかない。F、G、Hを先に読むことにする。

F問題

O(NK)のDPが自明。何か謎の制約があるけどだから何だという気持ちになる。順位表を見ていると割と通している人がいて考えるけど何も思い浮かばない。

G問題

頂点a,bを同時に使えないのをフローで表現して埋める燃やすみたいなのを考えるけどグラフがうまくつくれない。グラフで書いて色々考えるけど何もでてこない。N<=40の制約から半分全列挙な気持ちになる。dp[S] = (Sが選べる集合か)みたいなのを前半と後半でつくる！みたいなのをやろうとするがマージに2^20^×2^20かかることに気づいて真顔になる。

H問題

クエリ先読みしてunion-findとか考えるが順位表で解かれていなさすぎるので考えるのをやめる。

E問題(2回目)

よくよく考えると適当に枚数に差をつけてやれば一意に定まることに気づく(遅い)。もたもた実装しながら出すと通った。残り1時間で不可能そうなのが3問残っていてつらい気持ちになる。

F問題(2回目)

制約が何もわからないので実験していると何か規則が見つかった気持ちになったので出すと落ちる。あとから考えると試してたケースが偏ってただけだったΩ＼ζ°)ﾁｰﾝ

1300点でオンサイト75位だった。レート順50位だったのでかなしい気持ちになる。
コンテスト中食べてる余裕がなかった焼肉弁当を食べながらtwitterでつらいつらい言ってるとchokudaiさんの解説が始まる。Fが頭よすぎてすごい。弁当食べてたらご飯の準備が始まったことを知って真顔になる。

コネクションハントをやる。確実に被るけど何も思いつかなかったので好きなデータ構造を聞いて回っていた。union-findとかセグ木が多かった。chokudaiさんにCODE FESTIVALのロゴを何も見ずに書いてくださいと言われたのがおもしろかった。

🍣と🍕を食べながらtwitterでよく見かける方と話をした。TLがリアルで再現されるオンサイトならではので楽しかった。

まとめ

めちゃくちゃ楽しかったです、リクルートさんありがとうございます。
オンサイトに参加できるような実力をつけていきたい。