E869120 and Constructing Array 4 [yukicoder No.690] - はまやんはまやんはまやん

考察

1. N≦32でK≦10^9なので、明らかに2の累乗でやっていくやつ
2. 実験して2乗を足せる構造を作り出す

解法

構築のよくある方針として「2の累乗で表現していく」という方針がある。
例えば24を達成したいとして、25=16+8+1と表現できるので、2^4,2^3,2^0を構築すればいい。みたいな方針。
なので、2の累乗を独立に作り出せるグラフを実験で探しだそう。
　
結構Nの制約が厳しめなので、無駄な構造は作れない。
最も多く通り数を作れるグラフは完全グラフみたいなグラフなので、それをベースに考えていこう。
以下の様なグラフをまず作る。

1≦i＜j≦nについてi→jで辺を張る
1≦i≦nについてi→32で辺を張る

　
すると2^(n-1)通り作り出すことができる。
よって2^(n-1)がK以下でnが最大のものを特定して作り出そう。
このグラフにおいて、頂点n+1を追加で作り、n+1→32の辺を張っておく。
この頂点に辺を適切に追加すると2の累乗を独立に足していくことができる。
2≦i≦nについてi→n+1に辺を張ると、2^(i-2)を足していくことが出来る。
これは1→???→i→n+1→32という経路を追加することができるが、???の部分は2～i-1の頂点を取るか取らないかの全ての部分集合を取りうる。
よって2^(i-2)通り存在する。
この辺を張る処理は全て独立に行えるので、iが大きい順から貪欲に採用していけばいい。

int K;
int d[31];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> K;

    if (K == 0) {
        printf("2 0\n");
        return;
    }

    d[0] = 1;
    rep(i, 1, 31) d[i] = d[i - 1] * 2;

    int n = -1;
    rep(i, 0, 31) if (d[i] <= K) n = i;
    n++;

    vector<pair<int, int>> ans;
    rep(i, 0, n) rep(j, 0, n) if(i < j) ans.push_back({ i + 1, j + 1 });
    rep(i, 0, n) ans.push_back({ i + 1, 32 });

    K -= d[n - 1];

    if (K) {
        rrep(dgt, n, 2) {
            if (d[dgt - 2] <= K) {
                ans.push_back({ dgt, n + 1 });
                K -= d[dgt - 2];
            }
        }

        ans.push_back({ n + 1, 32 });
    }

    int m = ans.size();
    printf("32 %d\n", m);
    rep(i, 0, m) printf("%d %d\n", ans[i].first, ans[i].second);
}