Codeforces Round 311 D Vitaly and Cycle

問題

http://codeforces.com/contest/557/problem/D
多重辺や自己ループを含まないグラフが与えられる。またこのグラフでは辺の重みは全て1として考える。
この辺にいくつか辺を追加して長さ奇数の閉路(ただし自己ループではない)を一つ以上含むグラフにしたい。ただし元々辺があるノード間に新たに辺を追加するのはできない。

最小何本の追加で達成できるか。またその最小本数の追加は何通りあるか。

解法

入力で与えられるグラフの頂点数をn,エッジ数をmとする。
追加する最小本数tは0,1,2,3のどれかである。
グラフの最大次数が0の時、辺は1本もないのでt=3で、追加の仕方は全部の頂点から3個選んだ通りになるのでnC3となる。
グラフの最大次数が1の時、長さ3の閉路を作ればよく、この時t=2である。この時は辺とその辺に含まれない頂点の中から1個選べば良いのでm*(n-2)である。
それ以外の時、BFSまたはDFSによってグラフに奇数の閉路がないか調べる。あった場合はt=0で追加の仕方は1通り。奇数の閉路があった場合、頂点を2色で塗り分けて同じ色どうしの頂点をエッジで結べば長さ奇数の閉路ができるので n1 chose 2 + n2 choose 2で計算できる。ただしn1,n2はそれぞれ色1,2で塗られた頂点の個数。

Codeforces Round 311 C : Arthur and Table

問題
http://codeforces.com/contest/557/problem/C
n本の脚がついたテーブルがある。各脚の長さがL[i]で与えられる。このテーブルの脚を何本か切り落としてテーブルをStableな状態にしたい。テーブルがStableであるとは
・一番長い 脚の本数が残っている脚の中で過半数を占めている
ということを指す。また、脚が1本だけのテーブルはStableであるとする。
テーブルの各脚を切り落とすにはコストが必要でそれぞれのコストがd[i]で与えられる。
Stableにするための最小コストを求めよ。
制約としてn<=10^5, L[i]<=10^5, 1<=d[i]<=200

解法
脚の長さでソートしたあと、最長の脚をL[i]にした時の最小コストというのを各iについて求めれば良い。
最長の脚をL[i]にした時の最小コストというのは、
1. L[i]より長い脚を全て切る
2. L[i]より短い脚を、L[i]の脚が過半数になるようにコストが小さい順に切っていく
ことによって得られる。
1はコストの累積和をあらかじめ計算しておけば簡単に求められる。
2は今脚L[i]をみている時に、それまでみていた脚の中でコストjの脚が何本あるかというヒストグラムを保持しておけば高速に求められる(d[i]が200以下であるため)

CF Round 309 C Kyoya and Colored Balls

問題:

http://codeforces.com/contest/554/problem/C
k色ボールが全部でn個ある。
各色のボールはa[i]個ある(つまりn=Σa[i])
このボールを以下の条件を満たすように横に並べる時、その並べ方は何通りあるか。ただし同じ色のボールは区別しない。

条件: 全ての色i=1,2,...,k-1に対して、並べた色iのボールの中で一番左側にあるものをp[i]と表すと、p[i]はp[i+1]の右側にある。

入力はkと各a[i]で、制限はn<=1000, k<=1000である。

解法:

例えばk=2の場合を考えてみます。
一番左にくるのは必ず色kでなければならず、その時残りのボールの並べ方について考えてみます。
まず最初に色1のボールa[1]個を横一列に並べると、一番左に置いたもの以外の色2のボールa[2]-1個は色1のボールに割り込む形で入れていくことが可能です。
例えばa[1]=○5,a[2]=3の場合だと、まず最初に
1 1 1 1 1 2
と並べたあと残りのa[2]-1=2個のボールは
○ 1 ○ 1 ○ 1 ○ 1 ○ 1 ○ 2
この6個ある○の中のどこかに2個入れるということになります。これは重複組み合わせになっているのでconbinationを使って求めることができます。
3色以上の場合も同様で、まず最初に色1を並べる。そのあとに一番左に置いたあとに色2を並べる。その次に一番左に色3を置いたあとに置けるところに色3のボールを置いていく...というのを繰り返すことで求めることが出来ます。