kmjp's blog

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

Codeforces #491 Div2 F. Concise and clear

これSRMとかで出たらしんどそう。
http://codeforces.com/contest/991/problem/F

問題

整数Nが与えられる。
1000000007→10^9+7のように、加算・乗算・指数演算の記号のみ用いて、Nをより短い文字数で表記せよ。
ただしa^b^cのように指数演算記号を複数連ねることは不可。

解法

幸いサンプルでN=10^10は示してくれているので、N<10^10の場合を考える。
とすると、演算記号を使う場合は9文字以下でなければならない。
以下の場合を列挙しよう。

+を1つも含まない場合

N=A*B^Cの形で表すことになる。
Cは2以上でなければならないので、B,Cを総当たりすればよい。

+を含む場合

文字列表記の文字数より多い桁を表すには指数表記を使うしかない。
よってその場合3文字は必須である。
また、全体で9文字以下なので、+を含むと必ず1つは4文字以下の項ができる。
さらに、4文字以下の指数表記ではA*B^Cの形はとれず、B^Cの形しか取れない。

よって、最初にB^Cの形で4文字以下で表記できる整数を列挙しておこう。
B,Cが高々2ケタなのでこれは容易である。

N=####+(4文字以下)のケース
  1. の右側に来る4ケタ以下の値(Mとする)を総当たりしよう。

左側は(N-M)について、上記+を含まないケースを探せばよい。

N=(4文字以下)+(4文字以下)のケース
N=(3文字)+(3文字)+(1文字)のケース
N=(3文字)*(3文字)+(1文字)のケース

4文字以下のケースは1000通りもないので、これらはそれぞれ総当たりする。

ll V;
unordered_map<ll,string> po;
string ret;


string no_plus(ll v) {
	string ret=to_string(v);
	
	// no plus
	for(ll a=2;a*a<=v;a++) {
		ll b=a*a;
		int c=2;
		while(v%b==0) {
			string s;
			if(v/b>1) s=to_string(v/b)+"*"+to_string(a)+"^"+to_string(c);
			else s=to_string(a)+"^"+to_string(c);
			
			if(s.size()<ret.size()) ret=s;
			
			c++;
			b*=a;
		}
	}
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>V;
	if(V==10000000000LL) return _P("100^5\n");
	ret=no_plus(V);
	
	// 4*4
	for(x=2;x<=99;x++) {
		ll v=1;
		for(y=1;y<=99;y++) {
			v*=x;
			if(v>V) break;
			if(x>=10 && y>=10) break;
			string tmp=to_string(x)+"^"+to_string(y);
			if(po.count(v)==0 || po[v].size()>tmp.size()) po[v]=tmp;
		}
	}
	for(i=0;i<1000;i++) po[i]=to_string(i);
	
	// one plus
	FORR(p,po) {
		ll v=V-p.first;
		if(v>0) {
			string tmp=p.second+"+"+no_plus(v);
			if(tmp.size()<ret.size()) ret=tmp;
		}
	}
	
	// two plus
	FORR(p,po) FORR(p2,po) {
		ll v=V-p.first-p2.first;
		if(po.count(v)) {
			string tmp=p.second+"+"+p2.second;
			if(v) tmp+="+"+po[v];
			if(tmp.size()<ret.size()) ret=tmp;
		}
		v=V-p.first*p2.first;
		if(po.count(v)) {
			string tmp=p.second+"*"+p2.second;
			if(v) tmp+="+"+po[v];
			if(tmp.size()<ret.size()) ret=tmp;
		}
	}
	cout<<ret<<endl;
}

まとめ

N=(3文字)*(3文字)+(1文字) のケースを見逃した。