読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

UVa 104 - Arbitrage

WA出しても正答率が分からない恐怖。
問題の読みとばしが原因のWAだったので反省。

- 問題概要

Arbitrage、すなわり価格差を利用して利益を得る取引のことです。
裁定取引や鞘取引といったりもするそうです。
ある物品A,B,Cがあって、
AをBに交換、BをCに交換、CをAに交換という操作をします。
すると各交換時のレートによって交換前のAと交換後のAの量が変わったりします。
これを利用して、Aをもとの量の1.01倍以上にする交換回数が最小な交換順を求めてくださいという問題です。

具体的には、状態の数nが与えられます。次にテーブルが与えられ、i行目j列に
iから(j<i?j:j+1)に遷移するとき値が何倍になるかが与えられます。
ある状態mから状態遷移を繰り返し、再びmに戻った時値が1.01倍以上になる長さが最小の状態遷移列を求めよ。
ただし開始位置mはどの状態から始めてもよい。状態遷移列がnを超えた場合や利益を全く得られない場合は特定の文字列を出力する。

- 解法

dpもどきで解きました。
が、ベルマンフォードと同じ動きをしていたのでベルマンフォードで解ける問題だと思います。
状態1,,,nについて、始点をsとし、dp(i,j)をi回目の状態遷移でjに到達できる最大の倍率とします。
table(x,y)をxからyに遷移するときの倍率とすると、
dp(i,j)=max(dp(i-1,k)*table(k,j))となるため、O(N)で求められます。
これを全てのjについて求め、iの小さい順に動的計画法を適用すると、
dp(i,s) \ge 1.01を満たす最小のiがsを始点とした時の最小の遷移回数となります。
遷移する際遷移前の状態を保存しておくことでパスを辿ることが可能です。
よって始点sからの最小の状態遷移列を求めるために必要な計算量はO(N^3)
これを全てのsに対して行えばよいのでO(n^4)で解が求められます。

おそらく負の経路を検出できればよいのでワーシャルフロイドを使って効率よく解ける気もします。
実装する際はリストの初期化などを忘れないようにしましょう。

- ソースコード

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<list>
#include<vector>
#include<fstream>
using namespace std;
#define rep(i,a,b) for(auto (i)=(a);(i)<(b);(i)++)
#define itr(i,b) for(auto (i)=(b).begin();(i)!=(b).end();++(i))
double table[30][30];
const double eps = 1e-8;
int n;
struct dptable{
	double c;
	int par;
};
dptable dp[30][30];

list<int> path;
vector<int> result;

void calc(int st){
	path.clear();
	rep(i, 0, n)dp[0][i].c = 0.0;
	dp[0][st].c = 1.0;
	rep(i, 1, n + 1){
		rep(j, 0, n){
			dp[i][j].c = dp[i - 1][j].c;
			dp[i][j].par = j;
			rep(k, 0, n){
				if (dp[i][j].c < dp[i - 1][k].c * table[k][j])
					dp[i][j].c = dp[i - 1][k].c * table[k][j], dp[i][j].par = k;
			}
		}
		if (dp[i][st].c > 1.01+eps ){
			path.push_front(st);
			int p = st;
			while (i>0){
				path.push_front(dp[i][p].par);
				p = dp[i--][p].par;
			}
			break;
		}
	}
	
}

int main(void){
	while (cin >> n){
		result.clear();
		rep(i, 0, n){
			table[i][i] = 1.0;
			rep(j, 0, n){
				if (i != j){
					cin >> table[i][j];
				}
			}
		}
	
		rep(i, 0, n){
			calc(i);
			if ((result.empty()==true) ||( path.size() < result.size()))
			if(path.empty()==false){
				vector<int> temp(path.begin(), path.end());
				result = temp;
			}
		}

		if (result.empty()){
			cout << "no arbitrage sequence exists" << endl;
		}
		else{
			rep(i, 0u,result.size()-1)
				cout <<result[i] + 1<<" ";
			cout << result[result.size() - 1]+1 << endl;
		}
	}
	return(0);
}