https://beta.atcoder.jp/contests/agc027/tasks/agc027_d
解法
https://beta.atcoder.jp/contests/agc027/submissions/3208300
公式解説放送を見ましょう。
動画を見れば、考え方はそんなに難しくない。
実装方法について説明する。
まずN=2のときは数が被ってしまうので、サンプルケース通りに答えておこう。
minをまず確定するが、(x+y)%2==0の所にminを入れていく。
斜めに素数を割り当てていくというのを実装するにはx+y,x-yを使うといい。
x+yで/の向きの斜めを特定できる。x-yで\の向きの斜めを特定できる。
x+y,x-y共に偶数であるので、2で割って圧縮しよう。
u = (x+y)/2
v = (x-y)/2
これで良さそうだが、このままだとvが-N/2からN/2まで取りうるので、N/2を足して0以上にしておこう。
(下の解法では一応、ちゃんと0以上になるように+1している)
uもvも最大500通りあるので、素数を1000個ほど用意して、それぞれ割り当てる。
「vp[i] := i番目の素数」とすると、uにはvp[u]、vにはvp[1010-v]を割り当てることにする。
1010は適当です。
これで後は、かけて入れるだけ。
maxは周りのlcmを取るだけ。
特に注意点なし。
int N; ll ans[505][505]; //--------------------------------------------------------------------------------------------------- void _main() { auto vp = makePrimes(51010); cin >> N; if (N == 2) { printf("4 7\n23 10\n"); return; } rep(y, 0, N) rep(x, 0, N) if ((x + y) % 2 == 0) { int u = (x + y) / 2; int v = (x - y) / 2 + N / 2 + 1; ans[y][x] = 1LL * vp[u] * vp[1010 - v]; } rep(y, 0, N) rep(x, 0, N) if ((x + y) % 2 == 1) { ll c = 1; if (0 <= y - 1) c = lcm(c, ans[y - 1][x]); if (y + 1 < N) c = lcm(c, ans[y + 1][x]); if (0 <= x - 1) c = lcm(c, ans[y][x - 1]); if (x + 1 < N) c = lcm(c, ans[y][x + 1]); ans[y][x] = c + 1; } rep(y, 0, N) { rep(x, 0, N) { if (x) printf(" "); printf("%lld", ans[y][x]); } printf("\n"); } }