kmjp's blog

競技プログラミング参加記です

天下一プログラマーコンテスト2015 本戦（オープン） : E - 天下一コップ

その他コンテスト

大体の方針はすぐに立ったけど、細かい微調整でだいぶ時間を食った。
ただ周りが先にFに行ってくれたおかげか、オープン参加者内でFAでした。
http://tenka1-2015-final-open.contest.atcoder.jp/tasks/tenka1_2015_final_e

問題

N個の長方形がある。
それぞれ幅W[i]、高さH[i]である。
これらの長方形を任意の順で並べ替え、底辺が一致するようにして横に並べて接着することを考える。

接着後の図形は一部くぼみがある場合があり、その場合そこはコップであるとみなし水を入れることができる。
長方形の並べ方N!において、上記水の入れられる容積(奥行き方向は常に1であるとみなす)の総和を求めよ。

解法

挿入DPで解く。
まず長方形を高さで降順にソートする。

(1-originで)高い順にx番の長方形に対し、その上にy番(y＜x)の高さまで水が注がれるケースの組み合わせ総数f(x,y)を考える。
そうすると解は \sum_{1 \le y \lt x \le N} f(x,y)\times (H_y - H_x) \times W_xである。
このf(x,y)がO(1)で求められれば、総和はO(N^2)で求められる。
O(N^2)では部分点にしかならないが、まずはf(x,y)を考えよう。

x番の上にy番までの高さに水が注がれるには、y番未満の長方形は全部x番の左で、y番だけがx番の右か、その逆である。
条件を満たす最初x個の並べ方は以下の積となる。

  • y番未満の並べ方は(y-1)!通り。
  • y番目はy番全体の左端か右端の2通り
  • ここで先にx番目を並べる。y番未満の(y-1)個とy番の間1通り。
  • 残された(y+1)～(x-1)番は、順に適当に挿入するので(y+2)*(y+3)*...*x通り

よって上記4つの値を掛け合わせると (y-1)! * 2 * 1 * \frac{x!}{(y+1)!} = \frac{2*x!}{y*(y+1)}通り。
事前に階乗を前処理で計算しておけばこの値はO(1)で求められる。
残り(N-x)個を順に埋めていくことを考えると、まずN個中先頭x個を埋める埋め方が {}_N C_x通りで、残り(N-x)個を埋める埋め方は (N-x)!通り。
よって全部掛け合わせると f(x,y) = \frac{2*x!}{y*(y-1)} * {}_N C_x * (N-x)!。
あとは各(x,y)の対に対して \sum_{1 \le y \lt x \le N} f(x,y)\times (H_y - H_x) \times W_xを計算すれば答え。

次にこの式えをO(N)にすることを考える。
良く見るとf(x,y)はxの式とyの式の積になっており、 f(x,y) = \frac{1}{y*(y-1)} * (2*x! * {}_N C_x * (N-x)!)と分割できる。
よってxを固定すると、 g(y)=\frac{1}{y*(y-1)}としたとき、 \sum_{1 \le y \lt x} f(x,y)\times (H_y - H_x) \times W_x =
(\sum_y g(y)*(H_y - H_x)) * (2*x! * {}_N C_x * (N-x)!) \times (H_y - H_x) \times W_xと変形できる。
そこで2つの累積和 p(y) = \sum_{i\le y} (g(i)*H_i)と q(y) = \sum_{i\le y} g(i)を順次求めていくと先の式は (p(y) - q(y)*H_x) \times (2*x! * {}_N C_x * (N-x)!) \times (H_y - H_x) \times W_xとなり各xについてO(1)で計算できるようになる。

int N;
pair<int,int> B[101010];
int H[101010],W[101010];
ll sum[101010];
ll mo=1000000007LL;
ll tot;
const int NUM_=110001;
ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];

ll combi(ll N_, ll C_) {
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>B[i].second>>B[i].first;
	
	
	sort(B,B+N);
	FOR(i,N) H[i]=B[N-1-i].first,W[i]=B[N-1-i].second;
	FOR(i,N) sum[i+1]=sum[i]+H[i];
	
	inv[1]=fact[0]=factr[0]=1;
	for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
	for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	
	ll pat=0,invsum=0;
	for(i=2;i<N;i++) {
		
		y=i-1;
		if(y>=1) {
			(pat += inv[y+1]%mo*inv[y+2]%mo*H[y])%=mo;
			(invsum += inv[y+1]%mo*inv[y+2])%=mo;
		}
		ll tp=pat-invsum*H[i]%mo;
		tp=(tp+mo)%mo;
		(tot += fact[i+1]*2%mo*tp%mo*fact[N-(i+1)]%mo*combi(N,i+1)%mo*W[i])%=mo;
	}
	
	cout<<tot%mo<<endl;
}

まとめ

挿入DPはSRMでもyukicoderでも苦戦した記憶があったので、今回解けて良かった。

ところで本戦参加者の懇談会もこんなコップだったのでしょうかね。