Dまで四完。
コンテスト後のツイート
D (で+1、)で-1とした配列をAとすると、A[l]=A[r]が必須。また、l～rでA[l]*2を超えるものがあってはダメ。セグ木二分探索の後、二分探索。
— titia (@titia_til) May 30, 2024
E (q+1)*(q+2)*...がどの数字をどこへでも置けるときの答えで、そこからいくつか削る方針で考えていた。
E. Splittable Permutations
こたつがめさんの放送を見てAC。
クエリで与えられた数字が一意に並ぶことは分かっており、その間に余った数字を入れていくと考える部分もあっていたが、その条件が分かっていなかった。
ただ、並べる部分を再帰を使って書き、その書き方だと二乗になっていることに気付かずなぜTLE・MLEするか分からず随分悩んでしまった。
こういう実装はすらすらできるようにならないと。
F. Remove Bridges
こたつがめさんの放送や実装を見てAC。
解法は面白かったが、それだけだと実装が分からずこたつがめさんの実装を見る。すると、「各葉について、消された頂点までの距離」（この説明は意味不明だが……答えを得るのに必要な配列のことです）がdfs一発で求められていることに驚いた。言われてみれば分かるが、葉を中心に考えていたため思いつかなかった。
ただ、そのままだとPyPyの再帰がメモリを食うため通らず、非再帰に直してAC。木DPを使うと非再帰に直せた。
0 件のコメント:
コメントを投稿