Codeforces Round #303 (Div. 2 only) - hirokazu1020の日記

http://codeforces.com/contest/545
A-Toy Cars
塗りつぶすだけ

B-Equidistant String
概要
長さnの0,1からなる文字列s,tが与えられる。
s,tと編集距離が等しい文字列を出力、存在しないなら"impossible"と出力せよ。
解法
ある位置のsとtの数字が異なる場合だけ変化させたときに編集距離の差が2増減する。
よってsとtの編集距離/2の分だけsの数字をtにあわせればいい。

C-Woodcutters
概要
n本の木のx座標 $x$ と高さ $h$ が与えられる。木を左に切り倒した場合は $[x_i-h_i,x_i]$ 、右に倒した場合は $[x_i,x_i+h_i]$ を占有する。
切り倒す場所に既に木がないときだけ木を切り落とせる。切り落とせる木の最大数を求めよ。
解法
xの昇順に考えたとき、左に倒せる場合は倒したほうが明らかに最適、
左に倒せず右に倒せる場合は右に倒さなかった場合の最適解が倒した場合の最適解を上回ることはないので貪欲に倒していけばいい。

D-Queue
概要
キューに人が並んでいる。それぞれの人に対応するには $t_i$ 時間かかることがわかっている。対応開始までに $t_i$ 時間以上待たされるとがっかりする。
人を並び替えて達成できるかっがりしない人の最大数を求めよ。
解法
validな解を $b$ として [tex:b_i > b_j (i $i,j$ が存在するときswapしても解として成り立つので、ソートされた解だけを考えればいいというよくあるパターン。E-Paths and Trees
概要
始点の頂点番号と重みつき無向グラフが与えられる。
始点からの最短距離を変えないような重みの和が最小となる全域部分グラフの辺を求めよ。
解法
ダイクストラして最短距離を構成するのに明らかに不必要な辺を除くとDAGになる。
あとはDAG上で最小全域有向木を求めればいい。方法は各頂点について始点方向に接続する辺のうち重みが最小のものだけ残して残りは削除すればよい。一般の最小全域有向木ライブラリでも通るらしい。