CODE FESTIVAL 2015 参加記
リクルートさんの開催する CODE FESTIVAL というイベントに参加してきました。
http://recruit-jinji.jp/code_fes2015/
予選
予選 A も予選 B もゴミのような結果でしたが、なんとか通過しました。
Day1
asa!
5 時 15 分起床に成功する (品川まで 3.5 時間かかるところに住んでいる)。できたら来年は前泊したいです。 起きてすぐ家を出られるわけでもなく、新幹線で集合 5 分前とかに行くのは難しいです。
本戦
A コード川柳
やるだけ (このレベルの問題があると安心する)
B ダイスゲーム
3.5 掛けるだけでは… → 最後のサンプルに助けられて AC。
C 寿司タワー
KUPC2015 の A 問題感。前からとる貪欲を投げてみると通る。
D 足ゲームII
ルールの書き方が難しいけど、区間を 1 つ取り除いたときにある座標で重なっている区間の数の最大値を最小化するということだろうか…
区間の貪欲っぽい問題は嫌いなのでとばす。
E ショートコーディング
プログラムへの入力として考えるべきなのは -2,-1,0,1,2 だけだと思う。
記号をその部分集合間の関数だと思うと、要素数が 5 しかないのにそんなに長くなるとは思えない。高々 32 でしょ (謎考察)。
ビットを使った全探索を書いて投げる → WA
全列挙できていない (やばいレベルのミス)。修正して投げる → AC
D
E を解いた時点で 60 分くらいだったのでこれはパーカーワンちゃんww (偽)
D に戻ってきてよく読むと区間の加算と最大値クエリが処理できればいいような気がする。
Starry Sky Tree のことは知っていたけど、書いたことがないので kagamiz さんのブログのを貼り付ける。
けどなぜか最後のサンプルが合わない…
F 以降も考えてみたけど D より難しい。
区間への減算ができないのではという仮説が生え、いろいろ書きなおしているうちに 2 時間経ってしまった…
パーカーゲットできなかった。
コンテスト後
他の人のコードを見て、Imos して 3 回 RMQ するだけだと気づく。セグツリー使わない方法も頭いいなあ。 面白い問題を考えるところまで行けなかったのがつらい。
屋台にご飯を取りに行く。トークセッションが聞きたかったので 🍣 だけ確保してすぐ移動する。 トークセッションの席で隣になった odan さんに D で kagamiz さんの Starry (略) の実装はデフォルト引数の n がグローバルになっててはまりましたと言われる。自分もそれだった… これで 2 時間無駄にしたのか…
チームうなぎ座談会を聞く
毎年 ICFPC は面白そうだと思っているけどハードルが高くて参加できていない。コンパイラを書きますとさらっと言えるのがすごい。来年こそはチームで参加できるといいなあ。
LayCurse 氏トークライブ
ストーリードリブンの作問は難しいと思っていたのでいろいろ参考になりました。 自分が問題を考えると典型にしかならないけど、それでもまあ出してしまうのもありかなあと思った。 サインをもらうのを忘れてしまった。
残りの引換券を交換する。
エキシビション
席が Mi_Sawa さんのディスプレイの目の前だった。みさわさんのコードによくついてる }}}
の意味がわかる。
自分も A をしばらく考えていたけど分からなかった。言われてみれば確かに強連結成分分解のような気がしなくもないけどこれは思いつかない。
りんごさんすごかった。
リレーチームの顔合わせ
yosupo さんチームだった。
たまたま yuki2006 さんの後輩と同じになった。
来年は yuki さんにサインを貰いたいです。 (実際自分が通過できるかのほうが怪しい)
ホテル
ショートコーディングの A 問題だけやる。Ruby でがんばっていたら問題別で 5 位になる。
ショートコーディングを真面目にやったのは初めてだったけど、言語仕様の隅をつつくよりも、アルゴリズムを考えたほうが短くなるところが楽しかった。 yukicoder に提出された ciel さんのショートコードをいくらか参考にしながらやった。 素人としては記号だらけでぐぐりようのないのがとにかく辛い。あと Perl が強すぎる。結局 2 時くらいまで起きてしまう。
自分の期間内で最短の提出 (61 Bytes)
s=0;n,a,=$<.map{|i|s+=i.to_i};puts s/n+2*n>2*a ?"Fail":"Pass"
Day2
朝プロ
なんとか起きられたけど睡眠時間が足りていない。昨日は散々だったのでおとなしく Easy を解く。 問題は外部公開していいかわからないので一応貼りません。
A ヘイホー君と加算
やるだけなんだけど頭が働かいない。妙にバグって 3 分もかかる。
B ヘイホー君と置き換え
一致していないところを数える。
C ヘイホー君と最終試験
$N \ K \ M \ R$ の中村感。
二分探索を書く。意外とすぐに実装が終わったので提出 → WA
上限を m+1 にしていたのを修正 → AC
D ヘイホー君と削除
ライブラリの LCS を貼る。
順位表を見たら 1 位でびっくりする。
E 一次元オセロ
誤読して両方いつでも好きな方におけるのだと思ってしまう。 これに気づくまでかなり時間がかかる。
間違いに気づいた後色々実験してみると … 3,2,1,0,1,2,3, …
のような係数をかけた後に足した値を最小化すればいいような気がしてくる。
これどうやって計算するんだろう…
Imos で良さそう。
書いてみるけどバグりまくって時間内に書き終わらない…
こういうのは落ち着いて紙で考えてからコードを書かないとダメですね。
結局簡単枠しか解けなかったのでつらい…
D は LCS を知ってたら簡単だけど知らなかった後輩は苦労したらしい。
高橋 chokudai 氏トークライブ
確かにこういう逆引きが頭にあると昨日の D みたいなハマり方はしなさそう。でも DP と フロー と 貪欲 あたりの判定はすごく難しい気がする… そのへんは修行あるのみなんだろうなあ。
りんごさんトークライブ
なんだこれは… (ほめ言葉)
焼肉弁当を食べながらリレーを待つ。
チーム対抗リレー
「ゑ」が入っているチームの「く」を担当する。
チーム内で昨日の順位の降順に A … J まで割り当てることになる。
9 人チームの最下位なので A と B の 2 問を担当する。
A チーム分け
シミュレーションするだけなんだけどバグりやすそう…
前に行って書いてみると案の定バグって負の値がでるので戻ってちゃんと実装の方針を立てることにする。
少し考えると全部同じになるような気がしてくる。
おかづきさんに聞いたらそれっぽいとの同意をもらえたので Ruby で p 1005
とだけ書いて提出 → AC
交代している間に C が AC する。
B 全完
ハマりにくさで言えばこっちのほうが簡単だと思う。 OR をとるだけの実装をして出す → AC
自分の担当は終わった (遅すぎ)。
他の人担当の問題
それなりに順調に進む。みんな自分より強いので安心できる。
G が WA する。
ナップサック DP した後に負のインデックスにアクセスしていそうな部分があるのを bluejam さんが見つけるが、なぜか RE が発生していない…
加えて価値の上限が足りないような気もする (?) .
怪しい部分を直して出す → AC
なぜ RE にならないんだ…
青コーダー勢が G までと格闘している間に yosupo さんが J でいろいろ実験していたけど、法則性が見えないらしい。
H もバグっている。
しばらくみんなで考えていると G の実験結果の表に間違いがあったらしい。それを直すと法則が見えたようで、 書いたら通ってしまったらしい。 (理解できないので全部伝聞形) すごい…
H のバグが取れないのでみんなでデバッグする。
ハマると怖い系の問題で倍以上面倒くさい方法で実装している。
時間も迫ってくるが、 yosupo さんがばんばんバグを見つける.
急いで直しに行くけどギリギリ間に合わなくて、終了 1 分後くらいに AC する。
yosupo さん、普段はドイツ語キャラだけどやっぱりレッドコーダーだった。 全完できなかったけどまあ H は自分もハマると 1 時間はかかりそう。 ワイワイやれたので楽しかった。
ハッピーアワー (表彰式)
きゅうりさんがおもしろかった (konami)
まとめ
競技プログラミングのオンサイトはいくつかありますが、こどふぇすはその中でもダントツに楽しいので、来年もぜひ開催してほしいです。これだけ人数がいると知っている競プロ勢にはだいたい会って話せます。話すとモチベーションもとても上がります。自分は何か始めても約 1 週間で飽きるのですが競技プログラミングだけは 2 年以上持っているのは、オンラインやオンサイトで人に会っているからだと思う。 今年は予選でギリギリで本戦も unko でしたが、来年までにもっと練習して余裕で通過できるようになりたいです。 謎社さんありがとうございました。