Subgraphs [SRM730 Div1 Med] - はまやんはまやんはまやん

https://community.topcoder.com/stat?c=problem_statement&pm=14817

ある数Kが与えられる。
以下の条件を満たすようにグラフを生成する。

頂点数Nは46個以下
自己辺、多重辺無し
x=[0,K*(K-1)/2]について、N個からK個取ってきた頂点集合の中の辺がx本であるような集合が存在する

グラフの隣接グラフと、x=[0,K*(K-1)/2]それぞれについて集合を答えよ

解法

ksunさんの解法が素晴らしい。
　
まず、K=23でのx=0,x=23*(23-1)/2の場合を考えてみよう。
K=23でx=0の場合は取ってきた頂点間に辺があっては行けない
K=23でx=23*(23-1)/2の場合は取ってきたどの頂点間にも辺が無ければいけない
つまり、K=23の場合は最大46頂点のうち、半分が互いに辺を持たず、半分が完全グラフになる必要がある。
この考察から、半分は完全グラフ、もう片方は互いに辺を持たず、その2つの集合間に何かしら辺を張る方針で考えていこう。
　
自分はここで詰まったが、ここからはksunさんの解法の解説しよう。
どのKであっても使用する無向グラフは同じである。
以下のルールで無向グラフを生成していく。
頂点[0,22]は完全グラフを作る。
頂点[23,45]の間には辺を張らない。
そして、

頂点0は頂点23
頂点1は頂点23,24
頂点2は頂点[23,25]
...
頂点22は頂点[23,35]

のように数を一つずつ増やした辺を作る。
　
次は集合の構築フェーズであるが、方針としては「頂点0か頂点23,頂点1か頂点24のように頂点iか頂点(i+23)のどちらかを選択して構築する」
このように構築すると、頂点iと頂点(i+23)の選択の場合に

頂点iを選択 → 辺の数が+iされる
頂点i+23を選択 → 辺の数は変化なし

のようになる。これは

頂点iは頂点[0,i)と頂点[23,i+23)の全ての頂点に繋がっているが、頂点i+23は頂点[0,i)と頂点[23,i+23)の全ての頂点につながっていない
頂点[0,i)と頂点[23,i+23)で選択させれている頂点の合計はi個である（どのペアでもどちらか選択されているため）

から言える。
あとは、構築でよくある大きい方から貪欲に取っていく戦略で構築すれば答え。

// ksun's fantastic solution!
int E[46][46];
struct Subgraphs {
    vector <string> findGroups(int k) {
        rep(i, 0, 46) rep(j, 0, 46) E[i][j] = 0;


        rep(i, 0, 46) rep(j, 0, i) {
            if (23 <= i and 23 <= j) continue;
            if (i < 23 and j < 23) E[i][j] = E[j][i] = 1;
            else {
                int c = i - 23;
                if (c <= j) E[i][j] = E[j][i] = 1;
            }
        }

        vector<string> ans;
        rep(i, 0, 46) {
            string s = "";
            rep(j, 0, 46) {
                if (E[i][j]) s += "1";
                else s += "0";
            }
            ans.push_back(s);
        }

        int tot = k * (k - 1) / 2;
        rep(i, 0, tot + 1) {
            string s = "";
            rep(j, 0, 46) s += "N";

            int cur = i;
            rrep(r, k - 1, 0) {
                if (r <= cur) {
                    cur -= r;
                    s[r] = 'Y';
                }
                else {
                    s[r + 23] = 'Y';
                }
            }
            ans.push_back(s);
        }

        return ans;
    }
};