読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

DDCC2016に参加しました

「DISCO presents ディスカバリーチャンネル コードコンテスト 2016」参加記です。

japan.discovery.com

今回は割と注釈芸をしています*1

予選は3完75位で、18卒枠で通過しました。

会場まで

始発でぎりぎり間に合ってしまうことがわかったので、5:10に奈良を出発し東京へ向かった。

会場がおしゃれな感じですごかった*2

進行役の女性がプロのアナウンサーっぽい人で、"""本物"""感に圧倒された*3

本戦

配点*4を見て3完を目標にした。時間が120分しかないので、B, Cは部分点を無視して700点から解きに行くつもりだった。

Aはぱっと見、普通に2重ループ回してすべての正方形を見ればよさそうという気持ちになった。しかし左上の格子点が円の内部*5にあるかだけで判定しようとしてバグらせていた*6。正方形の4頂点すべてが円の内部にあるかを判定するようにしてAC。15:16(遅い)。

Bは「この問題予選で見たことある!」となったが中身はちゃんと難しくなっていた。部分点は真ん中から鏡合わせにつなげばよさそうとわかったが満点解法は10分くらい考えてもわからず。しかたないので部分点を取りに行く。300点確保。

Cに行く。部分点は文字列を頂点とみなしてグラフを作るとダイクストラでいけそう。満点はどこから手をつけていいのかわからなかった。しかたないので部分点を取りに行く*7。こちらは実装が結構しんどくて、typedef map<string, vector<pair<string, int>>> Graph;みたいなものをひいひい言いながら書いていた。これを通した時点で71:32。

Bに戻る。いろいろ考えていると、今残っている中で最長のものの長さはコストに加算せざるを得ない……ならばそいつと一緒にできるだけ長いやつを道連れにしてやればいい、というようなことを思った。制約に甘えて毎回ソートするO(N2 logN)解法を投げる。AC! 考察中は円だとだるいので、後で載せる図のように長さの順だけ書いて考えていた。

残り時間はCを考えていた。いろいろ書いていると、"10"があったらそこは反転していなければならないのでそこで左右に分かれるんだろうという気がしたがまとまらず。D, Eはちらっとみたけど皆目見当がつかないという感じだった。

f:id:pakapa104:20161205173843j:plain:w480
▲コンテスト中に取ったメモ

f:id:pakapa104:20161205173848j:plain:w480
▲Bの考察

f:id:pakapa104:20161205173852j:plain:w480
▲†闇のダイクストラ

特別ビュッフェ

おいしかった。なんかお寿司が知ってるお寿司と違った。サンドイッチのパンがクロワッサンっぽい感じでブルジョワっぽかった。チョコフォンデュを初めて食べた。

こどふぇすで会おうと思っていたものの会えなかったtorus711さんを発見したので会いに行った*8。某件でお世話になっているお礼を直接述べたかったので述べる*9。本戦の問題について何人かで話しているとちょくだいさんもやってきてしばらく話していた。どうやら提出を監視されていたらしく、僕がCの部分点をダイクストラで解いたことに対し「ダイクストラって何!?」と言われむしろ「ダイクストラって何って何!?」という気分になった。説明するとあーと納得してもらえたけどどうやら普通に全探索すればいけるらしかった*10。1つ方針を思いつくとそこにハマりがちなので、簡単な方針を選ぶ能力を身に着けていきたい。ICPCに向けてという意味でも。

他にも母校である阪大の競プロerに声をかけてもらえたりして嬉しかった*11

厚切りジェイソン氏特別講演

本当に厚切りジェイソンだった*12。競プロやっててよかったと思った。

ディスコ会社紹介

Kiru Kezuru Migaku

社内ツアー

デュアルカットが生で見られて面白かった。ちょくだいさん曰く「このためのウェーハ」だったらしい。プールやジムなどの福利厚生施設もいろいろ見せてもらったけど、もう少し技術的な部分をいろいろ見たかった感がある。

表彰式・懇親会

表彰式では名だたるプロたちのご尊顔を拝むことができ大変光栄だった。懇親会では↓のツイートをしていたおかげかいろんな人に話かけてもらえてうれしかった。

他にも、E869120氏*13の協力によりLatteMalta氏を特定した。レアキャラのpekempey氏を特定したのも特定ポイント高い。

また食事が出て、ケーキがおいしかった。生ハムが人気だった。

まとめ

今回のコンテストで1つ驚いたのは、スタッフさんの多さです。撮影があったからというのも理由としてあるとは思いますが、これだけ多くの人に支えられてコンテストを開いてもらっているのだなあと思うと感謝の念を禁じえません。

コンテストを開いてくれる方々に感謝しつつ、もっといろんなオンサイトに出られるように精進していきたいですね。

DDCC、来年度も開催されるなら、いいイベントなので特に19卒のみなさんは予選に出てみるといいと思います。

*1:括弧が多くなりすぎたので

*2:語彙不足

*3:ディスカバリーチャンネルの人?

*4:300, 700(300), 700(300), 1000, 1500

*5:境界含む

*6:右端の方で余分にカウントしてしまう

*7:2回目

*8:僕はお会いしたことがなかったのだけれど、一緒にいたshora_kujira16がtorus711さんを知っていたので特定できた

*9:さて某件とはなんでしょう??

*10:空文字から初めて、構成中の文字列と直前に反転したかというフラグを引数に持つ再帰で書けるはず

*11:最近さらに盛り上がってるみたいでOBとして嬉しいです

*12:別に疑っていたわけではない

*13:今そらで869120って書けたんですけどすごくないですか??