門松グラフ [yukicoder No.630]

https://yukicoder.me/problems/no/630

解法

https://yukicoder.me/submissions/228058

ある一つの事実だけに気付くとあとは実装問題となる。
「2部グラフを構築し、1つのグループには半分より小さい数、もう一方のグループには半分より大きい数を割り当てる」
このグラフを構築すればいい。
なぜそうなるかは公式解説が詳しい。
構築問題の方針の1つとして、こういうハッキリとした方針を見つけるというのがある。
なるべく簡潔で十分そうな性質を探そう。
　
b = N / 2
a = N - b
として2つのグループに分ける。
　
すると、構築できない条件は

• M＜N-1 : 連結にならない
• a*b＜M : 二部グラフを壊さないようにおける辺の最大数を超えてしまう

のどちらかを満たす場合である。どちらかを満たすならNO
a*bはintの計算範囲を越える可能性があるのでlong longで計算しよう。
　
奇数番目の頂点がグループAで個数a, 偶数番目の頂点がグループBで個数b
グループAは半分より小さい数をいれて、グループBは半分より大きい数を入れておこう。
　
まずは、連結させる必要があるので、隣り合う頂点間に辺を貼ろう。
あとは、グループAとグループBの任意の頂点間に辺を貼りまくればいい。
O(ab)はTLEするが、M辺だけ貼ったら処理を終了するようにすればO(M)で済むので間に合う。

int N, M, A[101010];
vector<pair<int, int>> ans;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;

    int b = N / 2;
    int a = N - b;

    if (M < N - 1 or 1LL * a*b < M) {
        printf("NO\n");
        return;
    }

    int c = 1;
    rep(i, 0, a) A[i * 2] = c, c++;
    rep(i, 0, b) A[i * 2 + 1] = c, c++;

    // 最低限連結させる
    rep(i, 0, N - 1) ans.push_back({ i, i + 1 });
    M -= N - 1;

    rep(i, 0, a) {
        if (M == 0) break;
        rep(j, 0, b) {
            int aa = i * 2;
            int bb = j * 2 + 1;
            if (abs(aa - bb) <= 1) continue;
            ans.push_back({ aa, bb });
            M--;
            if (M == 0) break;
        }
    }

    printf("YES\n");
    rep(i, 0, N) {
        if (i) printf(" ");
        printf("%d", A[i]);
    }
    printf("\n");
    fore(p, ans) printf("%d %d\n", p.first + 1, p.second + 1);
}