2362:Square

keyword

BruteForce　C++

概要

M(<=20)本の棒が長さが与えられる。それらを組み合わせて正方形を作ることが出きるかどうか判定する問題。
サイズが小さいので全探索を考える。ただし4^20は流石に無理なので、まずは2^20通り調べて和が同じになるような分割を考える。その後に分割した両方がさらに分割できるか考えてやればよい。適当に定数倍最適化したら通ったけど0msの解答とかもあるのでもっとスマートな解があるのだと思う。

int ns[21];
int n;
static int v[2][21];

inline bool canDivide(int which, int s){
    int i, mask;
    int total = 0;
    REP(i,s) total += ns[v[which][i]];
    total >>= 1;
    s--;
    REP(mask,1<<s){
        int tmp = 0;
        REP(i,s)if(mask & (1<<i)){
            tmp += ns[v[which][i]];
            if(tmp > total) break;
        }
        if(tmp == total) return true;
    }
    return false;
}

void solve(){
    int i, mask, total;
    REP(i,21) ns[i] = 0;
    scanf("%d", &n);
    REP(i,n) scanf("%d",ns+i);
    sort(ns,ns+n,greater<int>());

    total = accumulate(ns,ns+n,0);
    if(total%4){
        printf("no\n");
        return ;
    }
    total >>= 1;
    if(ns[0] > (total>>1)){
        printf("no\n");
        return ;
    }

    REP(mask,1<<(n-1)){
        int tmp = 0;
        REP(i,n-1)if(mask & (1<<i)){
            tmp += ns[i];
            if(tmp>total)break;
        }
        if(tmp == total){
            int p1=0,p2=0;
            REP(i,n){
                if(mask & (1<<i)) v[0][p1++] = i;
                else v[1][p2++] = i;
            }
            if(canDivide(0,p1) && canDivide(1,p2)){
                printf("yes\n");
                return ;
            }
        }
    }

    printf("no\n");
    return ;
}

int main(){
    int rept;
    scanf("%d",&rept);

    LOOP(rept){
        solve();
    }

    return 0;
}