Hatena::Grouptopcoder

解いた問題

TopCoder: OgieKako / Codeforces: OgieKako

 | 

2012-01-15

SRM529 900

14:02

次の問題を考える.

N点のグラフがある. 頂点は,「大きい」か,「小さい」のいずれか.

大きい頂点は,次数B 以上, 小さい頂点は,次数S 以下 でなければならない.

また,グラフは連結でなければならない.

大きい頂点の数 としてありうるのは何通りか.

この問題の解を A(N,B,S) とする.

Nlo<=N<=Nhi, Blo<=B<=Bhi, Slo<=S<=Shi かつ,S < B を満たす,すべてのN,B,S に対する

A(N,B,S) の総和を求めよ.

  • Nlo <= Nhi <= 1000万
  • Blo <= Bhi <= 200
  • Slo <= Shi <= 200

----------

B,S を固定する. b を大きい点の数とする.

b=0と,b>0 で場合分けする.

  • b=0のとき

S>1 なら,パスとすればよいので,すべてのN でOK.

S=1 なら,N<=2 の場合のみOK.

  • b>0のとき

B>=N なら明らかに不可能.それ以外の場合で考える.

大きい点同士は完全グラフとしてよい.大きい点全体の残り次数は,b* (B-(b-1)).

これが,小さい点全体から出てよい次数 (N-b)*S よりも以下である場合のみOK.

連結性を保つ条件については,ある小さい点が非連結になっていたら,大きい点にくっつけてやればいいから大丈夫.

(これが,b=0 を別にした理由)

式変形すると,

 b^2 - (S+B+1)b + SN \ge 0

となる.

判別式は, D = (S+B+1)^2-4SN となり,

 D \lt 0 \Leftrightarrow \gt \frac{(S+B+1)^2}{4S} \lt N ... (1)

のとき,すべてのb がOK.

よって,Nを小さい方から増やしていき,(1) を満たしたら,それ以上の部分についてはO(1) で計算できる.

計算するとき,注意しないといけないのは,条件を満たす,bの範囲は,

b<= alpha, b >= beta という形で書かれるが,alpha,beta が一致する場合に,それをダブルカウントしないようにしないといけない.これで一回WAをだしてしまった.

*1

計算回数は

 \sum_{S,B\le200}\frac{(S+B+1)^2}{4S} くらいで,計算してみると大丈夫そうとわかる.

*1:というか,判別式の条件を < でなく <= にするべきだった.

 |