AtCoder ABC #288 (Toyota Programming Contest 2023 Spring Qual A) : G - 3^N Minesweeper

前半で躓きすぎた。
https://atcoder.jp/contests/abc288/tasks/abc288_g

問題

1辺3マス、N次元の計3^NマスからなるN次元グリッドを考える。
いくつかのマスに、爆弾が配置されている。
各マスには、各次元で1以下の距離にある近隣マスにおける爆弾の個数が書かれているとする。

爆弾がある場所を求めよ。

解法

1次元ずつ処理して行く。
ある次元において、

• 座標が0のマス : 書かれている個数は、座標が0と1のマスの総和
• 座標が1のマス : 書かれている個数は、座標が0と1と2のマスの総和
• 座標が2のマス : 書かれている個数は、座標が1と2のマスの総和

となる。
これらを足し引きすると、座標が0,1,2のマスには、その座標と一致するマスの総和のみが書かれた状態を求めることができる。
これを1次元ずつ処理して行けばよい。

int N;
int A[9*9*9*9*9*9];
int B[9*9*9*9*9*9];
int p3[13];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	p3[0]=1;
	FOR(i,12) p3[i+1]=p3[i]*3;
	cin>>N;
	FOR(i,p3[N]) cin>>A[i];
	FOR(i,N) {
		x=p3[i];
		FOR(j,p3[N]) {
			y=j/x%3;
			if(y==0) B[j]=A[j+x]-A[j+2*x];
			if(y==1) B[j]=A[j-x]+A[j+x]-A[j];
			if(y==2) B[j]=A[j-x]-A[j-2*x];
		}
		swap(A,B);
	}
	FOR(i,p3[N]) cout<<A[i]<<" ";
	
	
}

まとめ

もっと複雑に考えてしまった。