Codeforces #405 Div.1 ABC
赤コーダーになりました。
http://codeforces.com/contest/790
A. Bear and Different Names
独立性を高い解法をとりたい。
s[i]="NO"だったときans[i]=ans[i+K-1]にすればいい。ans[i]とans[i+K-1]が重複カウントされるような区間は[i,i+K)しか存在しないため、他の選択に影響を与えない。
B. Bear and Tree Jumps
関連
- 全方位木DP
解法
ceil(d(u,v)/K) の総和を求めればいいのだが、ceilの扱いが厄介である。といっても簡単で、 ceil の振る舞いは d(u,v) mod K で変わるので、d(u,v) mod K = i となるような d(u,v) の総和を求めておけばいい。
全頂点間の総和を考えるのは大変なので、頂点 0 から他の頂点への距離の総和を求める問題を考える。これはO(n)の木DPで解ける。
単一始点の問題が解けたので、全頂点間の問題も解ける（全方位木DP）。
C. Bear and Company
関連
- 転倒数
解法
貪欲を考えると意外と奥が深いことが分かる。DPしたい。
左から順に決めていくDPを行う。swap 回数は転倒数と一致するので、転倒数を最小にすればいい。状態として持つのは
- 決定した要素の個数
- 使用した V の個数
- 使用した K の個数
- 最後に使ったのが V かどうか？
である。これだけ分かれば転倒数は計算できる。
以下の入力を考えてみよう。
先頭 6 個が決定されていて、V を 3 個、K を 1 個使ったと分かれば a[0]..a[5] に含まれる要素が分かる（並び順までは分からないが）。
たとえばa[6]=Kとしたなら以下のようになる。4,6,8 が 3 より大きいので転倒数が 3 増加する。
