問題概要 1~N(N 解法 max-heapに区間を突っ込んでいけば良い。ただし、heap内の区間を削除したりすることがある。pairing heapなどのheapを使ってもよいが、ポインタを利用して直接中身をいじることでも対応できる。

問題概要 頂点数V( 解法 適当に根を決め打ちしてDFSなどで各部分有向木について向きが逆になっている辺の個数などを求めておく。 この情報があると、各頂点について根に選んだとき入れ替えなければならない辺の本数を求めることができる。 図の青で囲んだ部…

問題概要 AからK文字のアルファベットを使用した長さN( 解法 多分貪欲でも行けるはず。何だけどコンテスト中はDPに走った。dp[i][j]={i-1文字目がjであるときのそれまでの最適値}とすればよい。なぜか愚直なDPの計算量O(N*K)だと勘違いして、書いてる途中でO…

結果。 C,Dを解くのに時間がかかってしまったのと、Eで賢い実装方法を思いつかなかったのがよくない。最初に良くない実装方法を思いついてしまったときの修正能力が低いというのは前から気づいている問題点なんだけど、一度解ける解法が見えてしまうと中々そ…