Asa's Website

問題

奇数 $n$ に対して、 $n \times n$ のマス目を考える。
最初、それぞれのマスには 1 つのフィギュアがある。

以下の操作を最小で何回行えば、すべてのフィギュアを 1 マスに集められる？

ちょうど 1 つのフィギュアを選ぶ。
前後左右斜めの 8 マスのうち、どれかに移動させる。
すでにフィギュアのあるマスに移動させてもいいが、マス目の外には出せない。


0
40
41664916690999888

外側から内側にだんだん寄せていくのがよさそう。
あとは数学。

1 回の操作で真ん中に行けるのは 8 マスあるので $1 \cdot 8 = 8$ 回操作が必要、2 回の操作では 16 マスで 32 回操作、...、 $n$ 回の操作では $8n$ マス、を足していけばいい。
一番外側で $\frac{n-1}{2}$ 回の操作が必要。

よって答えは、 $\sum_{i=1}^{\frac{n-1}{2}} i \cdot 8i$ 。


void solve() {
  ll n;
  cin >> n;
  ll ans = 0;
  rep(i, n / 2 + 1) {
    ans += i * i * 8;
  }
  cout << ans << endl;
}