Educational Codeforces Round 51

スポンサーリンク

A. Vasya And Password

全種類あるなら何もしない.2種あるなら1か所変更.1種しかないなら2か所変更.

B. Relatively Prime Pairs

(x,x+1) でよいです.

C. Vasya and Multisets

差を考えると,頻度 $1$ のものは $+1, -1$,頻度 $2$ のものは $+0$,頻度 $3$ 以上もののは $0,+1,-1$ として使えます.頻度 $1$ のものを均等に配分したあと存在したら頻度 $3$ 以上のもので調整します.

D. Bicolorings

上の色・下の色・連結成分数を状態として dp します.

E. Vasya and Big Integers

dp をします.dp[i] から dp[j] への遷移が可能であるかは,多くの場合は長さだけで決まります.この部分は dp テーブルと同時に dp 累積和テーブルも作っていけば簡単に計算できます.

$O(1)$ 個の長さについて遷移可能であるかを調べればよいです.これは適当な部分文字列比較手法を使えばよいです.

F. The Shortest Statement

木にいくつかの辺を足したものと見なせます.木上の辺のみ使う場合と,そうでない場合を計算します.そうでない場合は,追加辺の端点からの最短距離を求めておけばよいです.

G. Distinctification

最終的なコストは $\sum a_ib_i$ から計算できるので,最適な終状態(結果的な $a_i$)が分かればよいです.

操作結果の multiset は一意に決まります.最小値はひとつ以上残ることに注目して,最小値から順に決めていけるからです.適当な方法で multiset を作ったとき,連番になっている部分は自由に置換できます.よって高速化を無視すれば,一要素ずつ追加しながら multiset がどうなるかを調べて,連番になっている部分を $b_i$ をソートして $\sum a_ib_i$ を計算するという感じになります.

UnionFind と何らかのデータ構造を持って,weighted union heuristic でマージすることを考えます.すると,次が行えればよいことが分かります:

  • $b_i$ からなる multiset を管理する.要素をひとつ追加するたびに,ソートして $b_i$ が昇順 $k_i$ 番目に来るとする.このとき $\sum k_ib_i$ を計算せよ.

これはモノイド区間クエリの機能がある平衡二分木を使えばよいです.UnionFind の連結成分ごとにこれを持ちます.

CodeForces
スポンサーリンク
シェアする
maspyをフォローする
maspyのHP
タイトルとURLをコピーしました