問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2893 解法 橋を全列挙し、それぞれについて削除したときの cost を求め、ソートすれば良い。具体的な実装としては、 橋を列挙する。 橋を含まない連結な部分グラフを潰して 1 つの頂点とし、…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2891 解法 N 頂点 N 辺のグラフ（いわゆる「なもりグラフ」）は1つだけ閉路があり、その閉路に木がいくつか連結している形になる。各クエリの頂点の両方とも閉路に含まれている場合2本切断す…

問題 beta.atcoder.jp 解法 が全て より小さくなるような x、すなわち、 となるような x の最大値を求めたい。 で x は a より大きいとすると、 を満たす x を求めれば良い。 コード /// Thank you tanakh!!! /// https://qiita.com/tanakh/items/0ba42c7ca3…

問題 beta.atcoder.jp 解法 を足したり引いたりしてを作る。 を足したり引いたりして 1 を作る。 にすることを目指すのではなく にすることを目指す。 であることは である。 なので、各 p について独立に考えればよいということになる。 コード /// Thank y…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2900 解法 と並んでいるのを としたいが、これが成り立っていないとする。 が成り立っている時、 となっているので、 を動かすことは得にならない。よって 以降について問題を解けば良い。が…

問題 C - Median Sum 解法 解説の通り。空でない部分列の数は 個存在するが、部分列の和が x となるような部分列の構成方法の数え上げは動的計画法で で求まる。だが、これでは間に合わない。中央値は配列の合計の 1/2 以上になるということに気づくと、部分…

問題 https://beta.atcoder.jp/contests/yahoo-procon2018-final/tasks/yahoo_procon2018_final_a 解法 ある整数 i について配列内の i と互いに素な整数の数を数えるのは大変そうなので、i と互いに素でない数を数えることにする。i を素因数分解し、例えば…

問題 https://beta.atcoder.jp/contests/abc107/tasks/arc101_b 解法 完全に解法の通り。 全ての連続部分列のうち、中央値が x 以上であるものがいくつあるかを考える問題になる。 数列の中央値が x 以上である。 => 数列の各要素を x 以上なら 1 そうでなけ…