AtCoder ABC136D (Rust)

問題

D - Gathering Children

• 移動回数が十分に大きいので、"LR"または"RL"の並びのところで行ったり来たりを繰り返すことになります
• 移動回数は偶数なので、距離の偶奇で場合分けします

回答

use itertools::Itertools;
use proconio::{input, marker::Chars};

fn main() {
    input! {
        S:Chars
    }

    // S[i]がRの場合は一番近いL、Lの場合は一番近いRの位置
    let mut pos_lr: Vec<usize> = vec![0; S.len()];

    //まずS[i]がLの場合の一番近いRの位置を、左から入れていく
    let mut pr = 0;
    for i in 0..S.len() {
        if S[i] == 'R' {
            pr = i;
        } else {
            pos_lr[i] = pr;
        }
    }

    //次にS[i]がRの場合の一番近いLの位置を、右から入れていく
    let mut pl = S.len() - 1;
    for i in (0..S.len()).rev() {
        if S[i] == 'L' {
            pl = i;
        } else {
            pos_lr[i] = pl;
        }
    }

    let mut ans: Vec<usize> = vec![0; S.len()];
    for i in 0..S.len() {
        if S[i] == 'L' {
            //一番近いRの位置
            let pos = pos_lr[i];
            //移動回数は偶数なので、距離の偶奇で場合分け
            if (i - pos) % 2 == 0 {
                //Rの位置にある
                ans[pos] += 1;
            } else {
                //一つ手前のLの位置にある
                ans[pos + 1] += 1;
            }
        } else {
            //一番近いLの位置
            let pos = pos_lr[i];
            //移動回数は偶数なので、距離の偶奇で場合分け
            if (pos - i) % 2 == 0 {
                //Lの位置にある
                ans[pos] += 1;
            } else {
                //一つ手前のRの位置にある
                ans[pos - 1] += 1;
            }
        }
    }
    println!("{}", ans.iter().join(" "))
}

メモ

解説では、

実装では、文字列を連続した文字ごとに分解する (例えば “AABCCC” を (‘A’, 2), (‘B’, 1), (‘C’, 3) のよ
うに分解する) ランレングス圧縮のライブラリがあると便利です。

と書いてありました。