ABC283F 平面走査の問題で，実装ではsegtreeを使う． まず，絶対値を外して考えるために，4つに場合分けする． 実装では，reverse をしたりすればある程度使いまわせるので，4つ書く必要はない． Case: \(i > j \) かつ \(P_{i} > P_{j}\)これは，よくある平…

ABC268F もし置換に関してDPをするなら， どれを選んだかという集合を持ちながら遷移するので， \(O(2^{N})\) がかかって無理． そこで，最適戦略を考える方針にする． いきなりは難しいので，簡単に考えるとすれば， 数字を1だけで考える 置換は互換のみ，…

ABC267F 木の直径に関する問題． 木の最長パスの一つを直径といい，これはDFSを2回することで求まる． まず任意の点 \(v\) からDFSをして，一番遠かった点を \(a\) とする． 次に \(a\) からDFSをして，一番遠かった点を \(b\) とする． \(a,b\) のパスが直…