C - Synthetic Kadomatsu ～dfs 全探索～

f:id:peroon:20191027041151p:plain

Quiz

https://atcoder.jp/contests/abc119/tasks/abc119_c

AC Code

https://atcoder.jp/contests/abc119/submissions/8134185

void dfs(VI V){
  if(SZ(V)==N){
    calc(V);
    return;
  }
  rep(i, 4){
    V.push_back(i);
    dfs(V);
    V.pop_back();
  }
}

解法

  • 各竹を0, 1, 2, 3のどれかに割り当てる
    • 0 : 左の竹
    • 1 : 中央の竹
    • 2 : 右の竹
    • 3 : 使わない竹
  • 全パターンを試すためにdfsを使った

テク

  • vectorなのにpop_backしてスタック的に増減させている

おまけ

ll mi = min({12, 23, 34});

のように3つ以上のminって書けたのね

dfs 全探索 類題