CF Round #642 C - Board Moves


Tags:cpcodeforcesdiv3math

問題

https://codeforces.com/contest/1353/problem/C

問題文

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

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

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

制約

  • 1t2001 \le t \le 200
  • 1n5×1051 \le n \le 5 \times 10^5
  • nn の総和は 5×1055 \times 10^5 を超えない

サンプル

3
1
5
499993
0
40
41664916690999888

考察

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

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

よって答えは、 i=1n12i8i\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;
}