Codeforces Round 922 (Div. 2)

　Dまで四完でさらにレートを落とす。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round 922 (Div. 2) 頑張って書いたEがTLEして悲しい。
A m=1なら-1
B 片方をソートした（未証明）
C a>bにするかa<bにするかを決めて貪欲
D 二分探索して判定問題をセグ木DP
E 最初にA[1]を決め、後は半分ずつに分けていく。クエリ数が分かってないけど余裕ありそう、と予想した。

— titia (@titia_til) January 30, 2024

E. ace5 and Task Order

　コンテスト中提出したコードをPython3で出したらあっさり通った。

　PyPyのprint(flush=True)が遅いというのを忘れていたのが敗因。こどふぉでは、「PyPy3でTLEしたらPyPy2やPython3でも試してみる」というのも重要ですね。PyPy3-64ができてから、PyPy3-64とPyPy3しか試さなくなっていた気がする。

F. Caterpillar on a Tree

　解説AC。

　解法ツイートで貪欲でいい、というのを見てもどう貪欲すれば良いか分からなかった。

　全ての葉を通れば良いので、葉の順番を考えれば良いというのは分かったが、その上で、

・子の中からmax深さが低い順にたどって、葉をつないでいくのが最適

　と気付くと、そのうちどこかの葉で親まで戻ったとき、何歩省略できるかが分かる。

　あとはソートしてやっていけばOK。

　E捨ててFいっていれば良かったかな、とコンテスト直後は思っていたけど、これだと無理だったかな……。