解けなかった問題を覚書程度に記す。
ABC144E
解けたけどめっちゃ時間かかった。
を昇順,を降順でソートすればいいのは直感的。あとはスコアを2分探索すればいい。
2分探索について,lhsとrhsの更新とか細かいところでちょっと詰まった。気を付けないといけない(より一般的なライブラリを作ればいいのかもしれないけれど,まあ注意すればいいだけの話かなあ)。
ABC144F
難しい...けれど解説を見れば超簡単。これは頑張って考察したかったなあ。
ルートを消さないときの期待値は大きい部屋から逆にdpすればいい。ルートを消すとき,期待値が最小になるように消すのだから,頂点iから出るルートのなかで一番コストのかかるものを除けばいい。あとはそれを1~N-1について確かめる。。