ルパン四世

パソコン甲子園２００６、唯一どのチームにも解かれなかった問題です。参考記事。

この問題は「巡回セールスマン問題」に帰着できるので、ちょっと勉強すれば簡単に解けます。もちろん、問題のサイズである蔵の数が最高でも 15 個なので、力任せのアルゴリズムでは解くことができません。巡回セールスマン問題は、分岐限定法や遺伝的アルゴリズムなど、様々な方法で解くことができますが、問題のサイズが高々 20 くらいまでなら動的計画法で厳密解を求めることが可能です。

以下の解答プログラムでは、F[][] という配列を用いてます。
ここで、F[state][i] には、
状態 state で i 番目の蔵に至るまでにかかった時間を記録します。
ここで、state は「どの蔵がすでに破られたか」を表す数で、以下の表のように 0 ～ 2ⁿ - 1 の数をわりあてます。

例：蔵の数 n が４の場合

state	bit	意味
0	0000	どの蔵も破られていない
1	0001	1 番目の蔵を破った状態
2	0010	2 番目の蔵を破った状態
3	0011	1, 2 番目の蔵を破った状態
4	0100	3 番目の蔵を破った状態
5	0101	1, 3 番目の蔵を破った状態
6	0110	2, 3 番目の蔵を破った状態
7	0111	1, 2, 3 番目の蔵を破った状態
8	1000	4 番目の蔵を破った状態
.	.	...
.	.	...
15	1111	全ての蔵を破った状態

この F[][] を、state が 0 から 2ⁿ - 1 に向かって、動的計画法により計算していきます。

#include<iostream>
#define INFTY 1e+1000
#define MAX 15
#define SMAX 1 << MAX

using namespace std;

struct StoreHouse{
    int id, dist, nbox;
};

int nstore; // the number of storehouse
StoreHouse stores[MAX];
double F[SMAX][MAX]; // cost table
int W[SMAX]; // total wight in states
pair<int, int> P[SMAX][MAX]; // for path generation

double getCost( int source, int target, int state ){
    return abs(stores[source].dist - stores[target].dist )/(2000.0/(70 + W[state]));
}

void compute(){
    int smax = 1 << nstore;
    
    for ( int state = 1; state < smax; state++ ){
        for ( int j = 0; j < nstore; j++ ){
            F[state][j] = INFTY;
            P[state][j] = make_pair(-1, -1);
        }
    }
    
    for ( int j = 0; j < nstore; j++ ) F[1 << j][j] = 0;
    
    for ( int state = 1; state < smax; state++ ){
        for ( int i = 0; i < nstore; i++ ){
            if ( ! (( 1 << i ) & state ) ) continue;
            for ( int j = 0; j < nstore; j++ ){
                if ( ( 1 << j ) & state ) continue;
                double cost = F[state][i] + getCost(i, j, state);
                if ( cost < F[state|(1 << j)][j] ){
                    F[state|(1 << j)][j] = cost;
                    P[state|(1 << j)][j] = make_pair(state, i);
                }
            }
        }
    }
    
    int endpoint = 0;
    for ( int i = 1; i < nstore; i++ ){
        if ( F[smax-1][i] < F[smax-1][endpoint] ) endpoint = i;
    }
    
    pair<int, int> pre = make_pair(smax-1, endpoint);
    int path[MAX];
    for ( int i = 0; pre.first != -1; pre = P[pre.first][pre.second], i++ ){
        path[i] = stores[pre.second].id;
    }
    
    for ( int i = 0; i < nstore; i++ ){
        if ( i ) cout << " ";
        cout << path[nstore - i - 1];
    }
    cout << endl;
}

void input(){
    cin >> nstore;
    for ( int i = 0; i < nstore; i++ ){
        cin >> stores[i].id >> stores[i].dist >> stores[i].nbox;
    }
}

void init(){
    int limit = 1 << nstore;
    for ( int state = 1; state < limit; state++ ){
        int sum = 0;
        for ( int i = 0; i < nstore; i++ ){
            if ( state & (1 << i) ) sum += (stores[i].nbox * 20);
        }
        W[state] = sum;
    }
}

main(){
    input();
    init();
    compute();
}