ヘクトのメモ

なんとなくいろいろ書いていくと思います．

CodeFestival2016 final day1

CodeFestival2016 finalに参加しました．
本戦は43位でした．

9時30分に家を出る．
新橋駅に到着する．
汐留に初めてきたので，ここに日テレを見たり，電通の会社がここにあるんだということを知る．
地下を歩いていたら，当然右方向に迂回して地上に行かないというところが難所
会場到着

いろいろアイテムをゲットする．
touristが本当に来ていると驚く．
JAG夏合宿やICPCつくば大会で会ったkonjoさんと会って雑談する．
同じ大学のnokotaroを全探索する．

本戦開始
A snukeを探して AC
B ループで計算すれば良いのだけれど，焦って条件式を書き間違えて多少バグらせるけどすぐに AC
C 人を頂点と考えるグラフの連結判定だけど，全てチェックすると時間がかかる．同じ言語を話せるグループの中である1人をリーダーに決めてそいつに全てマージして判定 AC
D 同じ数を処理してから，Mの倍数で処理すれば良いのではという解法を思いつく．しかし，サンプルケースにお前それは嘘だよと告げられる．ということで，いろいろ考える．とりあえず，Mの倍数で優先的に処理する．余ったら，同じ数の組を多く残した方が嬉しい．
そんな方針で書く AC

ここまでで30分

E 先に見るけど，面倒だなと思って飛ばす．
F 問題を読んだら，どんな状態がいるのか考える．dp[i][j][k] i日目，頂点1を含む強連結成分の頂点数がj，頂点1を含む強連結成分に含まれていない訪問済みの頂点がk個で dp[m][n][0]が答え とりあえず，dpの遷移を書くと答えが合う．階乗を掛けなくて良いのかなと思ったけど，頂点1が属すように集合をとっているから，ダブルカウントしないはずで投げる． AC

ここまでで45分で瞬間順位は14位くらいだった気がする．
この時点でパーカーが確定して安心する．

ここからは大変だった．
まず，E問題のクッキの消費時間をAxと勘違いしていた．
次に，素因数分解でなんとかなるのではという嘘解法を投げつけたりする．

ちゃんと問題を整理すると，m回クッキーを食べるとき，

\displaystyle \min \sum_{k=1}^{m} y_k + Am
\displaystyle s.t. \prod_{k=1}^{m} y_k \ge n

という問題を解けば良い．
そしたら，いつかのSRM easyに似た問題あったなと思い出す．
\displaystyle t=\sum_{k=1}^{m} y_k
とすると， \displaystyle y_k=\frac{t}{m} が最適になる．( \displaystyle y_kは整数なので，適切に切り下げと切り上げを行いますが)
そこで，クッキーを食べる回数は \displaystyle \log_{2}(n)， \displaystyle tは愚直に回してもオーダー \displaystyle O(\sum_{k=2}^m \sqrt[k]{n})は大丈夫そうなので書く．
そうすると，サンプルが合ったので提出する．

137分でAC

あとはHの部分点をdp+segtreeで実装しようとしたけど間に合わず．
本戦は終了する．

43位でした．

この後，mayokoさんやnokotaroやbtkさんの人々と問題について語る．はむこさんを認識する．
難易度的には F < Eというのが体感

touristのトークショーを聞く．
7歳からプログラミングを始めたという事実にまず驚く (2000年代の始めはPCがある程度普及していたけど)
あと，Twitterであらかじめ投げておいた質問が取り上げられた．


ICPCはチーム戦だけど，協力して解いたりせず，個人で解いているのかという感じ

その後は自由にコンテンツを楽しみつつ，torusさんに久々に会って話しつつ，体力計測する．
闇討ちをしてはいけない人のランキングを見て，ちゃんと認識する．


秋葉さんの講演を聴く．(「Re: 続 ペアプログラミング」この方式だとタイトルの長さが毎年単調増加しそう)
ICPCで出されたあのゲームの攻略方法がよく分かっていなかったので，なるほどという感じだった．

エキシビションを観る．
例年のエキシビジョンで，semiexpさんはコーディング速度が速いことは知っていたけど，touristも速かった．(タイピング対決したらどっちが勝つのだろう) B問題でtouristが乱拓を投げて，もしかしたら通るかもしれないと思ったけど，テストケースがしっかりしていた．あと，海外勢のCUIは青い，Indeedチームは「予想通りです」と言うようにB問題を通して本当に強かった．

きゅうりさんを含めた同じホテルに泊まるメンバーで移動
ホテルに着いてから，からあげクンを食べて，必要なスクリプトを回したり，いろいろして寝る．

day2はまた別の記事に書く予定です．