ふーらくたるの雑の記

雑な事を記していくなど

CODE THANKS FESTIVAL2017参加記

参加記 CODE THANKS FESTIVAL2017

12月2日(土)に開催されたCODE THANKS FESTIVAL2017に参加してきました。頑張って思い出しながら書いていくのでよろしくお願いします。

前日

TIkeさん主催のボドゲ会参加者の皆さんと合流するため品川までいきました。品川の港南口でTIkeさん、つたじろうさん、こうきさん、竹雄さん、らてあさん、フェリンさんに挨拶したあと、お腹空きましたねということでロイヤルホストの方へ。席が空くまでの待ち時間では、らてあさんにゼロ距離ふぁぼ爆を食らったり、2人でTreeoneさんに並列ふぁぼ爆をしたり、ついでにこたつがめさんにふぁぼ爆をしたりして時間を潰していました(ごめんなさい><)。注文したのはオムライスでしたが、注文する際、僕の声が小さすぎて店員さんに何回か聞き返されてWAを食らってました(今思えばこれはフラグだったのかも…)。オムライスはすごい美味しかったです。

食べ終わった後は解散して家に帰りました。普段は生活リズム崩壊勢なのですが、前日ということで早めに就寝。

当日

参加するまでフェーズ

早く寝たかいあって無事起床することができました。

ここで一つ罠にはまってしまったのですが、早く起きすぎたために余裕かましてTwitterをやってたら時間ギリギリになったので焦って家を出ることになります。

道中同じくTLEしそうなShinya Katoさんの焦っている様子を見てニヤニヤしていました。

そしてここでもう一つ罠があって、Twitterをやりすぎてしまったが故にスマホの充電が切れてしまいました。それだけなら別に大したことはないのですが、さんくすの会場をメモしてなかったので(は?)、駅に着いたのに会場がどこだかわからないという事態に陥ります。会場名のSuffixが「MONO」ということは記憶していたので、駅員さんに「この近くになんとかMONOっていう施設ありませんか!?」って聞いたら「は?」って言われて終わりました。悲しいね。

うろちょろしててもしょうがないので、とりあえずオタクっぽい人の流れに着いて行こうとしたりしていましたが(最悪)、目がついていないので見失って失敗しました。途方に暮れてましたが、突然自分がPCを持って来ているということに気づきます。近くにWi-fiスポットがあったので、無事会場の情報を得ることができました。この時点ですでにギリギリ。急いで会場に向かったらまだ開会式は始まっていなかったらしく、なんとか間に合うことができました。やったぜ。

ちなみにKatoさんは遅刻してたみたいで笑いました。

会場入りフェーズ

無事到着したので、会場でTシャツを貰いました!去年のこどふぇすは当日風邪で休んでしまったため、1年ごしのゲットとなり非常に感慨深かったです。早速着ようとしましたが、セーターの上からだときつくて入らなかったのでそのまま放置してました(それはそう)。そのままお弁当と僕の大好物のカントリーマアムを回収してコンテストに備えます。


コンテストフェーズ

code-thanks-festival-2017.contest.atcoder.jp
12:00から3:00までの3時間コンテストでした。

A問題
問題文を読んでソートするだけだと気づいたので実装して提出しました。12:02AC。

B問題
制約が小さいことを確認して、C++で文字列扱うの面倒臭いなあって思いながら全探索して通しました。12:06AC。

C問題
見た瞬間優先度付きキューを用いた貪欲法で解けると思ったので頑張って実装しました。12:12AC。

D問題
問題文を読んでmin { kn mod m | k ∈ N}を求めればいいことに気づきます。5分ぐらい考えて全く解法を思いつかなかったので、「300点だし、適当にkn mod mの重複が出るまでkを探索してやれば解けるだろ!w」と甘い考えのもと実装して提出します。当然のごとくTLE。ここで問題文をもう一度じっと睨んで見ると急に頭の中にgcdという単語が浮かんで来ます。頭の中で証明もどきをして、サンプルもあうことを確認したので実装してみます。しかしgcdをしばらく書いていなかったので、2分ぐらいバグらせます。何が間違っているかわからなかったのでネットで"gcd 再帰"って検索しました(ひどい…)。提出して見たら無事通りました!12:38AC。ここら辺ではじめて順位表を見ますが、意外と自分が悪くない順位にいることに気づきます。

E問題(1回目)
10分ぐらい偶奇を用いた考察をしていましたが、全く解ける気配がないのでパス。400点むずかしい。

F問題
太字で書かれたいかにも怪しげな制約から、DPをしても状態数がそんなに多くならないと思います。ペナルティもなしだし、とりあえず出してみるかと、mapに状態を突っ込んで行く素直なdpを書いたら通ってしまって「えぇ…」ってなってました(コンテスト後にTLの方のツイートで気づきましたが、これ嘘解法ですね…)。12:51AC。

G問題
制約を見て半分全列挙ができそうということに気づきます。前半分と後ろ半分でvalidな集合かどうかを判定するのは、bitを使えばできそう。問題はマージするところだけど、これもあらかじめbit DPで前計算しておけばO(1)でマージすることができそう、と思い頑張って実装します。サンプルがあったので祈る気持ちで提出。AC。この時点でパーカー獲得が決定してガッツポーズします。ここで順位表を見たら2位に僕の名前があって、おいおいおいってなってました。13:26AC。

H問題(1回目)
問題文からUnion-findを使いそうだとぼんやり感じます。逆操作を考えて見たりしましたが、うまい方法が思いつかなかったのでとりあえず平方分割+Union-findのシミュレーションを実装して投げて見たらTLE。自分には手に負えなさそうということでE問題に再チャレンジします。

E問題(2回目)
問題文をじっと睨んでたら「50/10って5だなー」と頭に浮かんで来ます。5種類の袋から取り出すコインの枚数をバラバラに決めて、各コインの重さを未知数とする方程式を解けばなんかコインの種類を特定できそう?=>実装してみるか=>AC! ここら辺からもしかして賞金狙えるんでは?なんてことを思い始めます。14:27AC。

H問題(2回目)
永続Union-findがあれば二分探索で解けるなーと気づきます。頑張って永続Union-findを検索しますが、全然検索に引っかからなかったのでモニターに向かって中指を立ててました(隣に座っていた方、いきなり隣の奴が中指を立てたことで驚かせてしまったのなら申し訳ありません)。それでも諦めずに検索してるとD言語を用いて実装されていた方のブログ記事が出て来ます(URLは後で貼ります)。D言語の言語仕様をぐぐりながら少しだけ直します。=>AC ABCとyukicoderを除けば人生初の全完だったので、思いっきりガッツポーズしてました。この時点で残り3分程度。14:56

表彰式、懇親会フェーズ

コンテストが終わった後、TLの人々と話しました(記憶力が鶏並なので時系列がごちゃごちゃになってるかもしれません…すみません…)。 ボドゲ会の人々や、去年のJAG夏合宿で同部屋だったoyasさん、全然残り一問を解き終わらない自宅番兵さんとお話しすることができました。こうきさんにはクソみたいな解法の説明をしてしまい、反省しております…。

一通り皆さんと話した後、表彰式がありました。なんとコンテスト前は考えもできなかった5位に入賞することができました。5000円です。やったぜ。


ただ、どうやら僕のid(fooractal)は可読性が著しく低いらしく、司会の方に何度か読み方をSubmitされましたが、全部WAでした。で、表彰されるということは何かしらの感想をみなさんの前で言わなければなりません。僕はこの手の人前に出て何かを喋るということが世界一苦手なのですが、勇気を出して必死に考えた内容を話そうとしました。しかし、僕が話し始めた瞬間、僕の周囲が突如真空状態になり、発した声が皆様の元に届くことが物理的に不可能になってしまいました。聞けば感動間違いなしの名スピーチであったと確信しておりますが、皆様の元にお届けすることができなくて非常に残念でした。ちなみに僕が話し終わったあとは真空じゃなくなりました。

現場にいたKatoさんの声


そのあとはchokudaiさんの解説を聞いた後、コネクションハントをやったり、ご飯を食べたりしながらTLの皆さんと交流していました。この時去年からずっと会いたかったゼオスさんや、Treeoneさんともお話しすることができました。あとご飯は寿司とかピザとかでてきていっぱい食べました。美味しかったです(小並感)。皆さんと喋ったあとは席に座って、後ろの席の竹雄さんとずっと喋っていました。帰り際に前の席のrunomさんともお話しできて、大満足のオンサイトでした。

感想

本当に、最高に楽しかったです。競プロをやる上での夢の一つだった「賞金をとる」という夢まで叶ってしまい、本当に言葉がありません。5位という結果は完全にまぐれなので、頑張って精進して、今度は実力で賞金を得られるように修行していきたいです。

最後に、話してくださった方々、そしてCODE THANKS FESTIVALを開いてくださった方々、本当にありがとうございました!!!!