Rustコトハジメ

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

【天下一プログラマーコンテスト2016予選B-B 天下一魔力発電】右から括弧列を見ていく

たぶん想定と違うので紹介。O(N)

問題

括弧列がある。左から辿っていき、その都度反転することが許される。

移動がコスト1、反転がコスト1とした時、この括弧列を対応がとれたものにするにはコストいくらかかるか?

方針

対応がとれているかの判定にはスタックを使うことが出来る。

反転させたいなら出来るだけ左で反転させたいので、まずは絶対に反転させないとどうしようもないものを右から見ていく。

例えば、

...((())

のような形はだめである。なぜならば、左の(は対応させることが出来ないから。

だからこのように(の方が多くなってしまった場合は絶対に反転させるしかない。すなわち、...(())にする他ない。

まず、こういう「絶対に反転させるしかないやつ」を反転させる。

次に左から見ていって、(成分の足りない分だけ反転させる。これは貪欲に前の方の)を反転させてしまってよい。なぜならば、スタックで対応判定を考えると、どこで反転させようが数があっていれば対応列であることがなんとなくわかるからである。直感的な説明は以下。

左から見ていった時も、右から見ていった時と同様に、(()))のような形になると死ぬ。例えばこの形ならば、間違いなく(())は良い。ではそれより前を反転させることを考えると、((())これもOKそう。(()()これもOKそう。ということで、「たぶん貪欲でOK」という判断になる。たぶんどの場合も、「より左の方の(が残ってくれるため、安心して短い対応列を作ることが出来る。それで単なる(に帰着するから。

実装

fn solve() {
    input!{
        s:chars
    }
    let mut s=s;
    let n=s.len();

    let mut right=0;
    let mut left=0;
    let mut ps=vec![];
    for i in (0..n).rev() { // O(n)
        if s[i]==')' {
            right+=1;
        } else {
            left+=1;
        }

        if left>right {
            ps.push(i);
            s[i]=')';
            left-=1;
            right+=1;
        }
    }
    assert!(right>=left);
    let mut k=(right-left)/2;
    for i in 0..n {
        if s[i]==')' && k>0 {
            s[i]='(';
            k-=1;
            ps.push(i);
        }
    }

    let mut m=ps.len();
    let mut max_i=0;
    for p in ps {
        max_i=max(max_i,p);
    }
    println!("{}",max_i+m);
}