TTPC2019 参加記 - 思考の墓場

おきもち(idsigma)です。2019/8/31に行われたTTPC2019に参加しました。

昼食

　わくさんとplatyplusさんとご飯に行くことに。何を食べようかなあと思っていたら...

大崎に非常に気になる店名のラーメン屋を見つけてしまった...
らーめん食堂あの小宮 https://t.co/IGVYnDLc3I
— 住建 (@smiken_61) August 31, 2019

行くしかないので行ってきた。(なんとことかわからない人はhttps://onlinejudge.u-aizu.ac.jp/challenges/sources/JAG/Prelim/2946を見てください)

さあ，TTPCに向かって移動開始だ！とあなたは意気込んでいるところかもしれないが，ちょっと待ってほしい．一つだけ先に忠告しておくことがある．それはこの大崎に潜む謎のラーメン屋，煮干醤油ラーメンのプロ・あの小宮の存在だ． pic.twitter.com/XsH49DKVcS
— おきもち (@IKyopro) August 31, 2019

TTPCに向って移動開始だ！と意気込んでいるところかもしれないが、少し待ってほしい。それはO崎駅周辺に潜む謎のラーメン屋、「らーめん食堂あの小宮」の存在である。 pic.twitter.com/hf6687FxsO
— platypus (@platypus999) August 31, 2019

あの小宮さんを食べました pic.twitter.com/sneKwG6O1m
— 🎀🐑わく🍆🎀 (@wakuwinmail_C) August 31, 2019

煮干しの味がしっかり聞いたラーメンでした。煮干し独特の臭み(？)も感じたので僕は好きですが個人差があるかも。
雑談していたらすぬけさんがやってきた。小宮好きすぎでは？(ブーメラン)

あの小宮にすぬけさんが来た、僕は信じていた
— おきもち (@IKyopro) August 31, 2019

さあ，優勝に向かって全完開始だ！とあなたは意気込んでいるところかもしれないが，ちょっと待ってほしい．一つだけ先に忠告しておくことがある．それはこの大崎に潜む謎のラーメン屋，あのプロ・あの小宮の存在だ． #ttpc2019 pic.twitter.com/f53l32XNQh
— ꑄ꒖ꐇꌅꏂ🐈 (@snuke_) August 31, 2019

あのプロってなに？

結局どの小宮なんだよ
— 住建 (@smiken_61) August 31, 2019

topcoderとかICPCの話をしながら会場へ。

コンテスト前

　ふっぴーくん(https://atcoder.jp/users/fuppy0716)とけんしんくん(https://atcoder.jp/users/knshnb)と組むことが決まっていた。チーム名が決まっていなかったが、fuppyくんが細いのとgirigiriを混ぜてgarigariになった。僕も少し前まで細かったはずなのだが、気づいたら腕が太くなっていて厳しい気持ちになった。
　近くにunkort0nとかいうチームがいたのでなんて読むのか聞いてみた。アンコルトンらしい。
　あとはomochana,risujiroh,Joeとかいうチームができていた。ヤバいな？

コンテスト

A

　ふっぴーが爆速で通していた。オンサイトFAだったらしい。すごい。

C

　Bがなんか調べものをしていたので僕がCを書き始める。自信満々で出したがWA。よく読んだら $a_i \leq X$ を無視していた(ひどい)。

B

　後で知ったのだが正規表現が書けるとすぐらしい。結局けんしんがC++で書いてAC。

再度C

　欲しい値が $X$ より大きかったときを入れて無事AC。

D

　ふっぴーに考察を聞いてくれと言われたので双子素数は？とか言いながら相槌を打っていたら自己解決していた。面白い問題に思えた。1WAだったらしいけど無事AC。

E

　僕とけんしんがいろいろ言いながら書いてあったが結局ふっぴーが可能な条件と構築思いついてAC。ここら辺は地力の差なのかなあ...。

F

　ふっぴーが先に見ていたのだが、すぐには思いつかなかったらしい。事前にこの制約で最小費用流っていける？と言われていけないと言ったのだが、読むと流量が2だったので $O(FE\log{V})$ で間に合うやんけと言い書き始める、が辺を張ろうと思ったらできないことに気付いてこれは嘘ですと言う。いろいろ言われるけどそういうのはできないと説明して振り出しに。一度僕とふっぴーが後ろを読むことにしたのだが、ほどなくしてけんしんが解法を思いつき、合ってそうなので実装してもらう。AC。これすごい。

　その後は一度ジャンルを確認して、ふっぴーがMの考察を開始。けんしんがHをやり始めいろいろデータ構造が必要らしくググっていた。僕がJを見てdpを組もうとするが破滅。諦めてOとかを見ている間にMができたらしく実装を始める、が全然合わないらしいのでGを書き始める。

G

　サンプルが合わないと言われたので解法を聞く。細かいところは正直わからなかったが(おい)やっていることは間違ってなさそうだったので謎だという気持ちになる。てきとうにサンプルを試しながら結局実装ミスだとわかりAC。

O

　解かれているので僕とふっぴーで考え始める。ふっぴーが[tex:2ⁿ]の形を思いつくがそれらの配置の組合せが思いつかず、ふっぴーがMに戻り、僕がOを考えることに。苦悶してしまったが結局以下のような構築を思いつきAC。ここまで何もしていなかったのでよかったー。

Oこんな感じ #ttpc2019 pic.twitter.com/Y9pppWBJGO
— おきもち (@IKyopro) August 31, 2019

$2\times 2$ のブロックが2通りのパスをもち、 $2\times 3$ のブロックが4通りのパスをもつことを利用して2冪を作っていく。[tex:2¹]と[tex:2⁰]を別に作ると足りないので一緒にやる。
　僕が勘違いしてふっぴーの考察を全く使わずにACしてしまった、ごめんね。
　ちなみにこの構築かなり変態だと思う。なんで思いつくんだ？(褒めています)

O，相当面倒なことをしてたっぽいなhttps://t.co/FbtyT9cJA5 pic.twitter.com/YUHBhMGsEe
— iroh (@risujiroh) August 31, 2019

M

　Gの前の話だが、ふっぴーが「この部分問題解ける？」と言うとけんしんが解けると言ったので2人で書くことになっていた。コードの共有はCE提出で行った(天才か？)。いろいろあった後ふっぴーが勘違いに気付いてサンプルが合って出すもTLE。その後2人がいろいろ案を出しつつHLD分解を使うことになったのだが、結局合わなくて終了。(結局原因わかったのかな？)

けんしんはHと心中してしまった。個人的には実力相応のパフォーマンスだったかなあ。組んでくれた2人はありがとう。

懇親会

いろいろあった(全部書くのは大変、ゆるして)

初めて会う人複数名にカツサンドくんと言われる

#ttpc2019 pic.twitter.com/m3lyeTo6bI
— おきもち (@IKyopro) August 31, 2019

シナモロールに早く黄色になってと言われる(わかるなあ)。
すぬけさんが寝ていたので何してるんですか？と聞いたら寝てると言われる。
言語アップデートがもうすぐかもしれないらしい。Goの古いバージョンはソートをするのにもいろいろ定義しないといけないらくし大変という話を聞いた。
そすうささんとえびちゃんがやってきて話す。ACPCのセット準備頑張ってほしい。

これ忘れてた #ttpc2019 pic.twitter.com/5d94a9ABJK
— おきもち (@IKyopro) August 31, 2019

ずっと名札の正しい下げ方がわからなかったのだがここで教えてもらう。すぬけさんに「青だからわからないよね...」と煽られ「銀に煽られた」と言ったら「僕も青だよ」と言われる(紺では？)。
Japan Regional Design部門の話を聞いて爆笑した。

懇親会後

スタバで大根(chokudai contest 004)に出る。激冷えした。

東工大の皆さん、Future様、参加者の皆さま、ありがとうございました。