Rustコトハジメ

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

ABC136 反省会

AtCoder Beginner Contest 136 - AtCoder

最悪すぎる。Dで発狂して終わってしまった。今週も4完以上するという目標を失敗してしまい、絶望している。

C

おれは最初の要素だけは低くすることが無条件で良いので低くして、あとはindex=1から順に、広義単調増加になりやすいように努力するという方針をとった。

D

ひどすぎる。

Rのやつは右にある直近のLを見つける、そしたらあとはRLの間を行き来するだけ。というのはすぐに分かったので実装を始めたが、その方針が狂ってたためコンテスト中に精神が壊れてしまった。

おれの方針としては、Lの右のRを二分探索で見つけるというものだったが、冷静になってみると、LとRは入り混じってるのだから二分探索が使えるわけがないということは明らかで、正しくは前処理をして、各インデックスから直近のLの位置をO(1)で見つけられるようにする必要があるのだが、実装をしてみたものの答えが間違ってるためここでおれは二分探索のライブラリの実装が間違ってると考えて、なんでテストをちゃんとしないんだ、なんで自分はこんなに愚かなんだとコンテスト中に発狂して、どうにかして二分探索ライブラリを直そうとしたが、壊れてないんだから直せるわけもなく、残り10分になって、二分探索ライブラリを使うのではなく、前処理方式で再実装しようということにしたが、心がもうカミーユ状態で、そのまま落ちてしまった。

とりあえず、二分探索もそうだが、01列を考えてなんかするということはたまにあるのでライブラリ化してリベンジしておいたが、本当に悔やまれる。

最近二分探索のことばかり考えていたので、てっきり二分探索だと早合点してしまった。

fn solve() {
    input! {
        S: chars
    }
    let mut ft = vec![]; // R->false, L->true
    let N = S.len();
    for i in 0..N {
        let b = if S[i] == 'R' {
            false
        } else { true };
        ft.push(b);
    }
    // dbg!(&ft);

    let mut state = vec![0; N];
    let fts = FTSearch::new(ft.clone());
    for i in 0..N {
        if S[i] == 'R' {
            let j = fts.t_search(i);
            let dist = j - i;
            if dist % 2 == 0 {
                state[j] += 1;
            } else {
                state[j-1] += 1;
            }
        } else {
            let j = fts.f_search(i).unwrap();
            let dist = i - j;
            if dist % 2 == 0 {
                state[j] += 1;
            } else {
                state[j+1] += 1;
            }
        }
    }
    // dbg!(&state);

    let tmp: Vec<String> = state.iter().map(|x| x.to_string()).collect();
    println!("{}", tmp.connect(" "));
}
struct FTSearch {
    orig: Vec<bool>,
    f_search: Vec<Option<usize>>,
    t_search: Vec<usize>,
}
impl FTSearch {
    fn new(xs: Vec<bool>) -> Self {
        let N = xs.len();
        let mut f_search = vec![None; N];
        let mut f_i = None;
        for i in 0..N {
            if xs[i] == false {
                f_i = Some(i);
            }
            f_search[i] = f_i;
        }
        let mut t_search = vec![N; N];
        let mut t_i = N;
        for i in (0..N).rev() {
            if xs[i] == true {
                t_i = i;
            }
            t_search[i] = t_i;
        }
        FTSearch {
            orig: xs,
            f_search: f_search,
            t_search: t_search,
        }
    }
    fn f_search(&self, i: usize) -> Option<usize> {
        self.f_search[i]
    }
    fn t_search(&self, i: usize) -> usize {
        self.t_search[i]
    }
}

この問題の範囲なら、ランレングス圧縮を使ってやるというのもエレガントだとは思う。別解の方はあまり理解出来ない。

まぁ将来的なことを考えると、今回二分探索の成立条件で痛い目にあったことで得になる意味もあると思うので、レートが上がってから死ぬよりは良かったとポジティブに考えることにして、また5完を目指してがんばります。