下の子がウェイクワードを使う / 競プロ典型 90 問 002

先週末くらいからだけど下の子が Google Home のウェイクワードを使えるようになっている。リスク。

---

競プロ典型 90 問

• 002 - Encyclopedia of Parentheses（★3） https://atcoder.jp/contests/typical90/tasks/typical90_b
  • 提出: https://atcoder.jp/contests/typical90/submissions/50476532
  • bit 全探索
  • 愚直に試す N <= 20 なので 2^20 のすべてのパターンに対して 20 要素確認しても間に合う

use std::collections::BTreeSet;

use proconio::input;

fn main() {
    input! {
        n: usize,
    };
    let mut ans = BTreeSet::new();
    for bits in 0..1 << n {
        let cs = (0..n)
            .map(|i| if ((bits >> i) & 1) == 1 { ')' } else { '(' })
            .collect::<Vec<char>>();
        let mut ok = true;
        let mut stack = vec![];
        for c in cs.iter().copied() {
            match c {
                '(' => stack.push(c),
                ')' => match stack.pop() {
                    None => {
                        ok = false;
                        break;
                    }
                    Some(p) => {
                        if p != '(' {
                            ok = false;
                            break;
                        }
                    }
                },
                _ => unreachable!(),
            }
        }
        ok &= stack.is_empty();
        if ok {
            ans.insert(cs.into_iter().collect::<String>());
        }
    }
    for a in ans {
        println!("{}", a);
    }
}

---

今日のコミット。

• rust-atcoder 1 commit
  • typical90 002
• rust-sandbox 1 commit
  • roguelike-tdd: Add Door::write_to_map