kmjp's blog

競技プログラミング参加記です

LeetCode Weekly Contest 118 : 972. Equal Rational Numbers

似たようなのどっかで見たなぁ…。
https://leetcode.com/contest/weekly-contest-118/problems/equal-rational-numbers/

問題

循環部分を括弧で囲う形で表現された数が2つ文字列で与えられる。
両者は同じ数を示すか判定せよ。

解法

面倒なので循環部分を小数点以下第1000桁位まで展開してしまい、比較すればよい。
ただし、循環部分が999999....となる場合は繰り上がりが生じるので注意。

class Solution {
public:
	string parse(string S) {
		string T;
		
		if(S.find('.')==string::npos) {
			T=S+"."+string(1000,'0');
		}
		else if(S.find('(')==string::npos) {
			T=S+string(1000,'0');
		}
		else {
			int i=S.find('(');
			T=S.substr(0,i);
			string U=S.substr(i+1,S.size()-1-(i+1));
			
			if(count(ALL(U),'9')==U.size()) {
				for(i=T.size()-1;i>=0;i--) {
					if(T[i]=='.') continue;
					if(T[i]!='9') {
						T[i]++;
						break;
					}
					T[i]='0';
				}
				if(i==-1) T="1"+T;
				T+=string(1000,'0');
			}
			else {
				while(T.size()<1000) T+=U;
			}
			
		}
		T.resize(1000);
		cout<<T<<endl;
		return T;
		
		
	}
	
	
    bool isRationalEqual(string S, string T) {
        return parse(S)==parse(T);
    }
};

まとめ

以前AtCoderでも似たようなの(もっと桁数の制限が厳しいの)見た気がする。