kmjp's blog

競技プログラミング参加記です

Mujin Programming Challenge 2018 : G - 移動

うーむ、あと一歩が詰められず。
https://beta.atcoder.jp/contests/mujin-pc-2018/tasks/mujin_pc_2018_g

問題

2次元座標上において、互いに向きが異なる3つのベクトルが与えられる。
原点から始め、いずれかのベクトルの示す相対位置に移動する、もしくはその場にとどまるという作業をK回行う。
その結果止まる可能性のある座標は何通りか。

解法

各ベクトルの移動回数をa,b,cとする。
3つのベクトルをv0,v1,v2とすると0≦a,b,cかつ0≦a+b+c≦Kの範囲でa*v0+b*v1+c*v2が何通りあるかを求めることになる。

単純にa,b,cの組み合わせを考えると、これはComb(K+3,6)に一致する。
しかし座標が2次元のため3つのベクトルは独立ではないので、a,bをいくつかいじるのと、cをいくつかいじるので結果が等しくなるケースがある。
これを求めよう。

a*v0+b*v1+c*v2=a’*v0+b’*v1+c’*v2となるケースを考えると、(a-a')*v0+(b-b')*v1+(c-c')*v2=0となる。
この時、(a-a'):(b-b'):(c-c')の比率は一定となるので、この比をA:B:Cとしよう。
なおA:B:CはGCDが1となるようにする。
A:B:Cは連立方程式を解けば求められる。

さて、そうすると3ベクトルの移動回数がa,b,c回の場合と、(a+A),(b+B),(c+C)回の移動先は等しくなる。
よってそのようなケースを重複分として取り除こう。

(0≦a,b,cかつ0≦a+b+c≦K)の示す領域と(0≦(a+A),(b+B),(c+C)かつ0≦(a+A)+(b+B)+(c+C)≦K)の共通部分を求めComb(K+3,6)から引けばよい。
A,B,Cの符号を反転できることを考えると、

  • A,B,Cの符号が一致するならComb*1+3,6)を引く
  • A,B,Cの符号が一致しないなら、例えばA,Bの符号が一致する場合Comb*2+3,6)を引く

上記は2つの三角錐の共通部分を考えるとわかる。

int Q;
ll X[3],Y[3],K;
ll mo=998244353;

ll AP,AQ;
ll BP,BQ;

ll modpow(ll a, ll n=mo-2) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

ll hoge(ll v) {
	if(v<0) return 0;
	return (v+3)*(v+2)%mo*(v+1)%mo*modpow(6)%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>Q;
	while(Q--) {
		FOR(i,3) cin>>X[i]>>Y[i];
		cin>>K;
		
		AP=X[2]*Y[1]-Y[2]*X[1];
		AQ=X[0]*Y[1]-Y[0]*X[1];
		BP=X[2]*Y[0]-Y[2]*X[0];
		BQ=X[1]*Y[0]-Y[1]*X[0];
		
		if(AQ<0) AP=-AP, AQ=-AQ;
		if(BQ<0) BP=-BP, BQ=-BQ;
		
		ll g=__gcd(abs(AP),abs(AQ));
		AP/=g;
		AQ/=g;
		g=__gcd(abs(BP),abs(BQ));
		BP/=g;
		BQ/=g;
		
		ll AA,BB,CC,G;
		AA=AP*BQ;
		BB=BP*AQ;
		CC=-AQ*BQ;
		
		G=__gcd(abs(AA),__gcd(abs(BB),abs(CC)));
		AA/=G;
		BB/=G;
		CC/=G;
		
		ll ret=hoge(K);
		if(abs(CC)<=K && abs(AA)<=K && abs(BB)<=K) {
			ll C[2]={};
			C[AA>0]+=abs(AA);
			C[BB>0]+=abs(BB);
			C[CC>0]+=abs(CC);
			ret-=hoge(K-max(C[0],C[1]));
		}
		cout<<(ret+mo)%mo<<endl;
		
	}
}

まとめ

A,B,Cは求めたけどその後のツメが甘かった。

*1:K-(A+B+C

*2:K-max(abs(A+B),C