hogecoder

tsutaj 競技プログラミングの記録

DDCC2017 本戦 参加記

大会参加記

DISCO presents ディスカバリーチャンネル コードコンテスト2017 本戦 に参加しました。去年の DDCC に引き続き、 2 回目の参加となります。

予選

予選は全完 122 位でした。D 問題が解けたのは嬉しかったのですが、結構条件漏れが多くてサブミットデバッグ気味になってしまい、ペナルティ無しの恩恵を受けまくって本戦進出できた感じですね・・・。

今回は就活枠 (19 卒枠) の対象外ゆえ交通費や宿泊費が自己負担なので正直行くかどうか迷っていたところもありましたが、TL の人々に会いたかったですし、なにより去年のあの雰囲気がとても好きだったのでそれをもう一度味わいたいなあと思い本戦に参加することにしました。

本戦の前

去年の反省を活かして受付 30 分前くらいに会場入り。たぶん一番乗りでした。

ロビーで出会った方々とおしゃべりしつつ、謎パネルを撮りつつ、受付開始を待っていました。

受付後、コンテスト本番が始まるまで時間があったので、なけなしのコミュ力を発揮して人々に会いに行きました。人生で初めてサインを求められてびっくりした (おかゆさん、olphe さんありがとうございました！)

そんなこんなでコンテスト本番の時間が近づく。去年ほどは緊張しなかったとはいえ、やっぱり緊張しますね・・・。

コンテスト本番

本戦は 2 完 77 位でした。去年の本戦は底辺みたいな順位だったので、それに比べたらだいぶ成長しました。が、C 解けなかったのは悔しいですね・・・

A 問題

なんかデジャヴを感じる。去年の自分のソースコード引っ張りだそうかなと思ったけど解読に時間がかかりそうなのでやめた (それはそう)

円の半径を R とします。各正方形について 4 つの頂点の座標を列挙し、この 4 点すべてについて円の中心との距離が R 以下なら、その正方形は切り出せます。正直コレだけなんですが、距離を計算するときに x*x + y+y みたいな typo をしたり、配列が作れなかったり (は？) してグダグダでした。大反省ものです。

AC (17:04)

B 問題

正直この問題が最も簡単でした。

自分の解法としてはこんな感じです。早い段階でサンプルから察せたのが良かったのかなと思います。ただ X を作る際に gcd の結果を素因数分解する必要があるんじゃないか、みたいに一瞬逸れかけたので危なかったです。反省。

AC (23:47)

C 問題

解けませんでした (悲しいね)。以下嘘考察です。

距離の総和が 0 でないサイクルを列挙して、そのサイクルすべてについて

  • 共通の辺が少なくとも 1 つ存在する (それがないと一部のサイクルについて総和を操作できないので)
  • 各サイクルの距離の総和が同じ (距離を変えられるのは 1 辺だけなので)

が成り立てば嬉しいよなあと思いましたが、そもそもサイクルの列挙があやしいし共通の辺を探すのも難しい。どうすればいいのかなあという感じでした。

上の条件をクリアする策はあまり出てこなくて、なんか 1 辺だけ取り除いた時にトポロジカルソートできたらいいのでは？みたいな謎の考察を苦し紛れに思いついて、他にやることもないのでそれを実装していたのですが、結局嘘だったようです。完全に思いつきだったので仕方ないです。悔しいので解き直します。

D 問題

1100 点問題だしやばみなんだけど一応読みました。でもこれに時間をかけるのは実力的に間違っている気がしたのであまり考察しませんでした。

解説を読んだ感じだと、割と思いつきやすい DP を枝刈りしたみたいな感じだったので意外でした。あとで解いてみようと思います。

DDCC 特別ビュッフェ

えび

結構いろんな人とおしゃべりしました。らてあさんが tourist じゃんけんの人として認識されているのが面白かったです。

特別対談

将棋は全く詳しくないのでどの程度まで話についていけるのかなあと対談前は不安に思っていたのですが、全然そんな心配する必要なかったです。めちゃくちゃ楽しかったです。

コンピューター将棋 vs. 日本将棋界の変遷の概要やプロ棋士の戦術・学習法の変化、さらにはコンピューター将棋の意義まで、興味深い話題がたくさんありました。

これから頑張らなきゃなあと思えた話としては、「競技プログラミング意外の技能も身につけたほうがいいよ」という話。競技プログラミングが狭く深い世界であることは自分も理解していますし、おそらくそういう認識を持っている競プロ er が他にも多くいるような気がします。これから自分がどう成長していけるのか、どのフィールドで輝けるのか、考えていきたいですね。

あとはこんな話題も。

コンピューターの成長は指数的で、人間の予想をはるかに上回るという話。自分は 5 年後くらいにはコンピューターに競プロ負けてるかも。そうなったら悲しいのでがんばります。

社内ツアー

去年に社内ツアーに行ったので、2 回目以降の人向けのツアーに参加しました。

社用車が電気自動車だったり、オフィスの風通しが良かったり、やっぱりすごい会社ですね・・・

毎度おなじみウェーハカットもばっちり見れました。やったね。

懇親会

懇親会もいろんな人と話しました！

RUPC 以来に会った方が結構いました。半年前に比べて強くなった方ばかりなので、自分も成長しないとなあと思います。

ちょくだいさんが最速最強アルゴリズマー養成講座にサインしてくださいました！うれしい！ありがとうございました！！

まとめ

オンサイト最高！！！！！

来月初めの CODE THANKS FESTIVAL でまたお会いしましょう！！！