結果

問題 No.519 アイドルユニット
コンテスト
ユーザー 戸澤遼
提出日時 2022-10-17 09:43:04
言語 C
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 6,233 bytes
コンパイル時間 452 ms
コンパイル使用メモリ 33,792 KB
実行使用メモリ 12,416 KB
最終ジャッジ日時 2024-06-28 01:10:33
合計ジャッジ時間 4,990 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <complex.h>

//全マッチング数の計算　n*(n-2)*(n-4)*...*1を返す
int all_explo(int n)
{
    if(n>1)
    {
        return n*all_explo(n-2);
    }
    else if(n==1)
    {
        return 1;
    }

}

//最大マッチング探査用関数
double explo(int Nexp,double d_euc[(int)Nexp][(int)Nexp],int vertex[(int)Nexp],double d,int decide)
{
    int i,j,flag=0;
    
    //最後の頂点データが埋まっている、つまり下の関数でi++が行われた後にこの関数に入ってくるとまずここに入る
    if(vertex[(int)Nexp-1]!=0)
    {
        //最後と最後の一個前の頂点データに格納されている組み合わせによる距離をdから引く
        d-=d_euc[vertex[(int)Nexp-2]][vertex[(int)Nexp-1]];

        //距離データ配列の中の使用済みマークを消す（使用済みマークは自己との距離、つまり00、11などに-1を入れている　ここが0なら未使用頂点ということ）
        d_euc[vertex[(int)Nexp-2]][vertex[(int)Nexp-2]]=0;
        d_euc[vertex[(int)Nexp-1]][vertex[(int)Nexp-1]]=0;

        //一番後ろの頂点データ組み合わせを0にする
        vertex[(int)Nexp-2]=0;
        vertex[(int)Nexp-1]=0;

        //現在決定中の頂点番号decideを-2（このdecideは頂点データvertexの何番目の頂点を現在決定しているか表す　0<=decide<Nexp）
        decide=Nexp-2;

        //最後の組み合わせの前の組み合わせから順に見ていく
        for(i=4;i<=Nexp;i+=2)
        {
            //今確認中の組み合わせの距離をdから引く
            d-=d_euc[vertex[(int)Nexp-i]][vertex[(int)Nexp-i+1]];

            //組み合わせの使用済みマーク消去
            d_euc[vertex[(int)Nexp-i]][vertex[(int)Nexp-i]]=0;
            d_euc[vertex[(int)Nexp-i+1]][vertex[(int)Nexp-i+1]]=0;

            //組み合わせの後半の頂点の順番が後の頂点を確認（例えば、Nexp=8、今確認中の頂点が45の場合、後半の頂点5の後ろの頂点6、7を確認）
            for(j=1;j<Nexp-vertex[(int)Nexp-i+1];j++)
            {
                //その頂点がNexpではない（例えばNexp=8、確認中の頂点が47の場合、ここでは存在しない9番目の頂点を見てしまうため）かつその頂点が使用済みではない場合
                if((vertex[(int)Nexp-i+1]+j)!=Nexp && d_euc[vertex[(int)Nexp-i+1]+j][vertex[(int)Nexp-i+1]+j]!=-1)
                {
                    //組み合わせの前半頂点といま見ている頂点を新たな組み合わせとする
                    d+=d_euc[vertex[(int)Nexp-i]][vertex[(int)Nexp-i+1]+j];

                    //2つに使用済みマークを付ける
                    d_euc[vertex[(int)Nexp-i]][vertex[(int)Nexp-i]]=-1;
                    d_euc[vertex[(int)Nexp-i+1]+j][vertex[(int)Nexp-i+1]+j]=-1;
                    
                    //頂点データの後半を見ていた頂点へと書き換え
                    vertex[(int)Nexp-i+1]=vertex[(int)Nexp-i+1]+j;

                    //2重forループ脱出
                    flag=1;
                    break;
                }
            }

            if(flag==1)
            {
                break;
            }

            //確認中の組み合わせ後半頂点の、順番が後ろの頂点がすべて使用済みの場合、確認中組み合わせ頂点データを消去して、decideを-2
            vertex[(int)Nexp-i]=0;
            vertex[(int)Nexp-i+1]=0;
            
            decide-=2;

            //このforループの最初に戻ることでさらにひとつ前の組み合わせを確認
        }
    }

    //使用済みでない頂点の中から、前から順番に探索して一つの組み合わせを作成し、距離間をdに
    for(i=0;i<Nexp;i++)
    {
        if(d_euc[i][i]!=-1)
        {
            vertex[decide]=i;
            d_euc[i][i]=-1;
            
            for(j=i+1;j<Nexp;j++)
            {
                if(d_euc[j][j]!=-1)
                {
                    decide++;
                    vertex[decide]=j;
                    d_euc[j][j]=-1;
                    d+=d_euc[i][j];
                    break;
                }
            }
            break;
        }
    }

    //すべての頂点が確定していない場合、すぐ上のfor文をもう一度回してさらに組み合わせを1つ作成
    if(decide!=(int)Nexp-1)
    {
        explo(Nexp,d_euc,vertex,d,decide+1);
    }
    //すべての頂点が確定した場合、下の関数にdを返す
    else if(decide==(int)Nexp-1)
    {
        return d;
    }
}

//最適配置を見つける関数　各頂点距離間データd_eucを受け取って、2点ずつ選んでつないでいったときに各組合せの距離間の合計が最大となるような組み合わせ表placeを返す
void optimal_place(int Nexp,double d_euc[(int)Nexp][(int)Nexp],int place[(int)Nexp])
{
    int i,j,k,n,decide=0;
    double d=0,dmax=0;
    //頂点データ一次保管用配列
    int vertex[(int)Nexp];
    
    //マッチングは全探査で行うが、その全探査数n
    n=all_explo((int)Nexp-1);

    //頂点データを0で初期化
    for(i=0;i<Nexp;i++)
    {
        vertex[i]=0;
    }

    for(i=0;i<n;i++)
    {
        //実際の探査用関数　配列2つは書き換えが行われ、現在探査中の組み合わせvertexにおける距離合計値をdで返す
        d=explo(Nexp,d_euc,vertex,d,decide);

        //dと現在の最大距離合計dmaxで比較して、dが大きければ頂点データvertexをplaceにコピー
        if(d>dmax)
        {
            dmax=d;
            for(j=0;j<Nexp;j++)
            {
                place[j]=vertex[j];
            }
        }
    }

    printf("%d\n",(int)dmax);
}

int main(void)
{
    int n,i,j;

    scanf("%d",&n);
    
    double a[n][n];
    int b[n];

    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            scanf("%lf",&a[i][j]);
        }
    }

    for(i=0;i<n;i++)
    {
        a[i][i]=0;
    }

    optimal_place(n,a,b);
}
0