第6回 ドワンゴからの挑戦状 予選 : E - Span Covering

考え方を変えると一気に楽になる問題。
https://atcoder.jp/contests/dwacon6th-prelims/tasks/dwacon6th_prelims_e

問題

X個のマスが並んでいる。
個々にN個の矩形があり、それぞれL[i]の長さを持つ。
各矩形を、マス目を合わせてX個のマス目の上に合わせる。複数の矩形が重なってもよい。

各マスが最低1個矩形で覆われるような矩形の配置は何通りか。

解法

矩形長降順に処理することを考える。

複数の矩形が重なったり連続する場合、それらを合わせて1つの矩形として扱うことにしよう。
矩形の位置は無視して、いまいくつの矩形がありその総長がいくらかを状態として持つ。
すなわち状態として
dp(i,n,l) := i番目までの矩形を考えたとき、n個の矩形になってその総長はlであるような配置の組み合わせ
とする。
最終的に1個の長さXの矩形ができればそれがすなわち解となるので、dp(0,0,0)から初めてdp(N,1,X)を求めよう。

dp(i,n,l)の状態に新たな矩形を加えるとき、以下のケースが考えられる。

• 既存の矩形から離れて新たな矩形となる。
• 既存の矩形で覆われる範囲にかぶせる。つまりnもlも変化しない。
  • このような配置は、l-n*(L[i]-1)通りであり、個々の矩形の長さがわからなくとも総長のみで計算できる点がコツ。
• 既存の矩形のうち1つを、右か左に1～L[i]だけ延長する。
• 既存の矩形のうち2つを選び、間のスキマを1～L[i]埋めて連結して1つの矩形にする。

矩形の長さを降順にしているのがコツで、長さL[i]の矩形を処理しているとき、そこまで処理した矩形は必ずL[i]の長さを持つので、3つ以上の矩形を連結したりすることはない。

int N,X;
int L[505];

ll from[505][505];
ll to[505][505];
const ll mo=1000000007;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X;
	FOR(i,N) cin>>L[i];
	sort(L,L+N);
	reverse(L,L+N);
	from[0][0]=1;
	FOR(i,N) {
		ZERO(to);
		for(x=0;x<=N/2+2;x++) {
			FOR(y,X+1) if(from[x][y]) {
				// add
				if(y+L[i]<=X) (to[x+1][y+L[i]]+=from[x][y])%=mo;
				//keep
				if(x) (to[x][y]+=from[x][y]*(y-(L[i]-1)*x))%=mo;
				
				for(j=1;j<=L[i]&&y+j<=X;j++) {
					// conn1
					if(x) (to[x][y+j]+=from[x][y]*2*x)%=mo;
					// conn2
					if(x>=2) (to[x-1][y+j]+=from[x][y]*x*(x-1)*(L[i]-j+1))%=mo;
				}
			}
		}
		swap(from,to);
	}
	
	cout<<from[1][X]<<endl;
	
}

まとめ

ちょっと計算量心配かと思ったけどそうでもなかった。
位置を気にせず総長だけ気にしているのがコツだね。