HackerRank Goldman Sachs CodeSprint : E. Currencies

Codeforcesやってなければ賞金圏内も狙えたかも？
https://www.hackerrank.com/contests/gs-codesprint/challenges/currencies

問題

N種類の通貨がある。
i番の通貨をj番の通貨に両替するときのレートがN次正方行列Aで与えられる。

初期状態でS番の通貨をXだけ持っていたとする。
全額両替をM回行った後F番の通貨を持っている状態にしたい。
最適な両替後の金額はいくらか。

解法

Mはとても大きいが、Nは小さい。
よって、M回のうちほとんどはどこかでループを繰り返すことになる。

よって

• Sからx回かけてUに到達
• Uでj手のループを(M-(x+y))/j回繰り返す
• Uからy回かけてFに到達

という両替ルートを、x,y,jに対し総当たりすればよい。
なお、普通に両替後の金額を保持するとdouble型でも格納しきれないが、幸い今回は乗算しか出てこないので、対数を使おう。
対数を取ったdouble値と、整数値を両方使い、大小判定には前者を、解には後者の値を使うとよい。

int N,X,S,F,M;
int A[20][20];
double L[20][20];

double dpf[20][61][20];
ll dpi[20][61][20];
ll mo=1000000007;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X>>S>>F>>M;
	FOR(y,N) FOR(x,N) {
		cin>>A[y][x];
		if(x!=y) L[y][x]=log(A[y][x]);
	}
	
	FOR(x,N) FOR(y,60) FOR(i,N) dpf[x][y][i]=-1;
	FOR(i,N) {
		dpf[i][0][i]=0;
		dpi[i][0][i]=1;
		FOR(j,60) {
			FOR(x,N) if(dpf[i][j][x]>=0) {
				FOR(y,N) if(x!=y && dpf[i][j][x]+L[x][y]>dpf[i][j+1][y]) {
					dpf[i][j+1][y]=dpf[i][j][x]+L[x][y];
					dpi[i][j+1][y]=dpi[i][j][x]*A[x][y]%mo;
				}
			}
		}
	}
	
	double maf=-1;
	ll ma=0;
	FOR(i,N) {
		FOR(x,60) FOR(y,60) for(j=2;j<=20;j++) {
			if(x+y<=M && (M-(x+y))%j==0) {
				double hoge=dpf[S][x][i]+dpf[i][y][F]+dpf[i][j][i]*((M-(x+y))/j);
				if(dpf[S][x][i]<0 || dpf[i][y][F]<0 || dpf[i][j][i]<0) continue;
				if(hoge>maf) {
					maf=hoge;
					ma=X*dpi[S][x][i]%mo*dpi[i][y][F]%mo*modpow(dpi[i][j][i],(M-(x+y))/j)%mo;
				}
			}
		}
		
	}
	
	cout<<ma<<endl;
	
	
}

まとめ

2日間やるコンテストで60ptが上限ってどうなの…。