AOJ : 2026 - Divisor is the Conqueror

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2026
N 枚のカードがあります.
このカードは, トランプカードで, 1~13の数字が書かれたカードが, それぞれ最大 4 枚あります.
そのため, N の上限は 52 と設定されています.

このとき, 次のような条件を満たす並べ方があるならば, その並べ方を出力します.

• 左側から数えて, i 番目のカードの数字は, 「1〜i-1 番目のカードの数字の合計」を割り切る.
• N 枚のカードはそれぞれ 1 回ずつしか使用できない.

アルゴリズム

動的計画法でできないか思考錯誤していて, 結局できなかったため, shioshiota さんのブログを参考にさせていただきました.
http://d.hatena.ne.jp/shioshiota/20100812/1281624750

ありがとうございます！

ポイント

要素量が 52 の配列を作って, 再帰するごとにループしていると時間が間に合わない.
14 の大きさの配列に縮めて, 13 種類のカードのカウント値だけ持つ.
これによって, 大幅に計算量が削減される.

後ろから再帰しないと間に合わない理由は, いまいちわからない.
実際に書いてみて, 遅いことは確認しましたが.

プログラム

#define REP(i,n,m) for(int i=n;i<m;i++)
#define rep(i,n) REP(i,0,n)

int n,cnt[14],ans[54];

bool solve(int idx,int sum){
  if(idx == 0 && sum == 0) return true;
  if(idx < 0 || sum < 0) return false;

  rep(i,14){
    if(cnt[i]>0 && (sum - i) % i == 0){
      ans[idx-1] = i;
      cnt[i]--;
      if(solve(idx-1,sum-i)) return true;
      cnt[i]++;
    }
  }

  return false;
}

int main(void){
  while(cin>>n,n){
    int sum = 0;
    memset(cnt,0,sizeof(cnt));
    rep(i,n){
      int x;
      cin>>x;
      sum += x;
      cnt[x]++;
    }
    bool flg = solve(n,sum);
    if(flg){
      rep(i,n-1) cout<<ans[i]<<" ";
      cout<<ans[n-1]<<endl;
    }
    else{
      cout<<"No\n";
    }
  }

  return 0;
}