kmjp's blog

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

Codeforces ECR #016 : E. Generate a String

これで通るの意外。
http://codeforces.com/contest/710/problem/E

問題

キーボードで文字を入力する。
1文字追加または削除するのに共に1文字あたりX秒、コピペで文字数を倍にするのにY秒かかる。
N文字ぴったり入力した状態にするのに最短何秒かかるか。

解法

f(k) := k文字入力するまでの最短時間
とすると、これは以下の遷移で求められる。
f(0) = 0
f(k) = min(f(k-1)+x,f(k+1)+x,f(k/2)+y) (最後の項はkが偶数の時のみ)

一見単なる最短経路問題として解くことができるが、Nの上限が10^7と割と多いため、ダイクストラ法を使うO(N*logN)解法だとTLEする。
状態遷移が単純であることから、自分は以下の解法で通してしまった。

  • 初期状態としてf(0)以外を無限大にし、以下を適当な回数繰り返す
    • k=0~Nに対し、文字を増やす方向の遷移2通りを順に行う。
    • K=N~1と降順で、文字を減らす方向の遷移を順に行う。

こちらもlog(N*logN)解法だが、ダイクストラ法のようにpriority_queueをせわしなく動かしたりしないためか若干軽く、通すことができた。

ll N,X,Y;
ll dp[11000000];
int up[11000000];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X>>Y;
	for(i=0;i<=10000000;i++) dp[i]=1LL<<60;
	dp[0]=0;up[0]=1;
	FOR(x,13) {
		for(j=0;j<2*N;j++) {
			if(j<=N) i=j;
			else i=2*N-j;
			if(up[i]==0) continue;
			up[i]=0;
			if(i && dp[i-1]>dp[i]+X) dp[i-1]=dp[i]+X, up[i-1]=1;
			if(i<N && dp[i+1]>dp[i]+X) dp[i+1]=dp[i]+X, up[i+1]=1;
			
			if(i*2<=N) {
				if(dp[i*2]>dp[i]+Y) dp[i*2]=dp[i]+Y,up[i*2]=1;
			}
			else {
				if(dp[N]>dp[i]+Y+(i*2-N)*X) dp[N]=dp[i]+Y+(i*2-N)*X, up[N]=1;
			}
		}
	}
	
	
	cout<<dp[N]<<endl;
}

問題

viだと同じ文字の入力とか簡単にリピートできなかったっけ。