Rustコトハジメ

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

【ABC064-D Insertion】 かっこの整合性がとれるように修正する

D - Insertion

めっちゃハマりました。自分なりの理解をまとめておきます。

問題

かっこ列が与えられる。これを整合がとれた形に修正し、複数の可能性がある場合は辞書順最小のものを出力しなさい。

考え方

修正するだけなら、)と(の間で列を分割してしまい、それぞれについてn x ( + n x )の形に修正するということが考えられますが、

たぶん最短でない上に明らかに辞書順最小ではないので半分くらいのテストにはねられます。

元のかっこ列に対して、先頭にいくつか(をつけて、末尾にいくつか)をつけることが、もし最短ならば、辞書順最小を出す方法というのはわかります。

だから、かっこ列をたどっていき、(と)の数の違いに注目して、

  • (が多いなら、末尾への)を予約する
  • )が1つ余るなら、その時点で先頭に1つつける
  • )がもっと余ってるなら、末尾に予約した)をキャンセルする

というもっともらしいアルゴリズムを考えて実装します。

実装

fn solve() {
    input! {
        N: usize,
        S: chars,
    }

    let mut head = 0;
    let mut d = 0;
    for &c in &S {
        if c == '(' {
            d += 1;
        } else if c == ')' {
            if d == 0 {
                head += 1;
            } else {
                d -= 1;
            }
        }
    }

    let mut res = vec![];
    for _ in 0..head {
        res.push("(".to_string());
    }
    for c in S {
        res.push(c.to_string());
    }
    for _ in 0..d {
        res.push(")".to_string());
    }
    println!("{}", res.connect(""))
}

考察

蟻本のAtCoder問題集の「スタック」を用いる問題に数えられていましたが、この問題は違うと思います。かっこ列の不整合を判定するならばスタックを使うと思いますが。