チーム練習 (04/29)

2020 Petrozavodsk Winter Camp, Jagiellonian U Contest をやった。本番51位相当、参加者のレベル帯めっちゃ高くないか

(開始) 手分けして読む。L,Bが解かれているので考える。
(0:22) Lは貪欲でいいことがわかるのでolpheが書きはじめる。
(0:25) Lが通る。
(0:39) Bは高速ゼータ変換でいいことにdivくんが気づいて書く。
(0:59) Iが貪欲にできる限り大きいものから取っていいことにolpheが気づいて書き始める。
(1:37) Gについて色々考えた結果、マッチング全探索して2点間を直接線分で結ぶと一つは解が存在するに反例が見つからなかったので書くことになった。
(1:55) Gを出すとn<=6なのにMLE(？？？) 未定義を踏んでないか確認したけどなさそう。なんかやばそうなバグらせかたをしていそうなので実装をolpheにかわる。二人がHの考察を詰めてて、実装できる段階になった。
(2:29) Gが通る。divくんがHの実装をはじめる。Eを考えるけどつらそうなのでFを考える。隣接swapとreverseだけで揃える場合は転倒数で計算できそうなので、シャッフルをする場合の期待値を求めたい。頑張ればできそうな気もするけど遷移がよくわからない。
(3:09) Hが通る。Jを考える。
(3:37) Jは状態をうまくもってUFでつないで管理するとできるっぽいのでolpheが実装を始める。EJあたりを考えたけど通らなくて終了。

解説を読むとEが誤読だったことが判明 マジでごめん
Jは連結にするべきパターンが少し抜けてたらしい
cin高速化を複数回実行していたのを1回になるようにしたらGのMLEが取れた。標準入出力のあとにcin高速化のいつもの関数を呼ぶのは処理系定義らしく、気をつけた方がよさそう。
Gはもうちょっと早く実装に入ってもよかったかなあ

A 2020 Petrozavodsk Winter Camp, Jagiellonian U Contest A問題 Bags of Candies - ferinの競プロ帳
E 2020 Petrozavodsk Winter Camp, Jagiellonian U Contest E問題 Contamination - ferinの競プロ帳
F 2020 Petrozavodsk Winter Camp, Jagiellonian U Contest F問題 The Halfwitters - ferinの競プロ帳
J 2020 Petrozavodsk Winter Camp, Jagiellonian U Contest J問題 Space Gophers - ferinの競プロ帳

C 解説のの条件を消せると書いてある部分がよくわからない