TopCoder SRM 761 : Div1 Easy Div2 Hard AddPeriodic

Mediumで早とちりして誤解法に行っちゃったのもったいなかったな。
https://community.topcoder.com/stat?c=problem_statement&pm=15579

問題

循環小数表記の数が2つ与えられる。
2つの和を、最小な長さの循環小数表現でを答えよ。

解法

1つは両方を有理数で計算すること。
ただ、循環部分は最大8桁取れるので、最悪循環部分が7桁の値と8桁の値を足すと、循環部分が56桁になる。
そうすると多倍長整数が使えない環境だと面倒臭い。

もう１つは適当に数百桁文字列表記して足し算し、循環長を求めること。
今回はこちらを取っている。

const int L=300;

class AddPeriodic {
	public:
	pair<ll,string> conv(string A) {
		ll v=0;
		int i,j;
		string B;
		FOR(i,A.size()) {
			if(A[i]=='.') break;
			v=v*10+A[i]-'0';
		}
		
		for(j=i+1;j<A.size();j++) {
			if(A[j]!='(') {
				B+=A[j];
			}
			else {
				int x=j+1;
				int y=A.size()-1;
				FOR(i,L+200) {
					B.push_back(A[x+i%(y-x)]);
				}
				break;
				
			}
			
		}
		B.resize(L+200);
		return {v,B};
		
	}
	
	string add(string A, string B) {
		auto a=conv(A);
		auto b=conv(B);
		string S;
		int i,c=0;
		for(i=L+199;i>=0;i--) {
			int x=a.second[i]-'0'+b.second[i]-'0'+c;
			S.push_back('0'+x%10);
			c=x/10;
		}
		reverse(ALL(S));
		ll v=a.first+b.first+c;
		
		string R(500,'1');
		int s,l,x;
		FOR(s,L) {
			for(l=1;s+l<=L;l++) {
				int ok=1;
				for(x=s;x<L;x+=l) {
					int le=min(l,L-x);
					if(S.substr(s,le)!=S.substr(x,le)) {
						ok=0;
						break;
					}
				}
				if(ok==0) continue;
				string P=S.substr(0,s);
				string Q=S.substr(s,l);
				if(Q=="9") {
					Q="0";
					int c=1;
					for(i=(int)P.size()-1;i>=0;i--) {
						if(P[i]=='9') {
							P[i]='0';
							c=1;
						}
						else {
							P[i]++;
							c=0;
							break;
						}
					}
					v+=c;
				}
				
				string ret=to_string(v)+"."+P+"("+Q+")";
				if(ret.size()<R.size()) R=ret;
				break;
			}
		}
			
		
		
		
		
		return R;
		
	}

まとめ

解いてて楽しい問題ではないな…。