http://codeforces.com/contest/875/problem/Fprinceを点、princessの二人のprinceの候補を辺とみます。それからkruskalっぽいことをします。具体的には 1.違う連結成分どおしで、二つともlockedじゃなければ繋ぐ。 2.同じ連結成分どおしで、lockedじゃなけ…

https://szkopul.edu.pl/problemset/problem/6YiP6JA5U15hY94pLwuHoYPg/site/?key=statement実践的アルゴリズム貪欲編です。少し観察すると(列をstripする回数==M)または(行をstripする回数==N)が成立することがわかります。 対称なので(列をstripする回数==…

http://poj.org/problem?id=3045上からi-1番目まで決めているとする。i-1番目までの重さをWとすれば i番目とi+1番目のriskは W-S[i] W+A[i]-S[i+1](Aは重さ)となる。ここでi番目とi+1番目のcowを入れ替えてみるW-S[i+1] W+A[i+1]-S[i]となる。 W-S[i] W+A[i]…

http://agc016.contest.atcoder.jp/tasks/agc016_b 最初1CaseだけWAだったからこれはいけると思ったけどそうでもなかった。A[i]の最大値と最小値(それぞれrv,lvとする)の差が1か0で場合分けする 1. 0のとき rv = N - 1なら全色違うものを置けばOK rv * 2 2. …