部活休んだので個人的に復習その１
リンク
部活の方
not-522.appspot.com
個人練
not-522.appspot.com
Friction
W = 2ならコスト前計算とDPでO(H^2) で解ける
実は、全ての隣接するペアについてコストを求めて総和を取ると答えになる
下界なのは明らかなので達成可能であることを示せばよい
次のような長さN-1の文字列を考える
i番目の文字は、i番目の列とi+1番目の列について、ある状態で次に操作するべきなのがi番目のとき>、i+1番目のとき<である
前後に<と>を足した長さN+1の列を考えると、明らかに"<>"という形の連続部分列が存在するので、そこを操作すればよい
Rabbit Exercise
立式して x1, x1+x3-x2, x3 の階差を考えると、終わり！
木と整数
各頂点について「その頂点に書かれうる最小の数」と「その頂点に書かれうる最大の数」を考える
1 ≤ K よりこれらは明らかに有界で、またこれは最短路問題なので現実的な時間で求めることができる
ある頂点について
最小の数 > 最大の数であれば不可能
元々書かれていた数が [最小, 最大] に含まれていなければ不可能
ある隣接する頂点対について、最小の数のパリティが揃っていたら不可能
二部グラフなのでパリティが揃うということは、最初のK個の頂点の中に両立不可能な頂点対が存在する
(まあこれは最初から弾いておいた方が直感的かもしれない）
上のいずれでもなければ「最小の数」が求める答えそのものである
構成から隣接する頂点に書かれている数の差の絶対値は1以下
上でパリティが揃っている場合を弾いたので、0になることはない
感想
通すのと証明するので難易度感がずれるなあ
