読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces #405 Div.1 ABC

全方位木DP

赤コーダーになりました。

f:id:pekempey:20170319075315p:plain

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 かどうか?

である。これだけ分かれば転倒数は計算できる。

以下の入力を考えてみよう。

f:id:pekempey:20170319200417p:plain

先頭 6 個が決定されていて、V を 3 個、K を 1 個使ったと分かれば a[0]..a[5] に含まれる要素が分かる(並び順までは分からないが)。

f:id:pekempey:20170319201550p:plain

たとえばa[6]=Kとしたなら以下のようになる。4,6,8 が 3 より大きいので転倒数が 3 増加する。

f:id:pekempey:20170319201727p:plain