Rustコトハジメ

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

【AOJ0603 電飾】ABC140-Dの類問

ABC140-DがDにしては難しく、類問があったらいいなと思いました。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0603

ここでも紹介しましたが改めて。

ライツアウト系の基本を学ぶ - Rustコトハジメ

問題

長さNの01列Aが与えられる。

010101のような列を交互列と呼ぶことにする。

Aの中の範囲を一回だけ反転させて、最長の交互列を作る。その長さを求めよ。

方針

例えば

1100101110

のような列を

(1)(10)(0101)(1)(10)

のようにグルーピングしたとします。

すると、例えば(10)をひっくり返すと、左右のやつとくっついて交互列を作ることが出来ます。

(1)(01)(0101)

こうすれば、最長というのは、連続した3つのグループの長さ和の最大値といえます。

実装

fn solve() {
    input!{
        N:usize,
        a:[usize;N],
    }
    let mut comp=vec![];
    let mut cur=0;
    for i in 0..N {
        cur+=1;
        if i<N-1 && a[i]==a[i+1] {
            comp.push(cur);
            cur=0;
        }
    }
    comp.push(cur);
    for _ in 0..3 {
        comp.push(0);
    }
    // dbg!(&comp);
    let mut maxv=0;
    for i in 0..comp.len()-2 {
        maxv=max(maxv,comp[i]+comp[i+1]+comp[i+2]);
    }
    println!("{}",maxv);
}

考察

ABC140-Dの想定解法では、不幸せな人の数を減らすという方針を紹介していますが、これもある意味、数字が連続した境界が不幸せと考えると同じようなことだと思いました。