パナソニックプログラミングコンテスト2020 : F - Fractal Shortest Path

遠回りしすぎたな…。
https://atcoder.jp/contests/panasonic2020/tasks/panasonic2020_f

問題

(3^30)*(3^30)のグリッドがある。
このグリッドは以下のように一部の移動不可なマスが設定される。

• グリッド縦横1/3ずつに区切り9個の区域に分けると、その中央一帯が移動不可である。
• 残り8つの区域は、また再帰的にそれぞれ9個ずつに分けて…と処理していく。

グリッド中2セルの位置が指定されたとき、隣接セルをたどってその間を移動する最短距離を求めよ。

解法

直行しようとすると、どうしても避けられない最大の移動不可矩形領域を考える。
その矩形領域が縦移動を分断するように置かれているならそれを左か右から回避すればよいし、横移動を分断するように置かれているなら上か下から回避すればよい。
もっと小さい矩形は、その過程で(移動距離を増やさず)避けられるので気にしなくてよい。

結局1辺(3^29)～(3^0)の移動不可矩形領域について、それぞれ経路を分断しないかどうか判定すればよい。

int Q;
ll X1,Y1,X2,Y2;
ll p3[32];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	p3[0]=1;
	FOR(i,31) p3[i+1]=p3[i]*3;
	
	cin>>Q;
	while(Q--) {
		cin>>X1>>Y1>>X2>>Y2;
		X1--;
		Y1--;
		X2--;
		Y2--;
		
		ll ret=abs(X1-X2)+abs(Y1-Y2);
		for(i=29;i>=0;i--) {
			ll x1=X1/p3[i];
			ll y1=Y1/p3[i];
			ll x2=X2/p3[i];
			ll y2=Y2/p3[i];
			if(x1==x2 && x1%3==1 && abs(y1-y2)>=2) {
				ret=abs(Y2-Y1)+min(X1%p3[i]+X2%p3[i]+2,2*p3[i]-X1%p3[i]-X2%p3[i]);
				break;
			}
			if(y1==y2 && y1%3==1 && abs(x1-x2)>=2) {
				ret=abs(X2-X1)+min(Y1%p3[i]+Y2%p3[i]+2,2*p3[i]-Y1%p3[i]-Y2%p3[i]);
				break;
			}
			
		}
		cout<<ret<<endl;
	}
}

まとめ

いろいろもったいなかった回。
みんなミス多いし自分だけでもないけどね。