CSES - Two Sets

問題

CSES - Two Sets

CSES - Two Sets

 

考察と解

１からｎまでの和はS = n * (n + 1) / 2で求められる。

Sが偶数の時のみ２つの集合に分けることができ、その元たちの和はS/2であることがわかる。

 

なので、最初にＳが偶数であるかどうかを確認する。

 

与えられた自然数で指定の和S/2を作るためには、

最大の元ｎから始まり、和に達するまで大きい元を順に足していけばいいので、

S/2＝ｎ＋(n-1)＋(n-2)＋…＋ｒ

と表すことができる。

 

使用できる最大の元より、和に到達するために必要な数値が少なければ、

その残りの数値をｒとすればいい。

 

残りの数値が０になる時を考えてコードを作成すると、次のようになる。

 

この問題では使用していない方の自然数も出力しなければならないので、

後で参照しやすいようにisUsedで記録している。

 

集合の大きさを数えなおしたくもないので、それもusedCountに記録している。

 

後はisUsedを見ながら出力すればいい。

 

コード

#include <iostream>
#include <vector>

using namespace std;

using ll = long long;

void solve(const ll& n)
{
    auto sum = n * (n + 1) / 2;
    if (1 == (sum % 2))
    {
        cout << "NO";
        return;
    }

    cout << "YES\n";

    auto total = sum / 2;
    auto max = n;
    int usedCount{ 0 };
    vector<bool> isUsed(n, false);

    while (max < total)
    {
        total -= max;
        max -= 1;
        isUsed[max] = true;
        usedCount += 1;
    }

    isUsed[total - 1] = true;
    usedCount += 1;

    cout << usedCount << '\n';
    for (int i = 0; i < n; ++i)
    {
        if (isUsed[i]) cout << i + 1 << ' ';
    }
    cout << '\n';

    cout << n - usedCount << '\n';
    for (int i = 0; i < n; ++i)
    {
        if (!isUsed[i]) cout << i + 1 << ' ';
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n;
    cin >> n;

    solve(n);

    return 0;
}

 

結果