Rustコトハジメ

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

yukicoder contest 221 反省会

yukicoderのコンテストは2週間に一回くらい開催されている。AtCoderと違って、参加登録は必要なく、その時間になると勝手にコンテストが始まり、みんなおもむろに解き始める。

コンテストに慣れることで実力を出しやすくなるだろうから、今回からyukicoderコンテストにも積極的に参加していくことにした。

全体で5問。一応4問出したが2つしか通らなかった。105人中65番。どれも良い問題だったと思う。

871 かえるのうた (WA)

No.871 かえるのうた - yukicoder

問題

Xiにいるかえるが鳴くと、[Xi-Ai,Xi+Ai]にいるかえるが鳴く。これが伝搬していく。K番目のかえるが最初に鳴くとき、最終的に何匹のかえるが鳴くか?

方針

シミュレートすることにした。二分探索して、鳴いたかえるを塗りつぶしていく。これをKから上方向、下方向とやることにした。

実装

こんなコードを書いたが、4つ通らなかった。コードがモロに重複してるのは、bをミューテートするmutクロージャを定義してしまうと、whileループでb[i]をimmutable borrow出来ないから。

fn solve() {
    input!{
        N:usize,K:usize,
        X:[i64;N],
        A:[i64;N],
    }
    let mut b=vec![false;N];
    b[K-1]=true;
    let mut i=K-1;
    while b[i] {
        let lower = X[i]-A[i];
        let upper = X[i]+A[i];
        let k = X.lower_bound(&lower);
        for j in k..K {
            if b[j] { break; }
            b[j]=true;
        }
        let k = X.lower_bound(&(upper+1));
        for j in (K-1..k).rev() {
            if b[j] { break; }
            b[j]=true;
        }
        if i==N-1 { break; }
        i+=1;
    }
    let mut i=K-1;
    while b[i] {
        let lower = X[i]-A[i];
        let upper = X[i]+A[i];
        let k = X.lower_bound(&lower);
        for j in k..K {
            if b[j] { break; }
            b[j]=true;
        }
        let k = X.lower_bound(&(upper+1));
        for j in (K-1..k).rev() {
            if b[j] { break; }
            b[j]=true;
        }
        if i==0 { break; }
        i-=1;
    }

    let mut n=0;
    for i in 0..N{
        if b[i] {
            n+=1;
        }
    }
    println!("{}",n);
}

考察

何が間違ってるかというと、上方向に行ったあとに下方向で新しいかえるが鳴く可能性を無視している。実際に、whileループ文を2回繰り返すと、1つのテストケースを除いてすべて通るようになる。

それでもなぜ間違ってるかというと、2回繰り返したとしても、上方向と下方向でピンポンで新しいかえるが鳴く場合に対応出来ないからだ。

新しいかえるが現れなくなるまでループするとしても、それによってTLEする可能性はある(現実的には通ってしまうと思うが。実際に2回ではなく100回に増やしたら嘘解法でAC出来てしまった https://yukicoder.me/submissions/374412 )。

もしかしたら、DFSする方がいいのかも知れないと思った。あるかえるが鳴いた時に、範囲にあるかえるに対してエッジが飛ぶというグラフと見ることが出来るため。こうすると収束するまで探索してくれるはず。気が向いたら再実装してみます。

872 All Tree Path (AC)

No.872 All Tree Path - yukicoder

問題

重みつき木が与えられる。全ノード間の距離の総和を求めよ。

方針

ある辺で木を2つに切る。その時、木がN個とM個に分割されるとして、コストxMxNx2を足してあげればいい。まず、それぞれのノードの下(自分も含む)にノードが何個あるか深さ探索で数え上げる。その情報を使えばノードの上下関係は特定出来るから、あとはやるだけ。

873 バイナリやばいなり (WA)

No.873 バイナリ、ヤバいなり!w - yukicoder

問題

あるバイナリについて、同じ数字が並んだ時に分割して、それぞれの長さの二乗和をやばさと定義する。やばさがNのバイナリのうち、もっとも短いもののうち、辞書順最小のものを求めよ

方針

Nを作るのにもっとも短いバイナリ列と、その時の組成をDPによって計算する。

辞書順最小は、まず奇数長のものを小さい方から0|010|01010|のようにやっていくのが先頭の方に0が寄るから最善で、次に偶数長のものを小さい方から|1010|010101|のように繋いでいくのが最善。

サンプルは通ったが、3割くらいテストケースをしくった。TLEはしないと思っていたが、1つしてた。

実装

DP部分だけ。こういうかんじにしたが、間に合わない。方針がそもそも間違ってそう。Nが5乗なので、ぎり間に合うのではないかと思ったが。トータルで7.5乗なので無理なのかも知れない。loopの一番下でコピーしてるのも良くないかも。つけたした文字と、それを付け足す前のやつだけを記録していくことで、このコピー自体はなくすことが出来るが、それで間に合うかは不明。

    let mut dp = vec![(std::usize::MAX,vec![]);N+1];
    dp[0] = (0,vec![]);
    for i in 1..N+1 {
        let mut j=1;
        while j*j<=i {
            let l0 = dp[i-j*j].0;
            let mut l1=dp[i].0;
            if l0+j<l1 {
                let mut v = dp[i-j*j].1.clone();
                v.push(j);
                dp[i] = (l0+j,v);
            }
            j+=1;
        }
    }

考察

とりあえず、テストケースと照らし合わせてみたが、まず、辞書順最小を求める方法が間違ってるのと、DPのオーダーが大きいのか、ローカルでやってもTLEする。N10万くらいでだめそう。