A - Most Unstable Array

cpcodeforcesdiv3greedyconstructive

最終更新日

問題

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

問題文

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

制約

サンプル

5
1 100
2 2
5 5
2 1000000000
1000000000 1000000000
0
2
10
1000000000
2000000000

考察

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

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

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

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

公式解説だと a=[0,m,0,,0]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;
  }
}