AtCoder AGC 035 C - Skolem XOR Tree (Rust) - あるエンジニアのAtCoder奮闘記

irisruneです。Rust第一回ですが、余りにも茨の道すぎて早くも最終回が近い予感がしています。

前置き

Rustは入力がかなり難解なので下記サイトよりマクロを拝借しております。~~中身はほとんど理解できていません。~~本ブログ上では記述を省略します。

問題

本ブログ初の700点問題です。ある程度手計算で試すと最近の500点くらいに感じられました。

fn main() {
    input!{
        n: usize
    }
    let mut m = 1;
    while m <= n {
        if m == n {
            println!("No");
            return;
        }
        m *= 2;
    }
    println!("Yes");
    m = 2;
    while m < n {
        println!("{} {}", 1, m);
        println!("{} {}", 1, m + 1);
        println!("{} {}", m, m + n + 1);
        println!("{} {}", m + 1, m + n);
        m += 2;
    }

    println!("{} {}", n + 1, n + 3);

    if n % 2 == 0 {
        m = n;
        let mut e = 0;
        while m > 1 {
            m /= 2;
            e += 1;
        }
        println!("{} {}", n, 2usize.pow(e));
        println!("{} {}", n * 2, n + 1 - 2usize.pow(e));
    }
}

図がないと説明が難しいので、以下では公式解説を見ていることを前提とします。まず、 $N$ が2のべき数（2のべき乗で表される数）の場合は条件を満たす木は存在しません。なぜなら、重みが $2^e$ より小さい数同士の排他的論理和は必ず $2^e$ より小さくなるためです。

次に、 $N$ が3以上の奇数の場合について考えます。まず、 $N=3$ の場合は入出力例1のように条件を満たす木を構成することができます。ここで頂点の重みについてのみ考えると公式解説の図（の一部）になります。

更に $N=5$ に増やした場合について考えると、木に対し重みが4,5の頂点を2つずつ追加することとなります。ここで端点でない重み1の頂点に対し、公式解説の図のように頂点を接続することで条件を満たす木を構成することができます。これは、整数 $M$ に対して $2M xor (2M+1) = 1$ となることから証明できます。

あとは同様の操作により、 $N=7,9,\ldots$ に対しても条件を満たす木を構成することができます。

最後に $N$ が（2のべき数でない）偶数の場合についてですが、重み1の頂点と重み $2,3,\ldots,N-1$ の頂点が隣接していることと、（ $N$ が2のべき数でないとき） $A xor B=A+B=N$ となる2整数を用いて $A xor 1 xor (B+1) = N$ となることから条件を満たす木を構成することができます。具体的な手順としては、 $N$ より小さい最大の2のべき数を $A$ とおき、重み1の頂点に接続している重み $A,B+1$ の頂点それぞれに重み $N$ の頂点を接続すればよいです。