Codeforces #206 Div1 D. Transferring Pyramid

これはDiv1Dにしてもかなり面倒な問題。コード量は大したことないんだけどね。
http://codeforces.com/contest/354/problem/D

問題

高さN段の２次元ピラミッドがある。
上からi段目にはi個のセルが置いてあり、１段目のセルは1、2段目は2,3、3段目は4,5,6…と順に連番が振られている。
このうちK個色を塗るべきセルの位置が与えられる。

以下の処理を繰り返し行い、K個のセルの色を塗りたい(K個以外は塗っても塗らなくても良い)

• コストを３掛け、任意のセル１個を塗る。
• コストをS+2掛け、あるセルのsubpyramidを全部塗る。

K個の指定された色をすべて塗る最少コストを求めよ。

解法

K個のセルの色を塗るので、１つ目の処理を行えば最大でもコスト3Kで済む。
よって、ピラミッドの上部にありS+2＞3Kとなるようなセルは、１つ目の処理で塗ることが確定である。

実際は下から√6N段程度までなら２つ目の処理の方が得をする可能性がある。
よってそれより上は１つ目の処理で塗ることを確定させ、以下√6N段以下の事だけ考えよう。

dp[i][j]を、N段のピラミッドのうち右下i段分のサブプラミッドから、i段中左下j段のさらにサブピラミッド内において、塗るべきセルを全部塗る最少コストとする。
(わかりにくければhttp://codeforces.com/blog/entry/8672:Editorialの図を見よう)
このdp[i][j]を順次DPで更新していく。

dp[i][j]は、より大きな面積に相当するdp[i][j-1]内指定セルを塗りつぶすコストか、dp[i-1][j-1]に含まれずdp[i][j]に含まれるi段のサブピラミッドの左上部分を塗りつぶすコストのうち小さい方である。
という手順で計算していくとよい。
dp[i][0]だけは特殊で、各kにおいて、dp[i-1][k-1]の状態のサブピラミッドにたいし(i段のサブピラミッドにおける)k段目の一番左セルを頂点としたサブピラミッドを塗りつぶし、かつk段より上の部分を個別に塗りつぶすコストの最小値を求めていく。

文字でもコードでも説明がややこしいので、Editorialの図を見つつどの状態に対してどこを頂点とするサブピラミッドの塗りつぶしを行うかを丁寧に追わないと理解が難しい。

ll N,K,H;
vector<ll> V[100010];
ll dp[2][100020];
ll ret;

void solve() {
	int i,j,k,l,r;ll x,y; string s;
	
	cin>>N>>K;
	H=min(N,(ll)sqrt(6*K)+1);
	FOR(i,K) {
		cin>>x>>y;
		if(x<=N-H) ret+=3;
		else V[N-y].push_back(N-x);
	}
	FOR(i,N) sort(ALL(V[i]));
	
	dp[0][0]=(V[0].size() && V[0][0]==0)*3;
	
	for(y=1;y<N;y++) {
		int cur=y%2,pre=cur^1;
		
		dp[cur][0]=min(dp[pre][0]+V[y].size()*3,2LL+(y+1)*(y+2)/2);
		i=0;
		for(x=1;x<=min(H,y);x++) {
			dp[cur][0]=min(dp[cur][0], dp[pre][max(0LL,x-1)]+x*(x+1)/2+2+(V[y].size()-i)*3);
			while(i<V[y].size() && V[y][i]<=x) i++;
		}
		i=0;
		if(i<V[y].size() && V[y][i]==0) i++;
		for(x=1;x<=min(H,y);x++) {
			dp[cur][x]=min(dp[cur][x-1], dp[pre][x-1]+(V[y].size()-i)*3);
			while(i<V[y].size() && V[y][i]<=x) i++;
		}
	}
	cout << dp[(N-1)%2][0]+ret << endl;
	
}

まとめ

この問題、コード自体は短いのだけど、Editorial理解するのもだいぶ手間取ったし、説明も上記のとおりかなり文章では説明しにくいので、あまり記事作成の気乗りがしないのよね…。