紙コーダー未満

主に競技プログラミングについてです。Topcoder(togatogah)、Codeforces(togatoga)に参加してます。

CODEFESTIVAL 2015参加記

参加記

去年の本戦は予選落ち
去年のThanksの参加記togatogah.hatenablog.com

予選

・予選A 3完(落ちる)
・予選B 3完 + 部分点(通る)

1日目

・興奮して目が覚める。
・研究室で身支度を整えて、会場までの経路を調べる。
・品川のバスを予約していたことに気づきメールを送る(すいませんでした)
・会場に到着したが30分前のため会場に入れず、コンビニで時間を潰そうと思ったら研究室の先輩と出くわす。(今年僕がこどふぇすの事を伝えて誘ってあっさりと本戦出場を決めた強い人)
・会場入りしてさっそくスタッフの人と軽くおしゃべり、受付してた人も某ツアーの時にスマブラ一緒にやった人だった。
・134番のふだを渡されて、Tシャツなど受け取り席につく。
・本戦開始までに、時間があり適当にぶらつきながらお菓子をつまむ。

コンテスト

・5問以上がパーカーと発表され、去年の難易度ならワンちゃん
・ネットワークトラブルで開始時間が45分伸びる。
・遅延までは天空のmacを眺めたり、twitterの眺めて時間を潰す。
以下本戦
All submissions - CODE FESTIVAL 2015 決勝 | AtCoder
・A invalidとvalidをミスり1WA(ペナルティなし最高)→AC
・B 色々悩んでdpを考えたがB問題からdpはないだろうと思ってサンプルから察して3.5 * Nのfloorで投げてみる。AC(ペナルティなし最高)
・C greedyに寿司を載せられるなら載せて駄目なら分解してのせる→AC
・D sortして累積和かなあと思ったが全然思い浮かばず、そういえばsegtreeで区間和でRMQあったようなと思いぐぐる→あった→コピペして少し直す→AC
・E --は消えるよなあとぼんやり思い、取り敢えず-1,0,1のサンプルを作り手で色々とシミュレーションをする。途中!*!*!なら!にできることがわかり、一つでも変更できたならば、また全て試すという適当な実装でだす→AC
・ここでパーカーゲットして興奮する。
・順位表を確認したところ70番ぐらいで、上位陣はGを解いてる人が多かったためGを読む→DPっぽいなあ→わからず
・Fを読む。→無理だ
・Hを読む。→3つ以上は重なるとアウトだよなあとぼんやり思う→無理
・Gに戻って適当にdpっぽいのを書く→終了
ooooo----- 500 87位 / 200位で終了
・G問題を区間を持つDPで解けることが判明
・解説まで去年のThanks勢で一緒だった人と話して取り敢えず、お互いにパーカーが取れたことを喜ぶ。
・解説を聞く→F問題無理ゲーだった→G問題やはりよくわかんねー
取り敢えず、最低限自分が解けなければいけなかった問題を解けたのでそこそこ満足でしたが、やはりあと1問解きたかった。

コンテンツ

・ICFPCのお話、ガチガチのCSの知識がないととてもじゃないけど太刀打ちできず年によってはもし参加しても全く歯がたたなそう
・秋葉さんのペアプロ オイラーツアーの性質を学んだだけでも良かった。
・LayCurseさんの作問の話、良問について語った時にchokudaiさんがひたすらうなずいてた。作問は興味はあるけど時間が取られそうだし、まず問題が思い浮かばない。
・フードタイムで適当に食事を済ませてエキシビションマッチまで時間を潰す。
・本戦塾で、G問題の解説を聞くなるほどなあと関心、必ずしも解けない問題じゃなかったなあと思う。

エキシビション

・yosupoさんのエンターテイメント性が素晴らしかった。
・Misawaさんのvimがカスタマイズされていて、すごかった(小並感)

ホテル

・hadroriさんがご飯のツイートをふぁぼってご飯についていく(blue_jamさんponyoさんとhadroriさんと僕)
・ラーメン美味しかった。
・hadroriさんと僕がホテルのカードキーを忘れて一緒にフロントで手続きをする。
・風呂に入って寝る

2日目

・目覚ましをかけたがその前に目が覚める
・バスに乗り本選会場へ

あさプロ

・あさプロmiddleで参戦
・A K - 1個とってくるみたいなことをしたがN=1の時にはまってた、最後の1個は二分探索で求めて提出→AC
・B いろいろと悩み、適当に分割してLCS求めればいいじゃん→LCSコピペ→提出→AC
・C 小さい方でマージしてけばよくね→dequeで実装→バグらせる→何とかAC
・D 残り10分のため適当にお菓子を食べて時間を潰す
ooo- 400 58位 / 119位
まあ、まさしく本戦の順位通りだなあと思う。

コンテンツ

・タンブラー欲しさに音ゲーをやる久しぶりに太鼓の達人をやったが難しすぎ・・・
・ライトニングトークで坂本さんのゲームAIの話を聞く、やはりゲームのルールは複雑すぎると大変だよなあ、あとビジュアライザーがしっかりしてると面白そうだなあと思う。

チーム対抗リレー

RGB_colorで参加
・F問題を担当 N個の頂点かつN本の連結無向グラフの数がいくつかを数え上げる問題→適当にグラフ列挙してもいいけど手で数え上げられるよなあと思い手で数え上げる方針にする。→他の人と協力して数え上げた→CATで提出(WA)→数え間違い→WA→WA→
WA→WA→WA→WA・・・・・→数え間違いが発覚→これで絶対あってるだろ→WA→C++で提出→AC(17WA)
CATの提出で改行してなくてくっそハマってた本当にこれはチームメイトに申し訳なかった。
・そして30秒後にG問題AC全完
・あとは他のチームを眺めながら、みんなでどう解いたか簡単に話しながら待つ
初めてのチーム戦だったが最高に楽しかった。ACした時の興奮は個人戦で味わえないような喜びだった。あとズバズバと問題を解いていく、チームメイトが凄かった。

ハッピーアワー

・みんなで適当におしゃべりしながらコードを見て、どう解いたか掘り下げていった。
・各賞の発表でモニョ先輩が書道で受賞する。ヤバイ漢字が一瞬頭をよぎったが普通の漢字を書いてほっとする?

閉会式

・ドローンで記念撮影して終了
・帰宅
全体の感想
今年最後のチャンスなので参加できて良かったです。
最高のコンテストでした。スタッフの方々ありがとうございました。