Rustコトハジメ

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

ABC138 反省会

最低限の4完はしたが、これはEとれたと思う。なぜか通らなかった。本当に辛い。今日含めた4回のABCのうち一回は5完するという目標を立てていて、いきなり達成かと思ったが、そううまく行かなかった。

AtCoder Beginner Contest 138 - AtCoder

D

最初に各ノードの値をaccして、問い合わせを遡ればO(logN)だろと勝手読みしたが、木が一直線のケースを想定していなかった。

しかし、全部TLEだったので、入力されたエッジの向きが親子順になってることは確かめられたため、BFSで親から伝搬していく方式に変更して終了。

もしエッジの向きが親子順出なかった場合にはグラフを構成してからBFSでルートから辿ろうと思ってた。5分以上かかると思うので損得を考えて出してしまったという感じ。

E

長さが10の百乗みたいなふざけたケースは、存在しないか、存在する場合は終端を調べるまでもなく存在するみたいなケースが多いと思う。前にも見た気がする。

サンプルは通ったし、テストケースもあらかた通ったので勝ったかと思ったが謎。

方針としては、たぶん想定だと思うけど、まずSの中の分布を調べて、Tの文字を先頭から一つずつ探していく。トータルではO(len(T))

どこをどう間違ったのかわからないけど、最後の方の問題だけ失敗した。また32bitハメかと思ったが、accum_repeatをusizeにしてもだめなので、もっと本質的なところで失敗してそう。

fn solve() {
    input! {
        S: chars,
        T: chars,
    }
    let mut accum = vec![vec![]; 26];
    for i in 0..S.len() {
        let c = S[i];
        let k = c as usize - 'a' as usize;
        accum[k].push(i);
    }
    // dbg!(&accum);

    for i in 0..T.len() {
        let c = T[i];
        let k = c as usize - 'a' as usize;
        if accum[k].len() == 0 {
            println!("-1");
            return
        }
    }

    let M = T.len();
    let mut at = 0;
    let mut accum_repeat: usize = 0;
    let mut index = vec![0 as usize; 26];
    let mut last = None;
    while at < M {
        let c = T[at];
        // dbg!(c);
        let k = c as usize - 'a' as usize;
        // 長さ0はありえない
        // もう見つからん
        if index[k] >= accum[k].len() {
            last = None;
            index = vec![0;26];
            accum_repeat += 1;
            continue;
        }
        // 前に見つかった
        if last.is_some() && accum[k][index[k]] < last.unwrap() {
            last = None;
            index = vec![0;26];
            accum_repeat += 1;
            continue;
        }
        last = Some(accum[k][index[k]]);
        // dbg!(last);
        index[k] += 1;
        at += 1;
    }
    // dbg!(accum_repeat);
    // dbg!(last);

    let la: usize = if last.is_some() {
        last.unwrap() + 1
    } else { 0 };
    println!("{}", accum_repeat * S.len() + la);
}

なぜ間違っているか。わかった

おれのアルゴリズムでは、indexというのを使ってある文字についてのオフセットを順にたどっていくことを想定していますが、これが間違っています。

なぜならば、例えばabaと探すときに、aのオフセットが[2,4]でbのオフセットが[5]だとします。おれのアルゴリズムでは、bまでは探し出せますが、aの2番目を見た時に4で、最後に探した5より小さいため、次のラウンドに回ってしまいます。

正確にはここでは二分探索する必要がありました。前は二分探索出来ないものを二分探索しようとしましたが、今回は二分探索すべきところで二分探索しませんでした。

また5完には実力が足りていなかったと思います。

F

直感的に、

11xxと1100

のような場合のみ成立かと思った。こういうのを数えればいいだけ?xor系はよく出るけど、かなり既視感がある。