メモログ

競プロ典型90問 002 - Encyclopedia of Parentheses 解説

ilmango
2022/01/08 16:37


これは競プロ典型90問 問題002 - Encyclopedia of Parentheses の解説記事です.使用言語はRustです.

 

コードブロックが機能していません,そんな…

使い方が分かる方が居ましたら教えていただけると嬉しいです

 

問題

https://atcoder.jp/contests/typical90/tasks/typical90_b

 

ACコード

2通りの実装を示します.

実装その1

実装その2

 

解法(実装)その1

正しいカッコ列は文字 () のみから構成され,nが20以下であることからbit全探索ができそうなことが分かります.まず長さnのありうるカッコ列すべて(正しくないカッコ列も含めて)作ることを考えます.0を ( , 1を ) に対応させると,例えばn=10のときの正しいカッコ列のうちの1つ ((((()))))0000011111 に対応します.他にも (()()())()0010101101 に対応します.よって,n=10の場合2進数表記で 0b0000000000 から 0b1111111111 まで (10進数で表記すると,0 から 2^10 - 1 = 1023 まで) ループを回して,それぞれに対応したカッコ列を生成すればすべてのカッコ列を作ったことになります.一般化して, 0 から 2^n - 1 までループを回せばよいです.ACコードは

for bits in 0..1 << n {}

となっていますが,1 << n はn回左シフトすることを表しています.つまり 1 << 20b100, 1 << 100b10000000000 です.これは

for bits in 0..2usize.pow(n as u32) {}

と同じです.

数値を対応するカッコ列に変換するには各桁が0か1かを見なければなりませんが,それは

for shift in (0..n).rev() {
	if (bits >> shift) & 1 == 0 {
		parentheses.push('(');
	} else {
		parentheses.push(')');
	}
}

の部分に対応します.bits >> shift は,数値をshift回右シフトすることを表しています.0b101 >> 20b1 , 0b10111011 >> 50b101 です.そして1との論理積を取ることで各桁が1か0かを見ることができます(例えば, 0b1011101 & 11 , 0b101110 & 10 です). shiftはn-1から0まで回すので,上位桁(左側)から順に見ていく形です.

次に生成したカッコ列が正しいカッコ列かどうかを判定する必要があります.結論を述べると,左から順に見て ( である場合はカウンタを+1, ) である場合はカウンタを-1 して途中で負になった時点で正しいカッコ列でなく,最後まで見終わった後でカウンタが0でない場合も正しいカッコ列ではありません.より直感的なものとして,() を消すことを繰り返していき空文字列になればそれは正しいカッコ列であるというものがあります.いずれにせよ,実装は難しくありません.結局,O(n2^n) で解くことができました.

 

use proconio::*;

#[fastout]
fn main() {
    input! {
        n: usize,
    }
    for bits in 0..2usize.pow(n as u32) {
        let mut parentheses = String::with_capacity(n);
        for shift in (0..n).rev() {
            if (bits >> shift) & 1 == 0 {
                parentheses.push('(');
            } else {
                parentheses.push(')');
            }
        }

        if parentheses_valid(&parentheses) {
            println!("{}", parentheses);
        }
    }
}

fn parentheses_valid(parentheses: &str) -> bool {
    let mut check = 0;
    for c in parentheses.chars() {
        if c == '(' {
            check += 1;
        } else {
            check -= 1;
        }
        if check < 0 {
            return false;
        }
    }
    if check != 0 {
        return false;
    }
    true
}

 

解法(実装)その2

その1より少しだけはやい実装です.正しいカッコ列は,直感的に () の数が等しいカッコ列の集合の部分集合であることは分かると思います.必然的に,長さが奇数の正しいカッコ列は存在しません. () の数が等しいカッコ列を列挙するには combinations を用います.

for open in (0..n).combinations(n/2) {}

これは0からnまでの数のうち,n/2個だけ選ぶことをしています.はじめ ) のみで初期化しておいて,選ばれた数の場所を ( で置き換えることをすれば () の数が等しいカッコ列を生成できます.あとは実装その1と同様に正しいカッコ列かどうかを判定すれば良いです.なお,combinations は小さい数から選んでくれるので辞書順になってくれます.カッコ列の生成部分に関して,実装その1は最大で2^20 = 1048576回のループがありますが実装その2はおおよそ 20C10 = 184756回で済みます.nC(n/2) = n!/((n/2)!(n/2)!) より,結局 O(n*n!/((n/2)!)^2) で解けました.(この表記が正しいのかわかりません…)

 

数式モード欲しい

 

use proconio::*;
use itertools::Itertools;

#[fastout]
fn main() {
    input! {
        n: usize,
    }
    if n % 2 == 1 {
        return;
    }
    for open in (0..n).combinations(n/2) {
        let mut parentheses = Vec::with_capacity(n);
        parentheses.resize(n, ')');
        open.iter().for_each(|i| parentheses[i] = '(');
        let parentheses = parentheses.iter().collect::<String>();
        if parentheses_valid(&parentheses) {
            println!("{}", parentheses);
        }
    }
}

fn parentheses_valid(parentheses: &str) -> bool {
    let mut check = 0;
    for c in parentheses.chars() {
        if c == '(' {
            check += 1;
        } else {
            check -= 1;
        }
        if check < 0 {
            return false;
        }
    }
    if check != 0 {
        return false;
    }
    true
}
  • 65
  • 0

この投稿に最初のコメントをしましょう!


スポンサーリンク
PR

広告募集中!!

広告スペースをMONAで販売中です。
この投稿に最初のコメントをしましょう!

モナゲして応援しよう!

Loginすることで、モナゲが可能になります。