XYZ Triplets [エイシング プログラミング コンテスト 2020 C]

https://atcoder.jp/contests/aising2020/tasks/aising2020_c

解説

https://atcoder.jp/contests/aising2020/submissions/15185161

こういう系が初見だと何から手を付ければいいか分からないかもしれない。
基本は全探索なので、全探索を考える。
Nをそれぞれ答えるので、Nの全探索を考えたくなるが…これは罠である。
x,y,zを全探索しよう。

全探索範囲について

x,y,zが1以上の整数としか条件になっていないので、上限が困るところ。
この上限がどのくらいかで、全探索ができるかが変わる。
x,y,zは実は上限100までで探索すればいい。
これはx=100であるだけで、x²部分で10⁴となるのでこれ以上増やしても、計算結果がN以下とならない。
よって、x,y,zは[1,100]で全探索する。
x,y,zでやると、全体で10⁶通りとなるので、これは問題ない。
（探索空間が10⁶通りなら行けるし、10⁷くらいなら怪しいし、それ以上なら無理）
あとは、
ans[n] := 計算結果がnである組合せ
を数え上げていって、最後に順番に答えればよい。

int N;
int ans[10101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(x, 1, 101) rep(y, 1, 101) rep(z, 1, 101) {
        int tot = x * x + y * y + z * z + x * y + y * z + z * x;
        if (tot <= N) ans[tot]++;
    }
    rep(i, 1, N + 1) printf("%d\n", ans[i]);
}