2019-09-29
■ 第1回 最強コン 決勝
実家から2時間半電車に乗って新橋に行き、中高の部活の後輩にばったり会って会場まで連れて行ってもらう。
席がめちゃくちゃ狭くてびっくりした。隣がDEGwerさんだった。
コンテスト
A
和でペアを管理して、2つ以上見つかったら終わり -> 要素が被りませんか？ -> 数列がdistinctなので大丈夫 -> FA
B
やることはすぐ分かったが実装に時間がかかる
F
O(N^3)では確実にできて、高速化しないといけない -> 区間を伸ばすのはO(N)でできる、縮めるのも戻すDPでO(N)でできる -> Moだね
D
解法は先に出ていたので実装をするだけ、凸関数の極値を求めるのに傾き二分探索してバグりそうで怖かったけど大丈夫だった
C
ちょっと手を動かすと左右に分ける方法が一意に決まることがわかる -> multisetでゴリゴリ (番兵を入れておくと楽)
G
Eの地獄のような解法を思いついていたがやりたくなかったので考えたが、できなかった (想定解と同じ解法を考えてたが、根を消すと部分木たくさんに別れちゃって手に負えないな〜って棄却してしまっていた、なぜ？)
E
地獄のような解法を書く、SA+LCPライブラリがlog2乗で遅いので速いのを探すはめになったし実装もバグりまくるし涙が止まらない.....
G (再)
よく考えるとマージテクでできそうなことに気づくが、実装が全く間に合わない
結果
3位
コンテスト後
いつも以上に人と話せて楽しかった、渾身の懇親 (ふふっ....)
感想
コンテストもコンテスト以外もかなり満足度高めだった、でもいつかは雲上人バトルに割って入りたいね
オンサイト楽しいがちなのでもっと増えてほしいな〜〜〜
