問題文 http://codeforces.com/contest/570/problem/E 解法 前と後ろの状態を同時に持たないことにはどうしようもなさそうだが、愚直に持つとオーダーが悪い。 よく考えると、現状態から i ステップ後の位置は、列か行の位置のどちらか一方を持てばもう一方…

問題文 http://codeforces.com/contest/570/problem/D 解法 部分木の特定の高さのノードだけ取り出すのもオイラーツアーでできる。 この場合は高さごとにノードを管理すればよい。 各ノードが持つ区間は普通のオイラーツアーと同じで、各高さごとに持つデー…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1383 解法 始点および終点からの最短路を求めておく。それぞれ from_s, from_t とする。次に s-t 最短路グラフを作る。このとき、グラフには s から t へ行くのに必要になるかもしれない辺…

問題文 http://codeforces.com/contest/555/problem/E 解法 二重辺連結成分分解をしてくださいと書いてあるので、先にやっておく。 ただし、与えられるグラフは単純グラフとは限らないので、多重辺にも対応しておく。 するとグラフは森になるので、結局木の…