けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ ???? Stick Combination (KUPC 2020 D)

面白かった

問題概要

 1, 3, 5, \dots, 2N-1 という  N 個の整数がある。これらを 2 個以上のグループに分ける。各グループの整数の総和が互いに等しくなるようにグループ分けすることが可能かどうかを判定し、可能ならば具体例を構築せよ。

制約

  •  2 \le N \le 10^{5}

考えたこと

こういうのはいろんな  N で試していくのがよさそう。

  •  N = 2 はダメ
  •  N = 3 もダメ
  •  N = 4 は (1, 7), (3, 5) で OK
  •  N = 5 はダメ
  •  N = 6 は (1, 11), (3, 9), (5, 7) で OK

この辺りでとりあえず

  • 2 以外の偶数は OK
  • 素数はダメ

といったことが見えてきた。2 以外の偶数は、(2i+1, 2N-2i-1) を並べれば OK。素数は、仮に可能だとすると、グループの個数を  M、各グループの総和を  S とすると、

 N^{2} = SM

となる。 N素数なので  M \ge 2 だと  S = N M = N しかありえないけど、これもダメ。よって素数はダメ。

素数でない奇数のとき

多分いろんな方法があるけど、 N = 3n と表せる場合に帰着させて考えることにした。 N が 3 の倍数でなかったとしても、 N = pq としたとき、

  • まず最初の  3q 個を 3 個ずつの  q グループに分ける。
  • 残りの  (p-3)q 個を  q グループに振り分けていく

という風にできる。よって、 N = 3n の場合ができれば OK。これは色々手を動かしていると、できた (下のコード参照)!

コード

#include <bits/stdc++.h>
using namespace std;

bool is_prime(long long n) {
    if (n <= 1) return false;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p == 0) return false;
    }
    return true;
}

void print(vector<vector<int>> res) {
    cout << res.size() << endl;
    for (auto v : res) {
        sort(v.begin(), v.end());
        cout << v.size();
        for (auto p : v) cout << " " << p;
        cout << endl;
    }
}

vector<vector<int>> sub(int W) {
    vector<vector<int>> res;
    int sum = W * 9;
    for (int i = 0; i < W; ++i) {
        int a = i*2 + 1;
        int j = (i + W/2) % W;
        int b = W*2+1 + j*2;
        int c = sum - a - b;
        res.push_back(vector<int>({a, b, c}));
    }
    return res;
}

int num(int h, int w, int W) {
    int id = h * W + w;
    return id * 2 + 1;
}

bool check(vector<vector<int>> res) {
    set<long long> se;
    for (auto v : res) {
        long long sum = 0;
        for (auto p : v) sum += p;
        se.insert(sum);
    }
    return se.size() == 1;
}

void solve(int N) {
    if (is_prime(N)) {
        cout << "impossible" << endl;
        return;
    }

    long long H = 3, W = 1;
    for (; H * H <= N; ++H) {
        if (N % H == 0) {
            W = N / H;
            break;
        }
    }
    vector<vector<int>> res;
    if (N % 2 == 0) {
        for (int i = 1, j = N*2-1; i <= j; i += 2, j -= 2) {
            res.push_back(vector<int>({i, j}));
        }
        print(res);
        return;
    }

    res = sub(W);
    int width = (H - 3) / 2;
    for (int i = 0; i < W; ++i) {
        for (int j = 0; j < width; ++j) {
            int h = j + 3;
            int w = i;
            res[i].push_back(num(h, w, W));
        }
        for (int j = 0; j < width; ++j) {
            int h = j + width + 3;
            int w = W - i - 1;
            res[i].push_back(num(h, w, W));
        }
    }
    print(res);
}

int main() {
    int N;
    while (cin >> N) solve(N);
}