大体の方針はすぐに立ったけど、細かい微調整でだいぶ時間を食った。
ただ周りが先に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)を考える。
そうすると解はである。
この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つの値を掛け合わせると通り。
事前に階乗を前処理で計算しておけばこの値はO(1)で求められる。
残り(N-x)個を順に埋めていくことを考えると、まずN個中先頭x個を埋める埋め方が通りで、残り(N-x)個を埋める埋め方は通り。
よって全部掛け合わせると。
あとは各(x,y)の対に対してを計算すれば答え。
次にこの式えをO(N)にすることを考える。
良く見るとf(x,y)はxの式とyの式の積になっており、と分割できる。
よってxを固定すると、としたとき、
と変形できる。
そこで2つの累積和と を順次求めていくと先の式は となり各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でも苦戦した記憶があったので、今回解けて良かった。
ところで本戦参加者の懇談会もこんなコップだったのでしょうかね。