AtCoder ARC #015 : C - 変わった単位

今回はこれまでにないCの正答率。
幸い問題点に気づいて4ミスで解けた。1個はRuntime Errorだけどね。
http://arc015.contest.atcoder.jp/tasks/arc015_3

問題

いくつかの単位がある。
ある単位LargeとSmallについて、1 LargeがSmall何個分かが与えられている。
最大の単位1個分が、最小の単位何個分になるかを答えよ。

解法

入力から2単位間の変換倍率がわかる。
あとはFloyd法の要領で、直接変換できない単位間の倍率を求めていく。

注意点は、途中単位間の比率が整数でなく有理数になること。
また、どうやら有理数にしても分子分母が数百桁になるケースがあるので、long longで分子分母とっても失敗する。

ちなみに本番は分数になることに気づいてdoubleにしたら通った。
解答が整数比になることを利用して、最後に0.1を足して誤差対策。

対数を使って単位間の倍率を乗算から加算にする手もあるみたいね。そっちは気づかなかった。

int N;
double mat[401][401];
map<string,int> AA;
string SS[401];

void solve() {
	int f,r,i,j,k,l,x,y,tx,ty;
	
	int N;
	cin>>N;
	FOR(i,N) {
		string s1,s2;
		cin>>s1>>j>>s2;
		if(AA.find(s1)==AA.end()) {
			AA[s1]=AA.size()-1;
			SS[AA[s1]]=s1;
		}
		if(AA.find(s2)==AA.end()) {
			AA[s2]=AA.size()-1;
			SS[AA[s2]]=s2;
		}
		
		mat[AA[s2]][AA[s1]]=j;
		mat[AA[s1]][AA[s2]]=1.0/j;
	}
	N=AA.size();
	
	FOR(j,2) {
		FOR(i,N) FOR(x,N) FOR(y,N) {
			if(mat[x][y]==0 && mat[x][i]>0 && mat[i][y]>0) mat[x][y]=mat[x][i]*mat[i][y];
			if(mat[x][y]==0 && mat[x][i]>0 && mat[y][i]>0) mat[x][y]=mat[x][i]/mat[y][i];
		}
	}
	double la=0;
	string fr,to;
	FOR(x,N) FOR(y,N) {
		if(la<mat[x][y]) {
			la=mat[x][y];
			fr=SS[y];
			to=SS[x];
		}
	}
	_P("1%s=%lld%s\n",fr.c_str(),(ll)(la+0.001),to.c_str());
}

まとめ

途中で有理数になることに早めに気づけて良かった。