Fまで六完。
G - Game on Tree 2
しばらく解説を見ても理解できなかったが、落ち着いて考えたら理解でき、AC。
コンテスト中は、中央値を求めるのだから答え二分探索だろう！ と、飛びついてしまったのがダメだった。この方針（x以上のものを1, それ以外を-1として木DP）だと「答えがA[i]以上になるか？」という判定はできるが、(A[i]+A[j])/2となる場合の処理が上手くいかない（と思う、多分。）
なので、考え方を変える。
木の葉それぞれについて、「そこにたどりついたときの中央値」が求まれば、後は木DPで答えを求められる。
で、実はこれはオイラーツアー（DFS順）みたいなことをしながらBIT上の二分探索をすることで求めることはできる。
この前、「オイラーツアー（DFS順）の利用は見逃していることが多い」と書いたのに、今回も見逃してしまった。反省です。
なお、$10^5$回くらいなら間に合うだろうとDFS部分を再帰で書いたら、PyPyだとTLEして、PythonでACできました。やっぱりPyPyの再帰は遅いなぁ。
H - Red and Blue Lamps
解説AC。
凸性を理解するため勉強しようと思って解説を見たのに、貪欲で解けるということでそれでACしてしまった。
（貪欲解は）難しいけどなるほど、という感じ。
0 件のコメント:
コメントを投稿