Tenka1 2018 D - Crossing (緑色, 500 点)

C 問題もそうだったけど、C も D も証明した状態で提出していた。
ノーペナで行けたのはよかったけど、でもスピード的には、証明できていなくてもえいやっと提出した方が早いのかもしれない。

問題へのリンク

また類題として以下の問題がある:

• CODE FESTIVAL 2017 F - Distribute Numbers

問題概要

整数 N が与えられます。{1, 2, ..., N} の部分集合の組 (S1, S2, ..., Sk) であって、以下の条件を満たすものが存在するか判定し、 存在する場合はひとつ構成してください。

• 1, 2, ..., N のうちどの整数も、S1, S2, ..., Sk のうちちょうど 2 つに含まれる
• S1, S2,. .., Sk のうちどの 2 つの集合をとっても、それらに共通して含まれる要素はちょうど 1 つである

制約

• 2 <= N <= 10⁵

考えたこと

N = 3 の場合のサンプルを見る。ふむふむ。

N = 5 の場合を簡単に考えてみる。まず部分集合の大きさが 2 だと絶対できなさそう。{1, 2} と {3, 4} みたいなのは交わりがないとダメなので片方しか含められない。そうすると大きさが 2 で N 全体を被覆するのは無理そう。

そうすると大きさが 3 だとどうか？？
でも {1, 2, 3} と {1, 4, 5} をとるとそこから身動きが取れなくなった。ここまで来ると、N = 5 もできなさそうだと思った。

ここまでの考察からなんとなく思ったのは

• 部分集合の大きさを決めて考えるのがよいのではないか
• 部分集合の大きさを a と決めると、作れるような N は決まってしまうのではないか

ということだった。

部分集合の大きさがどれも等しくなること

まず、部分集合の大きさは一定でなければならならなそうである。

|S1| = a とすると、

• S2, S3, ..., はどれも S1 のうちの 1 個と交わる (それらを b2, b3, ... とする)
• b2, b3, ... は互いに異なる (もし被ったら、その値は 3 回以上登場することになってダメ)

ということから、実は部分集合は全部でちょうど a+1 回であることがわかる。つまり任意の i に対して |Si| = c とすると c = a+1 になるので、|Si| = a でなければならないことがわかる。

|Si| = a のときの N の値

S が全部で a+1 個なので、数字は全部で a(a+1) 個登場する。そして各数字が 2 回ずつ登場することから

N = a(a+1)/2

であることが確定する。

まとめ

結局、N は

• ある整数 a が存在して、N = a(a+1)/2

を満たさなければならないことがわかる。つまり N は三角数に限られる。逆に N が三角数のときは以下のように実際に構成できた:

これをそのままコードにした。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    long long N; cin >> N;
    long long K = 1;
    bool exist = false;
    for (K = 1; K <= N; ++K) {
        if (K * (K+1) / 2 == N) {
            exist = true;
            break;
        }
    }
        
    if (!exist) puts("No");
    else {
        puts("Yes");
        cout << K+1 << endl;
        vector<vector<long long> > res(K+1, vector<long long>());
        long long sum = 1;
        for (int k = K; k >= 1; --k) {
            for (int i = 0; i < k; ++i) {
                res[K-k].push_back(sum + i);
                res[K-k + i + 1].push_back(sum + i);
            }
            sum += k;
        }
            
        for (int i = 0; i < K+1; ++i) {
            cout << res[i].size();
            for (int j = 0; j < res[i].size(); ++j) cout << " " << res[i][j];
            cout << endl;
        }
    }
}

その後 TL を見て --- グラフを用いた議論

グラフで考えるとわかりやすい旨の記述を色々みた。

• S1, S2, ... を頂点とする完全グラフを考える
• {1, 2, ..., N} の各要素は、この完全グラフの各辺に対応する

ということから、グラフの頂点数を m とすると

• N = m(m-1)/2

に確定する (ここでの m は、僕の考察での a とは違うことに注意)。つまりグラフを用いた議論によっても、N が三角数であることが導かれる。