CODE FESTIVAL 2015 参加記
CODE FESTIVALという競プロのお祭りに参加してきました
予選A : 4完136位(ここで通過)
予選B : 寝過ごした
行き路
筑波からだと1.5hぐらいで着くので8時起きの8時半出発
電車で隣になったオッサンから刺激臭がしてつらみポイントが貯まる
ちょっと歩こうかと思って神谷町で降りたら会場まで登り坂になっててつらみポイントが貯まる
到着して席に着くと隣が知り合いでつらみポイントが減る
本戦
[A]
文字列の長さ見るだけ
[B]
Nが小さいので愚直に確率計算 →なんだかWA
doubleの誤差のせいかと思って場合の数計算 → オーバーフローしてた
(ここで一旦飛ばしてC〜E解く)
確率計算の時の÷6を÷8にしてみる → AC
なにこれこわい
[C]
貪欲な気もしつつ念のためDFS
(ペナルティ無いし、ダメ元で貪欲投げても良かったな…)
メモ化してなくてTLE → メモ化したらAC
[D]
減るとしても1だけっていうのに早めに気づけたのが幸い
一番重複してる区間群の最初と最後を探して、その最初と最後を内包するボタンがあったら(最大重複数-1)、なかったら(最大重複数そのまま)。って感じで実装
最大重複数を配列で持つと配列への入力時にTLEしそうだったので累積和で持った(実際に最大重複数をチェックするときは配列の頭から順に見るのでオッケー)
forの範囲ミスって2WA生やしつつもAC
[E]
後ろから適用が面倒に感じたので処理の最初と最後に文字列反転させることにした
手計算してみたら！の前にある-には意味が無いことに気づくので最初に消す
「--」→「」、「!が奇数個」→「!」、「!が偶数個(>0)」→「!!」ってルールで変換
途中で3WAほど食らったけど、そのたびに適当なケース試して手計算と違ってデバッグして…を繰り返した(結構すぐWAケースが見つかったので幸い)
順位表見たらGがそこそこ解かれてたので見てみる → ナムアミダブツ！1,000,000,007だ！
(1,000,000,007というか数え上げへの苦手意識ほんとにどうにかしないとまずい)
いろんなケース考えたりしてたら時間がきて終了
結果として5完の119位でした。Bでつまづいたのが結構大きい…
でもパーカー圏内なので満足です
自由時間とか
両日ともほぼセッション1のとこにいました(うなぎ、ペアプロ、LT、rngと聞いてました)エキシビションマッチは座席の目前にrngさんのディスプレイがあったのでずっと見てました。タイピングめっちゃ速い…(速いというか、記号や数字が混ざっても速度が落ちてないように見えた)
ボドゲとか書道はセッション見てたらやる時間なかった
ホテルに移動。22時台からごちうさを放送してるTOKYO MXに感激する
終物語→あの花→うたわれと見て就寝。そういえばあの花の映画見てないな…
ホテルのお湯出るマシーンの隣にプラスチックのコップが置かれてたの最高にクソUIだと思います
あさプロ
眠くて難問やると寝そうだったのでeasyからやっていくことにした
[A]
iを100までループさせてi*i>=Nになるときにi*i-Nを出力するだけ
[B]
文字列を道端で拾う世界とは一体…うごご
長さが奇数なら無理で、偶数ならs[i]とs[i+n/2]の不一致数を数えるだけ
[C]
ソートして点が高い方からk-1個選んでもにょもにょ
n==kのときが若干厄介で、0点でもいい判定をするときにa[k-1]を足してテストしていたが、n==kだとa[k-1]が2度足されるのでバグってしまう
入力1行目のN K M Rを見てM.K.Rを連想し頭の中でガチマッチが始まった
[D]
2重ループで始点を決めて、メモ化DFSで最大長を探索
メモ化してなくてTLEしたあたり全く成長してない…(本戦でも同じことした)
easy全完したのでmiddleに移動
[E](MiddleのC)
白は黒が置いた方にしか置けないので黒のことだけ考えればいい
ひっくり返す白の数が少ない方を選ぶだけでよかった(貪欲法)
黒連続何個、白連続何個、とかいうのはdequeで管理
[F](MiddleのD)
凹凸をなるべく均す方が少なくなるなーとか考えてたりしたけど結局時間切れ
5完してeasy20位、middle34位でした
チーム対抗リレー
ゑって文字が入ってる名前のチームです(忘れてしまった)
自分はDのピザを担当。上からk番目と下からk番目とを足したの全部一緒じゃね？ って気づいたら3行実装でAC
あとはFのグラフ列挙を手伝ったり、WAのコードとにらめっこしてたら終わった
ハッピーアワーはトイレ行ってたら実質終わってました(表彰が始まってた)
帰り路
久々に神田でラーメン食うぞと思ったけど値段的に松屋2回分だと気づいて足が止まった
結局つくばに帰って松屋に行きました。茄子のやつ美味い
まとめ
こどふぇす楽しいので行きましょう。青コーダーでも大丈夫です
来週もオンサイト(模擬地区)だ、がんばるぞい
