Rustコトハジメ

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

【AGC008-B Contiguous Repainting】2つの範囲で実験すると気づく系

B - Contiguous Repainting

ライツアウト系のような感じ。似たような問題が多いのでまとめたい。

問題

長さNの数列が与えられる。要素は整数(負もありえる)。最初これらは白で埋められている。今、連続したK個を黒か白で塗りつぶすことが何度でも許される。この時、黒で塗りつぶされたマスの最大値を求めよ。

方針

こういう範囲をどうにかする系は、よくあるが、

  • 任意範囲
  • K固定
  • K以下

くらいがパターンとしてある。

いずれにしろまずは、2つを組み合わせてどうなるか観察してみたい。

例えば、

D - Flipping Signs

では、11を作ったあと、1つずらしてフリップさせて、101,1001,10001としていくことで、任意の2点に1を立てられることが可能であるという性質に気づく必要がある。

D - Handstand

は任意範囲のフリップだが、これは、「任意の範囲を1にすることが出来る」ということに気づく必要がある。これは、2つの範囲の重なった部分は、0になるからだ。この性質は初見殺しなためよく見る。

このように、2つの範囲を組み合わせると、何か任意のことが出来ることが出来るというのがあるあるの性質である。

ライツアウトの他にも、複合的なものを組み合わせると単位元のようなものが作れるという性質に気づく必要がある問題は多い。例えば、色々移動操作はあるが、組み合わせによっては1移動を作れるとか。

今回は、端っこの方については、2つの黒と白を1つずらしておくと、1つの黒を作れることに気づく必要がある。つまり、最終図では必ずK黒かK白が存在する。まずはそのような領域を決めてしまい、残りの部分で正の値だけをとる。

実装

範囲加算をSEGで実装した。Rustなら75ms。言語によっては累積和じゃないと間に合わないかも知れない。

fn solve() {
    input!{
        N:usize,K:usize,
        a:[i64;N]
    }

    let mut all_black_sum: SEG<SUM> = SEG::new(N);
    for i in 0..N {
        all_black_sum.update(i, a[i]);
    }

    let mut positive_sum: SEG<SUM> = SEG::new(N);
    for i in 0..N {
        if a[i]>0 {
            positive_sum.update(i, a[i]);
        } else {
            positive_sum.update(i, 0);
        }
    }

    let mut maxv=0;
    for i in 0..N-K+1 {
        let fixed = max(all_black_sum.query(i, i+K), 0);
        let mut rest=0;
        rest+=positive_sum.query(0, i);
        // dbg!(rest);
        rest+=positive_sum.query(i+K, N);
        // dbg!(fixed,rest);
        maxv=max(maxv, fixed+rest);
    }

    println!("{}",maxv);
}