CSAcademy Round #76 : D. Pyramids

Div2回なので上位参加者が少ない、ということを除いてもDiv2回の方が妙に成績がいい気がするのはなんでだろう。典型を早く書くのが得意？
https://csacademy.com/contest/round-76/task/pyramids/

問題

X軸方向が無限に伸び、Y軸方向が正の位置のみ定義されるグリッドがある。
各マスは0か1が埋められている。
座標(X,Y)が1のとき、(X-1,Y-1)、(X,Y-1)、(X+1,Y-1)も1でなければならない。

いくつか1であることがわかっているマスの位置が与えられる。
その状態であり得る1のマスの最小数を求めよ。

解法

X座標について、与えられるマスのX座標だけを考える。
X座標の差がdである2つのX座標において、1が埋まったマスのY座標の最大値の差はd以下でなければならない。
逆にdよりもY座標の最大値の差が大きい場合、Y座標の最大値が小さい方の値を大きくして差がdになるようにする。

この作業はダイクストラの要領で行ってもよいが、X座標の小さい順および大きい順で計2周配列を舐めていくほうが楽。
あとは与えられたX座標のうち隣接する2要素X,X'においてそれぞれY座標の最大値がY,Y'とするならば、X座標がX～X'である間の1であるマスの形状は三角形または台形を2つ合わせた形なのでO(1)で数え上げられる。

int N;
map<int,int> M;
vector<pair<ll,ll>> V;

ll hoge(ll X,ll Y1,ll Y2) {
	if(Y1>Y2) swap(Y1,Y2);
	
	if(Y2-Y1==X) return (Y1+Y2)*(X+1)/2;
	if(Y1+Y2-1<X) return (Y1*(Y1+1)+Y2*(Y2+1))/2;
	
	ll D=Y2-Y1;
	ll ret=(Y2+(Y2-(D-1)))*D/2;
	X-=D;
	
	if(X%2==0) {
		return ret+2*hoge(X/2-1,Y1-(X/2-1),Y1)+(Y1-(X/2));
	}
	else {
		return ret+2*hoge(X/2,Y1-(X/2),Y1);
	}
	
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x>>y;
		M[y]=max(M[y],x);
	}
	
	FORR(m,M) V.push_back(m);
	FOR(i,V.size()-1) V[i+1].second=max(V[i+1].second,V[i].second-(V[i+1].first-V[i].first));
	for(i=V.size()-2;i>=0;i--) V[i].second=max(V[i].second,V[i+1].second-(V[i+1].first-V[i].first));
	
	ll ret=0;
	ret+=V[0].second*(V[0].second-1)/2;
	ret+=V.back().second*(V.back().second-1)/2;
	FOR(i,V.size()-1) ret+=hoge(V[i+1].first-V[i].first,V[i].second,V[i+1].second);
	for(i=1;i<V.size()-1;i++) ret-=V[i].second;
	cout<<ret<<endl;
	
}

まとめ

恐らく多くの人はすぐに解法を思いつくけど、最後の台形を合わせた部分の面積を求めるのに1ずれで苦戦したと思われる問題。
自分もミスした。