C - Synthetic Kadomatsu

Quiz

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

Submit

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

Note

  • N=8と小さい
  • 伸ばしてから合成と、合成してから伸ばすのは同じ
  • 各竹をA, B, C, D(使わない)に割り当てるのを全パターン試せばいい

全パターン列挙のためのビットシフトとAND

f:id:peroon:20190225002837j:plain

対応するコード

    FOR(i, 0, 1<<2*N){
        vector<ll> S(4); // sum of A, B, C, D
        vector<ll> merge(4);
 
        FOR(j, 0, N){
            ll b0 = i >> 2*j & 3;
            S[b0] += L[j];
            merge[b0]++;
        }