11/26~11/27に行われたCODE FESTIVAL 2016に行ってきたので参加記を書きました
予選の話
予選はAとBに出てました。
コンテストの結果、予選Bを4完して84位で突破できたので、去年に引き続いて本戦に行くことができました。
CODE FESTIVAL 2016 qual A - CODE FESTIVAL 2016 qual A | AtCoder
CODE FESTIVAL 2016 qual B - CODE FESTIVAL 2016 qual B | AtCoder
----------- 1日目 -----------
一日目は11時半ぐらいに会場のベルサール汐留につきました。
会場に入ったら、Tシャツやトートバッグ、ノート、軽食などがもらえました。着く前に朝マックしてたので、軽食はコンテスト中にゆっくり食べてました。
本戦
始まりは12時で、本戦のコンテスト開始は12時半でした。
CODE FESTIVAL 2016 Final - CODE FESTIVAL 2016 Final | AtCoder
開始前、通信環境が微妙に遅くて大丈夫かなと思ったけど、コンテスト中は問題なく参加することができました。
本戦中は、A(AC)->B(AC)->C(ハマる)->D(AC)->E(ハマる)->C(AC)->E(部分点)みたいな流れで辛い感じになって、結果は2000点、97位でした。
言語は全てPythonでした。
A問題: 文字列を探すだけだったけど、最初はサンプル通りに'A'~'J'までしか扱ってなくて一回WAくらった。
B問題: 少し考えて、1~Kまでの総和がN超えれば作れそう、と思って実装したら通った。
C問題: 全て辿れるか計算するために使ったunion-findでハマった (YESなケースを、要素のparentが全て0に属することを利用して判定してるつもりだった)。
C問題のunion-findでparent整理するのを忘れてsum(parent) == 0とかしてて判定してハマったのつらい
— やけぬる (@jken_ull) 2016年11月26日
D問題: 少し悩んだ後、まず
E問題: 方針で苦戦したけど、最終的にx枚焼くのにかかる時間をメモ化したdfs(x)として求めたら部分点が取れた。最後に満点狙ってたけどダメダメだった。
E問題は絶対三分探索で通すマンになってたけどだめだった (並行になるところがつらぽよだった)
— やけぬる (@jken_ull) 2016年11月26日
あと、どうやらE問題満点よりもF問題のほうが楽だったらしいので、E部分点取った時点でF問題に目を通せばよかったなと思いました。
とりあえず1600点以上でパーカーがもらえたので良かったです。去年の黒いパーカーとは対照的な白いパーカーでした。
本戦の後
本戦終わった後に、touristが受けた質問に答える形でトークしてて、強い人すごいなー、環境や経験の差は出るんだな、と聞いてて思いました。
その後は、ご飯🍣🍖🍕を食べて、その後トークセッション聞いてました。秋葉さんのトーク面白かったです。
🍣！🍖！ pic.twitter.com/ZdDQ2ZGOtL
— やけぬる (@jken_ull) 2016年11月26日
今年初めてのクレーンゲームもやったけど一回のみのチャレンジだったので、景品であるタオル入手難易度がめっちゃ高かったです。
何人か取ってる人はいたけど、クレーン技術0の自分は当然だめでした...。
エキシビションマッチ
一日目最後のイベントであるエキシビションマッチは、日本勢と海外勢の本戦上位陣がそれぞれチームとなって解いてて、それを観戦していました。
CODE FESTIVAL 2016 Exhibition(Parallel) - CODE FESTIVAL 2016 Exhibition(Parallel) | AtCoder
見てて問題がむずそうでつらそうだなーって感じでした。とりあえず自分もA問題に手を付けてみたけど、うまい解法が思いつかず終わりました...。
上位陣の実装を見てて、コーディングがめっちゃ早くてすごいなと思ってました。
1日目はこれで終了で、21時半くらいに解散したのでそのまま帰宅しました。
---------- 2日目 ----------
二日目は起床に成功して、朝早くの8時半くらいに会場につきました。
会場には朝食のおにぎりが用意されていたので開始前に食べていました。
トーナメント
朝はトーナメント形式のコンテストが行われました。
トーナメントは1グループ8人でいくつかのグループに分かれ、1,2回戦は30分2問で8人中上位4人が勝ち残り、1回ごとに隣?のグループの残った4人と合併する、そして最後の3回戦は40分2問で8人中上位3人勝ち残る、というルールでした。
問題については部分点が多めに設定されてて、短時間で部分点をいかに早くとるかみたいな感じでした。
短時間コンテストの経験がなくて少し焦っていたので、なかなか解法が思いつかなかったり、思いついた解法を実装しても通らず、思ったように部分点がとれなかったです。
実装は全てのRoundでPythonを使いました。
Round1: A問題は頂点と
を繋げたKruskal法で200点ケース (もしかして通るかもと思って複数ケースを一括でやったけど当然TLE)。B問題は二分探索で200点以上狙ったけどWAになって、結局終了直前に簡単な100点ケースのみ取った
Round2: A問題は簡単な200点ケースをさっさととってから別の解法を考えるも、確率の扱い方が分からず。それからB問題に移って、やるだけの200点ケースをとってから別の解法を考えたけど、結局だめだった
Round3: A問題でWA出しまくりながらなんとかメモ化dfsで200点ケースがとれた (100点ケースのdpはわからずソートしてたりした...)
部分点200点通らねえぇって発狂してたら、通らないケースは実はN=Mのケースだったというオチ(場合分けして未実装だったやつ)
— やけぬる (@jken_ull) 2016年11月27日
結果的には、1回戦はグループ5で2位、2回戦はグループ3で4位、3回戦はグループ2で3位でした。各Roundでうまく部分点をとって最後までぎりぎり残れた感じになりました。
↓上からRound1, Round2, Round3の順位
そして、最後まで勝ち残ったので、ステッカーが全てもらえました！
なんとか最後まで勝ち残ってステッカー揃いました #code_festival pic.twitter.com/PGBh5QPenC
— やけぬる (@jken_ull) 2016年11月27日
その後は昼飯として弁当を食べて、トークセッションでいろいろ面白い話を聞いていました。
チーム対抗リレー
最後はチーム対抗のリレーで、自分はチームIでした。机にはチームカラーのTシャツと、今年もレッドブルがチーム全員分置いてありました。
チームの中ではG問題を担当してて、少し考えたらうまい解法を思いついて一発でACすることができました。去年のようにハマってチームに迷惑をかけなくてよかったです。
G問題は、
- ボールの位置と、瞬間移動含めたボールの位置の候補を管理する配列を用意
- Q回のシャッフルをシミュレートしてボールの位置や配列の候補位置をスワップしながら、ボールの位置(x)から瞬間移動した時の位置(x-1, x+1)を候補として配列で保持
- シミュレート後に配列から、瞬間移動を含めてボールが存在し得る座標の候補数を数えて出力
みたいな感じのをC++で実装してました。
チームでは解けた人が解けてない問題を考えて協力しながら解いてたのですが、それでもK問題のみ解けなくて、11問中10完で7位になりました。
表彰式
リレーの後は表彰式でした。
今年も書道コーディングやコード川柳で素晴らしい作品が表彰されてました。
今年、表彰された方の文字を書いていただいてた書家さんは宇都鬼という方で、とても面白い方でした。
他にも、太鼓の達人や体力測定で優秀な方々が表彰されていました。
表彰の後は恒例の参加者全員の記念撮影を行い、それが終わった17時過ぎくらいに解散という感じで終わりました。
