2018-2019 ACM-ICPC, Asia Dhaka Regional Contest

問題リンク

jupiro snow39 kotamanegiで久しぶりのチーム連をした。

バチャの流れ

  • kotamanegiが後ろから、snow君が前から、jupiroが真ん中から読むという定番？とかした流れで読む

  • kotamanegiがJ解けたというので実装してもらう→ J AC(00:04)

  • snow君がC解けそうだがお昼ご飯で抜ける。

  • kotamanegiがCを解く→ C AC(00:48)

  • Fがどう見てもbitsetを使うと3secもあるので愚直が通ると確信する。

  • LCAの写経を始める(これ結構苦痛だった)

  • サンプルあったのでだす→WA

  • n \leq 10000とかなのに1<<nとか書いてた(は？？)

  • 書き直す→WA

  • ここでPCの充電が切れていったん別のカフェに移動する(がWAの原因が分からな過ぎた)

  • なんかWAが増えているのでみるとどうも出力しないといけないのをそもそも出力してなかった(は？？)

  • 歩きながらバグの原因を考えてる間にkotamanegiがBを通す→B AC(01:41)

  • snow君がHL分解でFが解けるというがどうみても自分の解法も正しいので、実装権を渡しながら永遠とにらめっこする。

f:id:jupiro:20200228183506p:plain

  • どうみてもaとbがlcと同じ時にバグるだろ…→直す→ F AC(01:57)

  • kotamanegiがH解けた→H AC(02:33)

反省点

出力形式はちゃんと見よう！！

bitsetはもう少しなれないといけない(不慣れで時間かかった)

kotamanegiに頼りすぎなので、地力をあげる

おまけ(F解説)

根からnode iに渡るのにたどるnodeの集合をS _ {i}とすると、u, vを渡るのにたどるnodeの集合Tは


T = ((S_{u} \cup S_{v}) \ xor \ S_{lca(u, v)})\cup \{lca(u,v)\}

である。あとは集合をbitsetで管理して順にみていけば、3secにはかなり余裕をもって通る。