SnackDown 2016 Onsite Final Round 参加記

その他

CodeChef の SnackDown 2016 Onsite Final Round に uwi さんと一緒にリクルートコミュニケーションズのチームとして出場しました。

コンテスト前

準決勝にあたる Elimination Round で上位 15 位以内に入れなかったため、航空券代は CodeChef 側から支給されませんでしたが、会社が海外出張として負担してくれました。ここに記して謝意を表します。*1

コンテスト

ほぼ uwi さんの独力で結果は 6 完 11 位でした。EQUALIZE が序盤で想定解が出ていたにも関わらず Java の呪いによってかなりハマってしまってペナルティが増えてしまったのが残念です。ちなみに僕はキーボードに触りませんでした（応援係）

TREECAKE

uwi さんが通しました。

SEGTREE2

uwi さんが通しました。

XORPATH

uwi さんが通しました。

BEAUTY

uwi さんが考察によって O(N) を O(log N) にして通しました。

EQUALIZE

TLE するものの uwi さんがどう頑張っても O(QNM log(NM)) から落ちず、苦し紛れに最初のソートを radix sort にしたら通りました。*2

CATCHSM

最初に図を見ると激ヤバそうな幾何に見えましたが、よく考えれば二分探索するだけだと感じました。uwi さんも同じように考えたらしく、通していたチームがほとんどないので巧妙なコーナーケースの可能性を考えましたが、残り時間も少なかったので二分探索するだけ解を提出したら通りました。なんだったんだ・・・

RAINFALL

O(N^3 M^3 T) 解しか思いつかず、最悪 3.2 \times 10^9 になるので、もう一つオーダーが落ちるのでは、という話になりましたが思いつかずに終了。*3

GAMCOUNT

僕の伝え方が悪かったようで、ちゃんと伝わっていれば解けたかもしれないとのこと。申し訳ないです。

感想

uwi さんや hogloid さん、sugim48 さんは自分とは異次元の強さなのは普段のコンテストでも知っていましたが、オンサイトで肌で感じました。今回のコンテストで僕の貢献はゼロ未満だった *4 ので、仕事を辞めて競プロに専念すべきではないかとも考えましたが、思いとどまりました。幸い、競技プログラミングに好意的な会社なので、修行を仕事に組み込みつつ、今回の悔しさを忘れずに鍛錬を積んでいきたいです。

コンテスト以外








*1:ちなみに、リクルートコミュニケーションズは競技プログラミングの会社ではなく、広告系の会社です。他の部署は知りませんが、エンジニアの部署は 30 人くらいで、インフラエンジニアが数名、フロントエンジニアが数名、データサイエンティストが 10 人くらい、アルゴリズムを実装している人（何という名前が付いているか知らない）が 10 人弱くらいいます。学習への支援がやたら手厚く、学会出張や勉強会開催、プロコン部活動に予算がつきます。今回の出張もその一環だと思います。

*2:後で hogloid さんに聞いた感じ想定解だったらしく、Java の厳しさを感じました。

*3:後で hogloid さんに聞いた感じ想定解だったらしく（おそらく、最大ケースばかりでないためこれで通る）、CodeChef への憎しみを感じました。

*4:実力に不相応なオンサイトコンテストへの出場は通常存在し得ない