Codeforces Round #375 (Div. 2)

http://codeforces.com/contest/723

The New Year: Meeting Friends

問題概要

数直線上に3軒の家がある。3つのうちどれかを集合地点としたとき、各人の移動距離の最小値を求めよ。

解法

集合地点は中央値にするのが最善なので、（最大値）-（最小値）が答えになる。

Text Document Analysis

問題概要

括弧の外にある単語の最大長、および括弧の中にある単語の総数をそれぞれ求めよ。

解法

地道にやる。もっときれいに書けるはず。

Polycarp at the Radio

問題概要

数列が与えられる。1..m の出現頻度の最小値が最大になるように a[i] を書き換えよ。また書き換え回数の最小値も求めよ。

解法。

最小値は floor(n/m) である。a[i]>m あるいは頻度が floor(n/m) より大きいものを貪欲に頻度が floor(n/m) より小さい値に変えればいい。

a[i]>m が残っていても問題ないので注意。

Lakes in Berland

問題概要

池の個数を丁度 K 個にするには最小でいくつのマスを陸に変える必要があるか。

解法

union find やるだけ。

One-Way Reform

問題概要

無向グラフが与えられる。入次数と出自数が等しい頂点の個数が最大になるように辺に向きをつけよ。

解法

奇数次の頂点は入次数と出次数を等しくできない。一方、偶数次の頂点はすべて等しくなるような割当が作れる。

奇数次の頂点はかならず偶数個あるので、2つずつマッチングして間に辺を張る。するとすべての頂点が偶数次になるためオイラー閉路が存在する。このオイラー閉路を作ればいい。

中国人郵便配達問題を知ってると思いつきやすいかも。

st-Spanning Tree

問題概要

無向グラフが与えられる。頂点 s の次数が ds 以下、頂点 t の次数が dt 以下であるような全域木をどれでもいいので一つ示せ。

解法

まず s, t を無視して全域木を作る。連結成分を潰してひとつの頂点として見なせば、下図の雰囲気の問題になる。

• s, t 両方に隣接していない連結成分があったら Impossible
• s, t の両方に辺が張られている連結成分は 2 つ以上作ってはならない（閉路ができるため）。
• ある連結成分 c に対して、辺(c,s)あるいは辺(c,t) のうち一方しかないのであれば、その辺は必ず使わなければならない。
• s から t への辺がある場合は少しだけ注意。

夏休み終了。つらい。