POJ2362 - Square

2362 -- Square

遅ればせながらid:Ozyさん、

Short Coding ~職人達の技法~

発売おめでとうございます！私も今日（遅っ）購入させていただきました〜。ゆるゆると味わいながら読ませていただきます。サイン欲しいよ〜、サイン。

ショートコーディングとは関係ないけど、結城浩さんの

数学ガール (数学ガールシリーズ 1)

も購入。数学も大好きですけど、数学の読み物も大好きです。

で、Square。
長さが与えられたn本の棒で正方形を作れるかどうかを判定する問題。
素直に再帰で解いてみました。

m,l,s[30],d[1<<20];

F(n,t,f,i,j){
  if(j=n|t)
    for(d[f]=1;i--;)
      if(~f&1<<i&&t+s[i]<=l&!d[f|1<<i]&&F(n-1,(t+s[i])%l,f|1<<i,m))
        return 1;
  return !j;
}

main(i,t){
  for(gets(t);~scanf("%d",&m);l/=4,puts(F(m,0,0,m)?"yes":"no"))
    for(bzero(d,1<<22),l=0,i=m;i--;l+=s[i])
      scanf("%d",s+i);
}

再帰関数の仮引数が紛らわしいので説明。
n : 処理していない棒の本数
t : 今繋いでいる辺の長さ
f : 使った棒のフラグ
i,j : ループやらなにやら