Rustコトハジメ

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

ABC139 反省会

本当に最悪・・・。

EでN3の実装をしてることに気づいて、色々考えたあげくN2くらいに落とせることはわかったんだけど、実装がうまく出来なくて

f:id:akiradeveloper529:20190901225152p:plain

終了を22秒過ぎてから提出したものが通ってしまった。

というわけで今回も4完です。伸びてはいるので、次もがんばります。

まぁでも悲しいは悲しい。寝れるだろうか。

C

意外とこれに手こずった。

シミュレーションしても出来るだろうけど、境界の扱いとかでミスりそうな気がして実装をどうしようか迷った。

最終的に、隣合うi,i+1の低くなるかどうかを計算してしまい、最後に番兵のfalseをつけたものの中で最長のtrueを探すという誤りにくい実装を選択した。

fn solve() {
    input!{
        N:usize,
        H:[usize;N]
    }

    let mut ok=vec![false;N]; // ラストのはガード
    for i in 0..N-1 {
        ok[i]=H[i+1]<=H[i];
    }
    // dbg!(&ok);

    let mut maxv=0;
    let mut k=0;
    for i in 0..N {
        if ok[i] {
            k+=1;
        }
        else if !ok[i] {
            maxv=max(maxv,k);
            k=0;
        }
    }

    println!("{}",maxv);
}

D

これは解法はすぐわかるけど、証明は出来なかった。

Nが109と大きいので、N(N-1)/2を愚直に計算するとオーバーフローするというのはこの前のコンテストで学んでいるので、今回はNの偶奇を判定して一発AC。

E

貪欲にシミュレーションするという方針にした。今取れるやつには他に選択肢がないから(例えば、1がある日に2と3のどちらかを相手出来るとかありえない)、常に最強で取っていけばよい。

本当に糞みたいな実装をするとN4になるはず。それで、「ある人にとってある人は何番目の相手ですか?」を保存することにした。しかしそれでも最悪でN3だった。

というのも、例えばだけど、N=4のケースで

234 134 124 143

とかだと、毎日1試合しか出来なくてN2日かかり、毎日Nループ回すとN3になる。

だから、Nループを回すのではなく、その時点で相手が決まってることにした。この処理は、マッチしたやつらからしか発生しないからトータルでN2回しか起こらない。従ってトータルでもN2となる。正確には、O(N2 logN)の実装をしているはず。

上に書いたように22秒遅れでACを逃し、糞がああああああああああああああ

fn solve() {
    input!{
        N:usize,
        A:[[usize;N-1];N],
    }

    // 0オリジンにする
    let mut a = vec![vec![0;N-1];N];
    for i in 0..N {
        for j in 0..N-1 {
            a[i][j]=A[i][j]-1;
        }
    }
    let mut matching = HashSet::new();
    for i in 0..N {
        let oppo=a[i][0];
        if a[oppo][0]==i {
            matching.insert(i);
            matching.insert(oppo);
        }
    }

    // 場所を探索するためのテーブル
    // p[i][j]=iくんがjくんと戦いたい順番
    let mut p = vec![];
    for i in 0..N {
        let mut v = vec![0;N];
        for j in 0..N-1 {
            v[a[i][j]]=j;
        }
        p.push(v);
    }
    // 次に戦うやつを管理
    let mut head = vec![0;N];

    // シミュレーションする
    // 貪欲でよい
    let mut days=0;
    loop {
        let mut consume=vec![];
        for &i in &matching {
            if !(head[i]<N-1) { continue; }
            // 次の相手
            let oppo=a[i][head[i]];

            if !(i<oppo) { continue; }

            if !(head[oppo]<N-1) { continue; }

            // 今oppoが欲してるものがiならばマッチ
            if p[oppo][i]==head[oppo] {
                consume.push(i);
                consume.push(oppo);
            }
        }
        matching=HashSet::new();
        if consume.len() > 0 {
            for &i in &consume {
                head[i]+=1;
            }
            for &i in &consume {
                if !(head[i]<N-1) { continue; }
                let oppo=a[i][head[i]];
                if !(head[oppo]<N-1) { continue; }
                if a[oppo][head[oppo]]==i {
                    matching.insert(oppo);
                    matching.insert(i);
                }
            }
            days+=1;
        } else {
            break;
        }
    }

    let mut complt=true;
    for i in 0..N {
        if head[i]<N-1 {
            complt=false;
        }
    }

    if complt {
        println!("{}",days);
    } else {
        println!("-1");
    }
}