kmjp's blog

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

Codeforces #687 Div1 A. Bouncing Ball

3完とは言えそこそこいい結果だった回。
https://codeforces.com/contest/1456/problem/A

問題

01で構成された文字列Sと、整数P,Kが与えられる。
Sに対し以下を行える。

  • コストXで、1か所0を1に変える。
  • コストYで、先頭1文字を取り除く

最終的に、S[P+nK-1]がすべて1であるようにしたい。
最小コストを求めよ。

解法

先頭取り除く文字を総当たりしていけばよい。
K文字取り除く文字数を変えるたびに、コストXの数が1変わりうるので差分を更新していこう。

int T;
int N,P,K,X,Y;
string A;
ll step[201010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>P>>K>>A;
		cin>>X>>Y;
		P--;
		FOR(i,2*N) step[i]=0;
		ll mi=1LL<<60;
		for(i=N-1;i>=P;i--) {
			step[i]=step[i+K];
			if(A[i]=='0') step[i]+=X;
			mi=min(mi,1LL*Y*(i-P)+step[i]);
		}
		
		
		cout<<mi<<endl;
		
	}
}

まとめ

解き味も問題設定もさほど面白く感じなかった…残念。