考察
各ternary桁で中心digit 0,1,2のneighbor許容集合はそれぞれ{0,1},{0,1,2},{1,2}であり、入力Aはこれらの直積領域にあるbomb数である。
求めるBは各桁を{0},{1},{2}へ固定した直積領域の値なので、各次元の3個の区間和から3個のsingleton値を逆変換すればよい。
近傍条件が桁ごとの直積なので、N次元変換は1次元の逆変換を各桁へ順に施すtensor productとして分離できる。
採用する候補: 各ternary桁について3値の局所逆変換を全3^N entryへ適用する多次元差分変換。
3×3の関係をN軸へ順番に解くだけで、入力の近傍和から各位置の0/1を復元できる。
棄却する候補: 3^N個のbomb有無を未知数とする一般の連立一次方程式をGaussian eliminationする。
行列dimensionが最大531441で、直積構造を無視した一般消去は不可能である。
棄却する候補: 全bomb配置2^(3^N)を列挙してAと一致するか調べる。
位置数自体が指数的であり、そのpower setは到底列挙できない。
1次元で近傍和をF_0=v_0+v_1、F_1=v_0+v_1+v_2、F_2=v_1+v_2とすると、v_0=F_1-F_2、v_1=F_0+F_2-F_1、v_2=F_1-F_0で復元できる。
他の桁条件を固定したまま同じ3式が成立するため、1軸変換後の値を次軸の入力としてin-placeに更新できる。
AをindexのN桁ternary配列とみなす。各axisのstride=3^axisについて、他桁が同じ3 entry (f0,f1,f2)を全blockから取り出し、(f1-f2, f0+f2-f1, f1-f0)へ同時更新する。全N軸の処理後、array[index]がその位置のbomb有無B_indexなので順に出力する。
典型の発動条件
多次元累積和の逆変換
発動条件: 入力が各座標軸の小区間の直積上の和で与えられるとき。
各軸の局所差分を順に適用してpoint値へ戻す。
Kronecker積構造の分離
発動条件: 高次元線形変換が同じ小行列の各軸作用として表せるとき。
巨大行列を作らず、strideごとの小変換を反復する。
問題固有の要素
ternary digit差≤1というneighbor定義は、数直線上の距離ではなく各桁独立の3値区間なので、近傍和matrixが完全にtensor分解する。
別の問題へ持ち帰る視点: 座標が進数digitで定義された問題では、条件がdigitwiseなら状態空間全体の演算を各桁変換へ分解できる。
正当性
一次元の近傍和はF_0=v_0+v_1,F_1=v_0+v_1+v_2,F_2=v_1+v_2で、その逆式が一意にvを復元する。N次元の近傍は軸ごとの直積なので変換はこの行列のtensor積であり、各軸逆変換を順に適用すると全変換の逆になる。同一組の旧3値を保存して同時更新すればin-placeでも式を保てる。
実装上の注意
- 3値をin-placeに1つずつ上書きせず、旧f0,f1,f2を一時変数へ保存してから同時更新する。
- 値は中間的に負になり得るのでsigned整数を使い、全軸後の値が保証により0または1になることを確認する。
- axis順とindexのlowest ternary digitに対応するstride=1,3,9,…を揃える。
復習の核
- N=1で3本の式を直接逆算し、N=2では一方の桁を固定した3-entry更新を縦横に1回ずつ施してsingleton値になるか確認する。
計算量と制約
時間
O(N3^N)。各ternary軸の3値組を一度変換する。
空間
O(3^N)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 12; There is a placement of bombs consistent with A_0, A_1, \ldots, A_{3^N-1}.; All values in the input are integers.
出典