問題文中で定義された距離は平行移動で不変であり、\((X,Y)\) と\((0,0)\) の距離は \(\max(|X|,|Y|,|X-Y|)\) です。そこで \((X,Y)\mapsto(X,Y,X-Y)\) とする線形座標変換を考えると、変換後の座標におけるチェビシェフ距離が変換前と同じ距離を与えます。

したがって変換後の座標における問題は、「集合 \(T\) であって、\(T\) に属する全ての点が \(D\times D\times D\) の立方体に収まるものは何個か？」となります。この問題は以下のように解くことができます。

条件を満たす集合を、その集合に属する点の各座標の最小値に注目して数え上げます。条件を満たす集合のうち、各座標の最小値が \(X,Y,Z\) になるような集合の個数は、\([X,X+D]\times[Y,Y+D]\times[Z,Z+D]\) に含まれる点を、\(x\) 座標が \(X\) かどうか / \(y\) 座標が \(Y\) かどうか / \(z\) 座標が \(Z\) かどうかの \(8\) 通りに分けて数えることで求めることができます。これは、\(X,Y\) を固定するごとに、すべての \(Z\) についてを差分更新により \(O(N)\) で求めることができるため、全体で \(O(N^3)\) で問題に答えることができます。

writer解(C++)
writer解(Python)