C - Board Moves

問題

https://codeforces.com/contest/1353/problem/C (新しいタブで開く)

問題文

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

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

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

制約

• $1 \le t \le 200$
• $1 \le n \le 5 \times 10^5$
• $n$ の総和は $5 \times 10^5$ を超えない

サンプル

3
1
5
499993

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$ 。

コード

https://codeforces.com/contest/1353/submission/127017674 (新しいタブで開く)

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