B. Balanced Array (Codeforces Round #636 Div. 3)

問題

https://codeforces.com/contest/1343/problem/B

問題概要

偶数nが与えられる。以下の条件を満たす長さnの数列を一つ構築せよ。なお、構築可能であるかどうかは保証されない。

• 前半のn/2個の要素は偶数である
• 後半のn/2個の要素は奇数である
• すべての要素はすべて相異なる正数である
• 前半のn/2個の要素の和と後半のn/2個の要素の和が等しくなる

考察

n/2が奇数となる場合、前半のn/2個の要素の和は偶数で後半のn/2個の要素の和は奇数となるので構築不可能です。

n/2が偶数となる場合は適当に構築します。

私は前半を2, 4, 6, ...., nと並べて後半を1, 3, 5, ...., n - 1 + n/2と並べました。機械的に1, 3, 5, ...., n - 1と並べた時点で、n/2だけ少ないので最後にn/2を足すことで調整します。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        if ((n / 2) % 2 == 1) {
            cout << "NO" << endl;
        } else {
            cout << "YES" << endl;
            for (int i = 1; i <= n / 2; i++) {
                cout << i * 2 << " ";
            }
            for (int i = 0; i < n / 2 - 1; i++) {
                cout << i * 2 + 1 << " ";
            }
            cout << n - 1 + (n / 2) << endl;
        }
    }
}

実は・・・

考え方自体は上の考察のとおりなのですが、実はn - 1 + n/2という式は立てておらず、ちょっと違う実装となっています。

Submission #77494353 - Codeforces

↑この実装、まずいところがあります。（この問題の制約だと最終的に答えは合うのですが）

お暇な方はどこがおかしいか見つけてみてください。