らての精進日記

修行をします

aoj1175:And Then. How Many Are There?

解法

円盤の色の種類が高々4種類、それぞれの色について最大の枚数が高々6枚です。よって、円盤の総数は高々24枚です。


したがって、状態数は高々{ \displaystyle2^{24}}通りしかないことが分かります。


よって、再帰を使って初期状態から状態を遷移させていきます。一度訪れた状態にもう一度訪れることは無駄なので(同じ状態を何度見ても結果は一緒)、一度訪れた状態はメモします。


辿り着けた状態のなかで、取り除かれた円盤の枚数の最大値が答えです。


計算量は、{ \displaystyle
2^N
}通りの状態に対して、次の状態に遷移するときに{ \displaystyle
N^2
}回ループを回しているので{ \displaystyle
O(2^NN^2)
}くらいです。


初めてACしたときの実行時間が1.62secと少し遅かったので、頑張って定数倍を改善しました(それでも0.99secですが)。
とりあえず1.00secより速くなったのでここで諦めます。

コード

#include<bits/stdc++.h>
using namespace std;

int n;
int x[24],y[24],r[24],c[24];
bool overlap[24][24];
bool memo[1<<24];

bool ok(int a,int bit){
    for(int i=0;i<a;i++)if((bit>>i)&1){
        if(overlap[a][i])return false;
    }
    return true;
}

int dfs(int bit){
    memo[bit]=true;

    int ret=n;
    for(int i=0;i<n;i++)if((bit>>i)&1)ret--;

    for(int i=0;i<n-1;i++){
        if(((bit>>i)&1)==0||ok(i,bit)==false)continue;
        for(int j=i+1;j<n;j++){
            if(c[i]!=c[j]||((bit>>j)&1)==0)continue;
            int to_bit=(bit^(1<<i))^(1<<j);
            if(ok(j,bit)&&!memo[to_bit]){
                ret=max(ret,dfs(to_bit));
            }
        }
    }


    return ret;
}

void solve(){
    fill_n(memo,1<<n,false);

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            int dist=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
            int sum=(r[i]+r[j])*(r[i]+r[j]);
            overlap[i][j]=dist<sum;
        }
    }
    cout<<dfs((1<<n)-1)<<endl;
}

bool input(){
    cin>>n;
    if(!n)return false;
    for(int i=0;i<n;i++)cin>>x[i]>>y[i]>>r[i]>>c[i];
    return true;
}



int main(){
    while(input())solve();
    return 0;
}