これで通るの意外。
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だと同じ文字の入力とか簡単にリピートできなかったっけ。