tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

「『JOI 2011年春合宿 Day1 の問題『Dragon』は強実装』はウソ」はウソ

まずは、あちらをご覧ください。
次に、こちらをご覧ください。

#include<stdio.h>
#include<algorithm>
#include<set>
#include<map>
using namespace std;
pair<int,int> dat[100000];
int x[100000];
int y[100000];
int h,w,n;
int L=-2100000000;
int R=2100000000;
int X[100001],Y[100001];
long long calc(){
	set<int> S;
	map<int,int>M;
	for(int i=0;i<n;i++)M[dat[i].second]++;
	S.insert(L);S.insert(R);
	std::sort(x,x+n);
	std::sort(y,y+n);
	int xx=0;
	int yy=0;
	X[xx++]=x[0];
	Y[yy++]=y[0];
	for(int i=1;i<n;i++){
		if(x[i]!=x[i-1])X[xx++]=x[i];
		if(y[i]!=y[i-1])Y[yy++]=y[i];
	}
	X[xx++]=R;
	Y[yy++]=R;
	std::sort(dat,dat+n);
	long long ret=0;
	int at=0;
	for(int i=0;i<n;i++){
		if(i<n-1&&dat[i].first==dat[i+1].first)continue;
		long long left=(*(lower_bound(dat,dat+n,make_pair(dat[i].first,L)))).second;
		long long right=(*(lower_bound(dat,dat+n,make_pair(dat[i].first,R))-1)).second;
		int A=lower_bound(Y,Y+yy,left-1)-Y;
		int B=yy-(upper_bound(Y,Y+yy,right+1)-Y)-1;
		ret=max(ret,max(left-2-A,w-right-2-B));
		left=*(--(S.lower_bound(left)));
		right=*(S.upper_bound(right));
		A=lower_bound(Y,Y+yy,left)-Y;
		B=yy-(upper_bound(Y,Y+yy,right)-Y)-1;
		int C=xx-(upper_bound(X,X+xx,dat[i].first)-X)-1;
		ret=max(ret,max(left+h-dat[i].first-1-A-C,w-right+h-dat[i].first-2-B-C));
		while(at<n&&dat[at].first==dat[i].first){
			M[dat[at].second]--;
			if(M[dat[at].second]==0)S.insert(dat[at].second);
			at++;
		}
	}
	return ret;
}
int main(){
	scanf("%d%d%d",&h,&w,&n);
	for(int i=0;i<n;i++){
		scanf("%d%d",x+i,y+i);
		dat[i]=make_pair(x[i],y[i]);
	}
	std::sort(x,x+n);
	std::sort(y,y+n);
	int H=h-1;
	int W=w-1;
	for(int i=1;i<n;i++){
		if(x[i]!=x[i-1])H--;
		if(y[i]!=y[i-1])W--;
	}
	long long A=(long long)H*W;
	long long B=0;
	for(int i=0;i<4;i++){
		long long C=calc();
	//	printf("%d\n",C);
		B=max(B,C);
		for(int j=0;j<n;j++){
			x[j]=w-dat[j].second+1;y[j]=dat[j].first;
			dat[j]=make_pair(x[j],y[j]);
		}
		swap(h,w);
	}
	printf("%lld\n",A+B);
}

81行あります。81行という時点では、とても強実装とは言えないかのように見えます。
さらに言うと、本質は35行目から45行目だけなので、実質11行分の実装です。

ですが、この問題は本当に「強実装ではない」のでしょうか。35行目から45行目を改めて見てみます。

		long long left=(*(lower_bound(dat,dat+n,make_pair(dat[i].first,L)))).second;
		long long right=(*(lower_bound(dat,dat+n,make_pair(dat[i].first,R))-1)).second;
		int A=lower_bound(Y,Y+yy,left-1)-Y;
		int B=yy-(upper_bound(Y,Y+yy,right+1)-Y)-1;
		ret=max(ret,max(left-2-A,w-right-2-B));
		left=*(--(S.lower_bound(left)));
		right=*(S.upper_bound(right));
		A=lower_bound(Y,Y+yy,left)-Y;
		B=yy-(upper_bound(Y,Y+yy,right)-Y)-1;
		int C=xx-(upper_bound(X,X+xx,dat[i].first)-X)-1;
		ret=max(ret,max(left+h-dat[i].first-1-A-C,w-right+h-dat[i].first-2-B-C));

人が死ぬレベルにlower_bound,upper_boundとそれらに付属した+1やら-1やら-2があります。
こんなの誰が書いて短時間のデバッグにより修正することが出来るのでしょうか。他の人のソースコードを見ても、このような1や2といった数字が多数混在しています。
この箇所をデバッグするのに一体何時間かかるのでしょうか。僕はさすがにこの問題を解くのは4回目(うち挫折2回)なので、それなりに修正すべき点は把握しているつもりでしたが、それでも2時間かかっています(最初のコンパイルまでは15分です)。
この箇所は本当に複雑すぎます。やれ0-originだ1-originだの、leftの左は含まれる含まれないだの、lower_boundではなくupper_boundを使わなければならないだの、大量に考えて試行錯誤(デバッグの)をせねばなりません。こんなものが他のただ実装量が多いだけ(Orienteeringとか)より実装が楽とは思えません。
強実装は多実装ではありません。「手ごわい」実装なのです。少なくともJOI2011のなかでは最も強実装だと思いますし、この11行は行数に対する実装の大変さは過去の合宿でも最強レベルだと思います。
したがって,「『JOI 2011年春合宿 Day1 の問題『Dragon』は強実装』はウソ」は真っ赤なウソです.
選手の皆さんはこの問題を短時間で解けたら、実装力に自信をもつべきだと思います。