kmjp's blog

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

Codeforces #392 Div2 D. Ability To Convert

雑すぎた。
http://codeforces.com/contest/758/problem/D

問題

整数Nと数字から構成された文字列Sが与えられる。
Sを分割し、いくつかのN以下の整数となるようにする。
そうして得られたいくつかの整数を、N進数の各桁の値とみなし、その値を改めて10進数表記に直す、という手順を考える。
得られる値の最小値を求めよ。

解法

以下の状態を考える。
f(i) := Sの先頭i文字に関し、問題の手順で得られる値の最小値

以下の要領でf(i)をDPで順次もとめていけばよい。
途中で10^18を超えるケースに注意。
f(i+x) = min(f(i)*N + int(S[(i+1)..(i+x)]))

ll N,L;
string S;

ll dp[1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	L=S.size();
	
	FOR(i,L+5) dp[i]=1LL<<60;
	
	dp[0]=0;
	FOR(i,L) if(dp[i]<1LL<<60) {
		ll a=0;
		for(x=i;x<L;x++) {
			a=a*10+S[x]-'0';
			if(a>=N) break;
			if(dp[i]*N/N == dp[i]) dp[x+1]=min(dp[x+1],dp[i]*N+a);
			if(S[i]=='0') break;
		}
	}
	cout<<dp[L]<<endl;
}

まとめ

計算量的にはもっと桁数多くてもよさそうだけど、10^18の制限があるから抑えたのかな。