こんちゅう

エッセイ・小説・ブログ・楽譜置き場。 不定期更新。

AtCoder ABC 144

解けなかった問題を覚書程度に記す。

ABC144E

atcoder.jp

解けたけどめっちゃ時間かかった。
A_iを昇順,F_iを降順でソートすればいいのは直感的。あとはスコアを2分探索すればいい。
2分探索について,lhsとrhsの更新とか細かいところでちょっと詰まった。気を付けないといけない(より一般的なライブラリを作ればいいのかもしれないけれど,まあ注意すればいいだけの話かなあ)。

ABC144F

atcoder.jp

難しい...けれど解説を見れば超簡単。これは頑張って考察したかったなあ。
ルートを消さないときの期待値は大きい部屋から逆にdpすればいい。ルートを消すとき,期待値が最小になるように消すのだから,頂点iから出るルートのなかで一番コストのかかるものを除けばいい。あとはそれを1~N-1について確かめる。O(NM)