Rustコトハジメ

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

ABC140 反省会

AtCoder Beginner Contest 140 - AtCoder

4完。今回の4完はむしろよくやった方。

この前は5完まで22秒足りなかったが、今回は1分前に4完の解法を提出した。Dが全くわからなくて本当にやばかった。実際難しかったようである。

毎日過去問埋めをやっており、少し疲れてる感じはある。が、やばいなりにも最終的には通したことに成長は感じるので、このままやります。

D

問題文からライツアウトだと思った。が、結果としては違った。ただの貪欲。

こういうタイプの問題で、RLRLLみたいなところで切ったりというパターンの問題は見たことがある。(たぶんRITZのコンテストだった気がする)例えばこの場合だと、...L RLRL L...と切って、RLRLを反転させてLLRLRRにして、次にRLを反転させるとLLLRRRになるよねみたいな話だったような感じがする。これではない。

なんとなく、LRを同時に含んで反転させるのは意味がなさそうというのは直感的にわかって、LだけかRだけかを選んで反転させていくという方針にした。例えばプライオリティキューを使って影響度の大きいやつからフリップかとか、ごちゃごちゃ考えているうちに時間が過ぎていき、わからなくなり、賭けに出てEに行ったが、これもわからず。

結局、端っこのやつはフリップしたとして損得が+1でしかなく、中間のやつが+2あるということがわかった。例えば、LLRをRRRにしても1から2に上がるだけだが、LRLをLLLにすると0が2になる。

これに気づくと、最初がLの場合は、その次のRから貪欲にLに書き換えていけばよいということがわかる。だが、これに気づいた時が残り8分だった。

手が震えながら書いたコードをご鑑賞ください。

fn solve() {
    input!{
        N:usize,K:usize,
        S:chars,
    }
    let mut s=S.clone();
    let mut rlc=run_length_compression(&s);
    if rlc.len()==1{
        println!("{}",rlc[0].1-1);
        return;
    }
    // dbg!(&rlc);
    let fi=rlc[0].0;
    let mut k=K;
    for i in 0..rlc.len() {
        if rlc[i].0 != fi {
            rlc[i].0 = fi;
            k-=1;
            if k==0 {
                break;
            }
        }
    }
    // dbg!(&rlc);
    let mut acc=('A',0);
    let mut vv=vec![];
    for i in 0..rlc.len() {
        let c=rlc[i].0;
        if c!=acc.0 {
            vv.push(acc);
            acc=rlc[i];
        } else {
            acc=(acc.0,acc.1+rlc[i].1)
        }
    }
    vv.push(acc);
    vv.remove(0);
    let mut acc =0;
    for v in vv {
        acc+=v.1-1;
    }
    println!("{}",acc)
}