Volume 1 / 0144->0147

Problem 0144 : Packet Transportation

有向グラフの最短経路を求める問題。
ワーシャル-フロイド法で解いた。

#include <iostream>
#include <vector>

using namespace std;


#define MAX 9999

int n;
vector< vector<int> > rtr;

void Floyd(){
	int i, j, k, l;

	for( i=1; i<=n; i++ ){
		for( j=1; j<=n; j++ ){
			for( k=1; k<=n; k++ ){
				if( rtr[j][k] > rtr[j][i]+rtr[i][k] ){
					rtr[j][k] = rtr[j][i]+rtr[i][k];
				}
			}
		}
	}

	return;
}

int main(void)
{
	int r, k, t, p, s, d, v, i, j;

	cin >> n;
	rtr.resize(n+1);
	for( i=0; i<=n; i++ )
		rtr[i].resize(n+1);

	for( i=1; i<=n; i++ )
		for( j=1; j<=n; j++ )
			rtr[i][j] = MAX;

	for( i=0; i<n; i++ ){
		cin >> r >> k;
		for( j=0; j<k; j++ ){
			cin >> t;
			rtr[r][t] = 1;
		}
	}

	Floyd();

	cin >> p;
	for( i=0; i<p; i++ ){
		cin >> s >> d >> v;
		if( rtr[s][d] != MAX && rtr[s][d]+1 <= v )
			cout << rtr[s][d]+1 << endl;
		else
			cout << "NA" << endl;
	}


	return 0;
}

Problem 0145 : Cards

動的計画法。

#include <iostream>
#include <vector>
#include <limits.h>

using namespace std;


#define MAX 100

typedef struct CARD_TAG {
	int top;
	int bottom;
} CARD;
int n, min_cost;
vector<CARD> src;


int calc(){

	int i, j, k, new_cost;
	unsigned int cost[MAX+1][MAX+1];

	for( i=0; i<=n; i++ )
		for( j=0; j<=n; j++ )
			cost[i][j] = INT_MAX;

	for( i=0; i<=n; i++ )
		cost[i][i] = 0;

	for( i=1; i<n; i++ ){
		for( j=0; j<n-i; j++ ){
			for( k=j+1; k<=i+j; k++ ){
				new_cost = src[j].top * src[k-1].bottom * src[k].top * src[i+j].bottom;
				if( cost[j][i+j] > cost[j][k-1] + cost[k][i+j] + new_cost ){
					cost[j][i+j] = cost[j][k-1] + cost[k][i+j] + new_cost;
				}
			}
		}
	}

	return cost[0][n-1];
}


int main(void)
{
	CARD tmp;

	cin >> n;
	for( int i=0; i<n; i++ ){
		cin >> tmp.top >> tmp.bottom;
		src.push_back(tmp);
	}

	cout << calc() << endl;

	return 0;
}

Problem 0146 : Lupin The 4th

動的計画法による巡回セールスマン問題。
ALGORITHM NOTEさんのALGORITHM NOTE ルパン四世を参考に。
というかほとんど丸写し。

メモ

state …　状態が保存されている変数
	0001 : 1番目の蔵に到達済み
	0010 : 2番目の蔵に到達済み
	0011 : 1,2番目の蔵に到達済み
4桁で書いたけれど、実際は蔵の数だけの桁がある。

cost[state][i]　…　stateの状態でi番目の蔵に到達（i番目の蔵に到達してstateの状態になった）ときの最小コスト。
そこから、例えばj番目の蔵に到達するためのコストは
cost[state|(1<<j)][j] = cost[state][i] + （i番目の蔵からj番目の蔵に向かうコスト）

#include <iostream>
#include <vector>
#include <stdlib.h>

using namespace std;


#define MAX 15
#define SMAX 1<<MAX

struct KURA_TAG {
	int id, dist, boxn;
} kura[MAX];

int n;
double cost[SMAX][MAX];
pair< int, int > p[SMAX][MAX];  // p[state][i]　…　i番目の蔵に達してstateの状態になった前の状態と蔵番号を保存（道順を得るときに使用）
int w[SMAX];


double getCost( int s, int d, int state )
{
	return abs( kura[s].dist - kura[d].dist )/(2000.0/(70+w[state]));
}

void calc()
{
	int state_max = 1 << n;
	int i, j;

	for( int state=1; state<state_max; state++ ){
		for( i=0; i<n; i++ ){
			cost[state][i] = 1000000000;
			p[state][i] = make_pair( -1, -1 );
		}
	}

	for( i=0; i<n; i++ )
		cost[1<<i][i] = 0;

	for( int state=1; state<state_max; state++ ){
		for( i=0; i<n; i++ ){
			if( !( ( 1<<i ) & state ) ) continue;
			for( j=0; j<n; j++ ){
				if( ( 1<<j ) & state ) continue;
				double new_cost = cost[state][i] + getCost( i, j, state );
				if( cost[state|(1<<j)][j] > new_cost ){
					cost[state|(1<<j)][j] = new_cost;
					p[state|(1<<j)][j] = make_pair( state, i );
				}
			}
		}
	}

	int end = 0;
	for( i=1; i<n; i++ )
		if( cost[state_max-1][i] < cost[state_max-1][end] )
			end = i;

	pair< int, int > pre = make_pair( state_max-1, end );
	int path[MAX];
	for( i=0; pre.first != -1; pre = p[pre.first][pre.second], i++ )
		path[i] = kura[pre.second].id;

	for( i=0; i<n; i++ ){
		// この書き方いい！
		if( i ) cout << " ";
		cout << path[n-i-1];
	}
	cout << endl;

	return;
}

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

	for( i=0; i<n; i++ )
		cin >> kura[i].id >> kura[i].dist >> kura[i].boxn;

	int limit = 1 << n;

	for( int state=1; state<limit; state++ ){
		int sum = 0;
		for( i=0; i<n; i++ )
			if( state&(1<<i) )
				sum += (kura[i].boxn*20);
		w[state] = sum;
	}

	calc();

	return 0;
}

Problem 0147 : Fukushimaken

goto文初めて使った。
意外と便利じゃない？

#include <iostream>
#include <vector>

using namespace std;


#define MAX 99
#define MAX_M 3047	// 全グループ終了までにかかる時間の最大（絶対にあり得ないけど）

struct STATE {
	int id; // グループ番号
	int m;  // 食事時間の残り
} state[MAX_M+1][17];  // state[minute][x] …　minute分のx番目の座席の状況


// テーブル作成
void calc()
{
	int t, p, i, j, k;
	bool flag = false;

	// 初期化
	for( i=0; i<=MAX_M; i++ ){
		for( j=0; j<17; j++ ){
			state[i][j].id = -1;
			state[i][j].m = 0;
		}
	}

	i = 0;
	for( t=0; t<=MAX_M && i<=MAX; t++ ){
		flag = false;	// 新しく座席が埋まったかを判定するフラグ

		// 前の時間の座席状況を引き継ぎ
		for( j=0; j<17 && t!=0; j++ ){
			if( state[t-1][j].m ){
				state[t][j].m = state[t-1][j].m-1;
				if( state[t][j].m )
					state[t][j].id = state[t-1][j].id;
			}
		}

		check:
		if( i*5<=t ){
			if( i%5 == 1 )
				p = 5;
			else
				p = 2;

			for( j=0; j<17 && !flag; j++ ){
				if( state[t][j].m == 0 ){ // 一番左の席を確定
					for( k=1; k<p && j+k<17 && state[t][j+k].m==0; k++ ); // 人数分あるか？
					if( k == p ){
						int tmp = 17*(i%2)+3*(i%3)+19; // 食事時間
						for( k=0; k<p; k++ ){
							state[t][j+k].id = i;
							state[t][j+k].m = tmp;
						}
						i++; goto check; // まだ入るグループがあるかチェック
					}
				}
			}
		}
	}

	return;
}

int search( int n )
{
	int t, x;
	for( t=n*5; ; t++ ){
		for( x=0; x<17; x++ )
			if( state[t][x].id == n )
				break;
		if( x != 17 )
			break;
	}

	// 待ち時間　=　グループ番号がstate[minute][x]に初めて現れる時刻 - 到着時刻
	return t-n*5;
}

int main(void)
{
	int n;

	calc();

	while( cin >> n )
		cout << search(n) << endl;

	return 0;
}