ちょっと迷ったけど何とか解けた。
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個を順次答えよ。
- 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])の和を管理する。
2番目のクエリに対しては区間和を比較するだけ。
1番目のクエリに対しては、(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値には入らないよな…」→「2倍以上ということは何か誤差があるのかな、比でも計算するのかな?」→「対数で行けるか」という思考順でした。