AtCoder ARC #035 : D - 高橋くんとマラソンコース

ちょっと迷ったけど何とか解けた。
http://arc035.contest.atcoder.jp/tasks/arc035_d

問題

プレイヤーは2次元座標上の格子点におり、上または右の隣接格子点に順次移動できる。

N個のチェックポイント(P[i],Q[i])があたえられる。
マラソンコースがチェックポイントu→vと設定されたとき、(P[u],Q[u])→(P[u+1],Q[u1])→...→(P[v],Q[v])を順に辿らなければならない。
((P[i],Q[i])→(P[i+1],Q[i+1])は上・右移動だけで到達されることが保証される)

以下のクエリQ個を順次答えよ。

1. K番目のチェックポイントの位置をP[K]=A, Q[K]=Bで更新する。
2. ２つのチェックポイントの対(L1,R1)、(L2,R2)が与えられる。L1→R1とL2→R2の移動経路のうち、組み合わせ数が多いのがどちらかを答えよ。

解法

i番から(i+1)番のチェックポイントへの移動経路の組み合わせ数M[i]を考える。
dx=P[i+1]-P[i]、dy=Q[i+1]-Q[i]とするとである。
またi番からj番へのチェックポイントの組み合わせ数は、M[i]*M[i+1]*...*M[j-1]である。

これらの値はそのまま64bit値に格納しようとしてもとても収まらない。
ただし、計算に掛算割り算しかしていないことから、全体を対数で計算すれば単なる足し算引き算で処理できる。

まず整数nに対しlog(n!)のテーブルを作成しておく。
後はlog(M[i])=log((dx+dy)!) - log(dx!) - log(dy!)でlog(M[i])を求め、BITでlog(M[i])の和を管理する。
２番目のクエリに対しては区間和を比較するだけ。
１番目のクエリに対しては、(P[K],Q[K])が更新されるのでM[K-1]とM[K]だけ再計算し、BITを更新する。

注意点として、dx==0またはdy==0の時logを取らないようにしなければならない。
dx==0またはdy==0ならM[i]=1なので、log(M[i])=0とできる。

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V total(int e) {V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void update(int e, V val) {e++; while(e<=1<<ME) bit[e-1]+=val,e+=e&-e;}
};
BIT<double,22> bt;

int N,QQ;
ll P[201000],Q[202000];
double facl[404000];
double pat[202000];

double pp(int x1,int y1,int x2,int y2) {
	int dx=x2-x1,dy=y2-y1;
	if(dx==0 || dy==0) return 0;
	return facl[dx+dy]-facl[dx]-facl[dy];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	facl[1]=0;
	for(i=1;i<=400000;i++) facl[i+1]=facl[i]+log(i+1);
	
	cin>>N;
	FOR(i,N) cin>>P[i]>>Q[i];
	FOR(i,N-1) {
		pat[i+1]=pp(P[i],Q[i],P[i+1],Q[i+1]);
		bt.update(i+1,pat[i+1]);
	}
	
	cin>>QQ;
	while(QQ--) {
		int t,k,a,b,l1,r1,l2,r2;
		cin>>t;
		if(t==1) {
			cin>>k>>a>>b;
			k--;
			
			if(k!=0) {
				double np=pp(P[k-1],Q[k-1],a,b);
				bt.update(k,np-pat[k]);
				pat[k]=np;
			}
			if(k!=N-1) {
				double np=pp(a,b,P[k+1],Q[k+1]);
				bt.update(k+1,np-pat[k+1]);
				pat[k+1]=np;
			}
			P[k]=a;
			Q[k]=b;
		}
		else {
			cin>>l1>>r1>>l2>>r2;
			l1--,r1--,l2--,r2--;
			if(bt.total(r2)-bt.total(l2) > bt.total(r1)-bt.total(l1)) _P("SECOND\n");
			else _P("FIRST\n");
		}
	}
}

まとめ

本番、「当然64bit値には入らないよな…」→「２倍以上ということは何か誤差があるのかな、比でも計算するのかな？」→「対数で行けるか」という思考順でした。