チームbroken_keyboardで参加して、ABCDFを解いて19位でした。 順位表
チーム構成
コンテスト中の出来事
- 作戦通り、私が最初にAを読む。これのCに似たよく分からない操作をすれば最小になるということはすぐに気づいたけど、なぜかバグらせまくっていて、20分くらいかかる
- 作戦通り、Bを後輩に任せる。構文解析らしい。夏休みに四則演算くらいは解けるようになった、と言っていたので、任せるつもりだったけど、無限ループバグを出してパニックになっていたので私が奪い取って書き直して60分くらいでAC
- 先輩とCを考える。どういう動きをすればサンプルの答えになるのか調べるのに結構時間がかかった。先輩に「intersectしている区間をまとめて、行ったり来たりすれば良いっぽい」ということを教えてもらって、しゃくとりっぽいものを実装するとWA。反例を考えると、完全にオーバーラップしているような制約条件 (ex. 5→2と4→3) があるときにおかしくなることがわかったので、それを直すとAC (時間不明)
- FのAC数が多いので考えてみる。なんか橋っぽいものが必要になりそうだけど、さすがにこれだけのチームが橋・関節点ライブラリを作っているとは思えなかったので、もうちょっと考察してみる。後輩が「MSTを構成する辺の数は|V|-1なので、|E|log|E|を|V|回繰り返してOK」ということを思いついたので、実装するとあっさりとAC
- DとEとGという選択肢があったけど、AC数と問題文の精査が終わっていたという理由でDに挑戦。二分探索でも解けそうだったけど、必要無さそうなので、ラグランジュの未定乗数法などを持ちだして解けないか検討して無駄な時間を過ごす。結局無理そうだったので角度で二分探索した。
- EとGの選択肢があって、残り30分しか時間が無かったので問題文がシンプルなGを考えてみる。'('を+1、')'を-1としたときの累積和的な配列を作ってセグメントツリー的な何かを使えば良いことが分かったけど①範囲に足し合わせるクエリ②最小値を求めるクエリ、の２つが必要になることが分かり、界隈で名前が付いているセグメントツリー*1の名前が出てきて絶望。
印象的な出来事
- 去年に比べると、かなりチーム戦していた
- @kagamizや@RKX1209とTwitterで知り合ってN年越しに初エンカウントした
- エクスカーションではIBMとPFIとドワンゴに行った。IBMは売上の中心がハードウェアからBtoBのサービスにシフトしていて、最近はセキュリティに力を入れているらしい。PFIでは「jubaclusteringのパラメータの数どうにかなりませんか」という質問をしたら、納得できる答えを頂けて良かった。ドワンゴは天井からぶらさがっているメイド服と、作業スペースの半分を覆い隠しているフィギュアタワーにびっくりしたけど、事務的な処理をする部署は至って真面目な普通の会社だった。
*1:Starry Sky Tree
