A - Most Unstable Array

問題

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

問題文

$n, m$ が与えられる。
長さ $n$ の非負整数の配列 $a$ であって、総和がちょうど $m$ であるもののうち、 $\sum_{i=1}^{n-1} |a_i - a_{i+1}|$ の最大値は？

制約

• $1 \le t \le 10^4$
• $1 \le n, m \le 10^9$

サンプル

5
1 100
2 2
5 5
2 1000000000
1000000000 1000000000

0
2
10
1000000000
2000000000

考察

$a = \left[ 0, x, 0, x, \cdots, 0 \right]$ としていくのがよさそう。

余りが出たら適当に足せばいいので、とりあえず $x$ は実数を許容しておいて、 $x \cdot \frac{n - 1}{2} = m$ つまり $x = \frac{2m}{n - 1}$ としておけばよさそう。
一番最後は $0$ になってほしいので $n-1$ にしておいた。

このとき、 $\sum_{i=1}^{n-1} |a_i - a_{i+1}| = \sum_{i=1}^{n-1} x = (n - 1) x = 2m$ 。なんかきれいにまとまった。

例外なのが $n = 1$ のときは明らかに $0$ 、 $n = 2$ のときは $a = \left[ 0, m \right]$ で $m$ 。

公式解説だと $a = \left[ 0, m, 0, \cdots, 0 \right]$ って書いてた。それでいいんかい

コード

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

void solve() {
  ll n, m;
  cin >> n >> m;
  if (n == 1) {
    cout << 0 << endl;
  }
  else if (n == 2) {
    cout << m << endl;
  }
  else {
    cout << 2 * m << endl;
  }
}