A. Most Unstable Array (Codeforces Round #62 Div. 3)

問題

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

問題概要

2つの整数n, mが与えられる。

負でない整数から構成された長さn、かつ隣接する各項の差の絶対値の合計が最大になるように配列aを作成した場合の、隣接する各項の差の絶対値の合計を答えよ。

コンテスト中の考察

サンブルの3番目で解答例で挙げられている[0,2,0,3,0]という配列のように、mを均等に割り振って周りに0を配置するのでよさそうに思いました。nが偶数の時は特に最後の一つの項は自動的に0としてしまって大丈夫そうです。（<-ここでもうちょっと考えると、より真実に近づけるのだが、本番ではそれができませんでした。）

なお、nが1のときは、[m]という配列しか作りようがなく、もちろん隣り合う項目がそもそも存在しませんので、答えは0となります。

また、nが2のときは、[m, 0]という配列がもっとも効率がよく、答えはmです。mを分割してしまうと差が減るのは明らかです。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        if (n == 1) {
            cout << 0 << endl;
            continue;
        } else if (n == 2) {
            cout << m << endl;
            continue;
        }
        if (n % 2 == 0) n--;
        int l = n / 2;
        int r = m % l;
        int p = m / l;
        cout << p * l * 2 + r * 2 << endl;
    }
}

真実

実は、mを分割する必要がそもそもなく、[0,m,0,0,...,0]と、してしまっていいのでした。

なので、答えは、n=1のとき0、n=2のときm、n>2のとき2mとなります。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        if (n == 1) {
            cout << 0 << endl;
            continue;
        } else if (n == 2) {
            cout << m << endl;
            continue;
        }
        cout << m * 2 << endl;
    }
}