Pの競プロ記

競技プログラミングに関することを書きます。

AOJ 2026 Divisor is the Conqueror

概要


問題文はこちら
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2026

N枚のカードを持っています。
そのカードをある条件に従って一枚ずつ場に出し、N枚全てのカードを場に出すことができるかを判定する問題です。

ある条件についてですが、あるカードを場に出すときそれ以前に場に出したカードの和を割り切ることができないといけません。
(例)場に 3 3 1 が出ているとき、その和は7なので次に場に出すことができるカードは1か7になります。


解法


全探索+枝刈りで解くことができます。

この問題は自力でやってもTLEを回避できなかったので、nanikakaさんの記事を参考にしました。感謝。

先頭から探索させていくと、分岐が多くなりTLEになってしまいます。
ここでひと工夫、どうやら末尾から始めるとあっという間に解くことができるようになるそうです。

まずN枚全てのカードが場に出ているとします。
そこから一枚選び、その残りの場に出ているカードの和が選んだ1枚のカードで割り切れるか判定します。 できるのならもう一枚取り除いていく…(ry。
という感じで末尾から探索させればよいです。

(逆から調べるという発想がありませんでした…)


ソースコード

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<complex>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<cassert>
#include<cstring>
using namespace std;
 
#define REP(i,x,n) for(int i = x ; i < (int)(n) ; i++)
#define rep(i,n) REP(i,0,n)
#define f first
#define s second
#define mp make_pair
#define pb push_back
 
typedef pair<int,int> P;
typedef long long ll;
 
static const int INF = (1 << 29);
static const double EPS = 1e-9;
static const double PI = acos(-1.0);
 
int N;
int total;
int card[14];
int ans[52];
 
bool dfs(int sum, int idx){
  if(idx < 0) return true;
   
  for(int i = 1; i <= 13; i++){
    if(card[i] == 0) continue;
    if((sum - i) % i != 0) continue;
    ans[idx] = i;
    card[i]--;
    if(dfs(sum - i, idx - 1)) return true;
    card[i]++;
  }
   
  return false;
}
 
bool solve(){
  for(int i = 1; i <= 13; i++){
    if(card[i] == 0) continue;
    if((total - i) % i != 0) continue;
    ans[N - 1] = i;
    card[i]--;
    if(dfs(total - i, N - 2)) return true;
    card[i]++;
  }
  return false;
}
 
int main(){
  while(cin >> N && N){
    total = 0;
    memset(card,0,sizeof(card));
    rep(i,N){
      int num;
      cin >> num;
      card[num]++;
      total += num;
    }
    if(!solve()) puts("No");
    else{
      rep(i,N){
        if(i + 1 != N) cout << ans[i] << " ";
        else cout << ans[i] << endl;
      }
    }
  }
  return 0;
}