はまやんはまやんはまやん

hamayanhamayan's blog

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であるだけで、x2部分で104となるのでこれ以上増やしても、計算結果がN以下とならない。
よって、x,y,zは[1,100]で全探索する。
x,y,zでやると、全体で106通りとなるので、これは問題ない。
(探索空間が106通りなら行けるし、107くらいなら怪しいし、それ以上なら無理)
あとは、
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]);
}