NSTomoS’s blog

NSTomoSの情報系の記録用ブログです.

CODE FESTIVAL 2016参加記

r.recruit-jinji.jp

CODE FESTIVAL 2016参加記

今回はCODE FESTIVAL 2016に参加させて頂いたのでその参加記です.

僕は二年前競技プログラミングを始めたての頃にCODE FESTIVAL 2014に参加して,去年CODE FESTIVAL 2015は惜しくも予選落ちしCODE THANKS FSTIVAL2015に参加しましたが,今年はなんとか最後の予選で通って本戦に参加できました.

一日目

本戦

本戦の配点を見た時点で「3完すれば万々歳で,パーカー(1600点)は夢のまた夢だなぁ」と思っていましたが,びっくりするほど調子が良く最終的にABCD満点E部分点の4.5完2000点で100位ぴったりと大健闘してパーカー貰えました.

以下ざっくりとした解説です(オーダーはテキトーなので自信ないです…)

A問題(100点)

入力を受け取って O(HW)で愚直に実装するだけで通る.

B問題

配点の最大値の最小値は N 1,2,3,4,5,6,7,8,9,10…と増えると 1,2,2,3,3,3,4,4,4,4…と増える(頭悪いから手で試して求めた)ので, O(N)で求まる.配点の最大値の最小値さえ求まれば,あとは配点の最大値の最小値以下の数を大きい順に和がちょうど Nになるように貪欲に求めていけば求めたい集合が求まる.

C問題

言語でUnion Findを使って,各人の使える全ての言語を同じ集合にする( O(MKlog(M))).使われていない言語がない保証があれば集合の個数がMであれば”YES”を出力で良いのだが,そうではないので,ある一人と他の人のそれぞれ最初の言語が求めたUnion Findで同じ集合内にあるかを確認すれば通る( O(Mlog(M))).

D問題

それぞれの数の枚数,それぞれの数のペアの数,それぞれの数のペアになれなかった枚数, mod(M)を取った数のペアの数, mod(M)を取った数のペアになれなかった枚数,を管理して,先に足してMになるペアを組んで,それに応じて同じ数のペアを減らし,最終的に数え上げるゴリ押し解法で通った.

なんとここまでをノーミスノートラブルで1時間で解き切った

E問題

最初自明なDP解法を思いつくも部分点でもTLEすると思い,時間を前から追って最終的に時間短縮になるなら貪欲にクッキーを食べる手法を実装するが,10ほどWAを出して1時間以上を溶かした…諦めて自明なDPを駄目元で試したら部分点解法が通った…

E問題の部分点を取った段階で残り30分だったのでそれ以上は解けませんでした…

1日目のその後

体力測定で体力のNASAを実感しました…

同じ大学の先輩方とボードゲームに勤しんで(殺伐とした殴り合いをして),エキシビジョンマッチを観戦しました.

余談ですが去年一昨年よりもホテルが綺麗な所だったんですがもしかして今年は全体的に予算が増えたとか?

二日目

トーナメント戦

なんとトーナメント戦で普段負けまくっててたまたま前日の本戦で勝ってしまった同じ大学の強い先輩と最初から同じグループになりましたw結局Round1では1位で勝ち抜けましたが,Round2で完敗しそこで敗退しました…

Round1A問題

Union Findでコストの小さい辺から貪欲に繋いでいくと200 点の部分点解法だった.

Round1B問題

自明な100点の部分点解法を通した.

Round2A問題

200 点の部分点解法が自明である事に気付くのに遅れて時間がかかった…

Round2B問題

愚直に貪欲に魔法を使ったら200 点の部分点解法だと思ったがWAで時間切れして最下位になった…

Round3A問題

DPで通ると思ったが通らなかった.(多分実装がザルだったのと考察がだいぶテキトーだったのでDPでもきちんとやれば通りそう?)

Round3B問題

A問題をのんびり考えてたので目を通してすらいない…

空き時間

いくらのお弁当美味しかったです. ボードゲームは昨日の殺伐とした殺し合いとは逆にプレイヤーが必死に協力するゲームで楽しんで,クレーンゲームでは一番欲しかった手拭いを手に入れました.

リレー

Aチームでまた同じ大学の先輩と同じでしたww

変に本戦で順位が高かったためにG問題を担当しましたが,結局自力で解法が分からず強い人(DEGwerさん)に教えてもらって実装しただけで終わりました…結局チームは最下位で何も役に立てなくて申し訳なかったです…

G問題(教えてもらった解法)

最初から玉の入ってるコップの位置を管理しながら,コップに玉が入ってるかどうかの情報をクエリの通りswapしつつ,最初から玉の入ってるコップの左右にも玉が入ってるように更新すると,最終的に玉の入ってるコップを数え上げる事ができる.

感想

ボードゲームや様々な方のトーク,交流などがありとても楽しいイベントだった. また,code festivalの問題は典型アルゴリズムの適用よりも解法を考える事が重視される問題が多く???,僕でも解けるような問題(それでいて簡単には解けない)が他のコンテストよりも多いのも良いと思った.まだあと二年は参加出来るので,来年再来年も予選通過してぜひ参加したいし,知り合いにも是非勧めたいと思った.(このエントリー見た人競技プログラミング始めましょうw)

(よくある感想的なのしか言えませんが本当にとても楽しいです…)

今回はリクルートさん本当にありがとうございました. また

その後

せっかく東京に来たので,駅メモの君の名は東京イベントを消化して今は宿です. 明日は下宿探しの下見(各地域の雰囲気とかを見にぶらぶら)する予定です.