AtCoder ARC #109 : D - く

これ11月だったか。
https://atcoder.jp/contests/arc109/tasks/arc109_d

問題

初期状態で、格子点(0,0)(1,0)(0,1)に石が置いてある。
1つ任意の石を選び、隣接する格子点で連結性を崩さない範囲で、他の格子点に動かす、という作業を行うとする。
指定された３マスに石を置くのにかかる手順は何通りか。

解法

3つの石のX座標の和と、Y座標の和を考える。
各状態に対し、この和は一意である。
そこで、この和を(1,1)から指定マスの和に移動することを考える。

実際に小さい座標で総当たりしてみると、移動にかかる手数は法則性があるので、O(1)で求められる。

int T;
ll X[3],Y[3];

ll hoge(ll x,ll y) {
	x--;
	y--;
	ll ox=x, oy=y;
	x=(x>=0?(x-(x+1)/3):-x-(-x+2)/3);
	y=(y>=0?(y-(y+1)/3):-y-(-y+2)/3);
	
	if(ox==0&&oy==0) return 0;
	if(ox==1&&oy==1) return 1;
	return max(x,y)+(ox==oy);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		FOR(i,3) cin>>X[i]>>Y[i];
		cout<<hoge(X[0]+X[1]+X[2],Y[0]+Y[1]+Y[2])<<endl;
	}
}

まとめ

うーん、小さい範囲で総当たりぐらいさっさとやればよかったな。