Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

【ABC140-F Many Slimes】multisetがほしい

ABC140-Eではsorted setがないから解けなかった。

www.rustforbeginners.com

今回の問題は、Rustがそもそもmultisetがないから死ぬという問題。まぁ、仮にsorted setがあればあとは別途カウンタを持って出来るような気はするが。いずれにしろ、コンパイラバージョンの更新が待ち遠しい。

F - Many Slimes

ABC140はセット回だったということで。

問題

数字が一つある。こいつが自分より小さい数字を一つ生成する。こうして出来た2つの数字は次のターンにそれぞれ、自分より小さな数字を生成する。こうやって、現世代が次の世代を劣化単為生殖していく。

N回ターンを繰り返したあと、数字の個数は2Nである。今、長さ2Nの数列Sが与えられたとき、これを作ることは可能か?

制約: N<=18, Si<=109

方針

ある世代の人をルートとする木はすべて同じ形となる。従って、各世代ごとに貪欲的に最大の数字を入れていけばよい。

これは、multiset(数字の重複ありのsortedなset)を使うと素直に実装することが出来る。

実装

配列を使って強引に攻めたが、無理だった。二分探索をしたあとにsの要素を削除するところが配列の長さ分かかるため、TLEする。(しかし3つしかTLEしなかったが)

もしsを最初にmultisetに突っ込んでよいならば、二分探索は同じオーダだが、削除はlogに落ちるので、たぶん通る。

fn solve() {
    input!{
        N:usize,
        s:[i64;1<<N],
    }
    let mut s=s;
    s.sort();

    let mut parents=vec![s.pop().unwrap()];
    // dbg!(&s,&parents);

    // M=1<<N
    // O(logM)
    'outer: loop {
        let mut new_parents = vec![];
        // O(M)
        for &par in &parents {
            if s.is_empty() {
                break 'outer;
            }
            // dbg!(&s);
            let res = {
                let mut bs = BinarySearch {
                    p: |i:usize| {
                        s[i]>=par
                    },
                    lower:0,
                    upper:s.len()-1,
                };
                bs.search()
            };
            // dbg!(res);
            if res.0.is_none() {
                println!("No");
                return;
            } else {
                // needs shifting 
                let x = s.remove(res.0.unwrap());
                new_parents.push(x);
            }
        }
        parents.append(&mut new_parents);
        // O(MlogM)
        parents.sort();
        parents.reverse();
    }

    println!("Yes");
}

考察

生殖は悪い。