yukicoder : No.2146 2 Pows

これは言い換えが賢いな。
https://yukicoder.me/problems/no/2146

問題

2のべき乗の整数からなるmultiset Sを考える。
Sのコストは、要素数をx、ユニークな要素の種類数をy、最大値を2^zとすると、定数A,B,Cを用いてAx+By+Czとする。
Sの和をNで割った場合の余りがkになるようなSのコストの最小値を、各kに対し求めよ。

解法

Sは以下を繰り返して構築できる。

• 要素1を追加する。その際コストはA加算される。また、この操作を2回以上連続していない場合、さらにB加算される。
• 既存の要素をすべて2倍する。その際コストはC加算される。

となると、Sの具体的な値を覚えておく必要はなく、Sの総和と、前回前者の操作を行ったかどうかを覚えておけばよい。

f(s,f) := 和をNで割った余りがsで、かつ直前に前者の操作を行ったかどうかを真偽値fで表したとき、そのようなSの状態のうち最小コスト
とする。
考えるべき状態は高々2N通りで、状態遷移は2通り。
あとはダイクストラ法で各状態のコスト最小値を求めよう。

int N,A,B,C;
ll dp[202020][2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>A>>B>>C;
	FOR(i,N) dp[i][0]=dp[i][1]=1LL<<60;
	priority_queue<pair<ll,int>> Q;
	dp[1][1]=A+B;
	Q.push({-dp[1][1],3});
	while(Q.size()) {
		ll co=-Q.top().first;
		int cur=Q.top().second/2;
		int one=Q.top().second%2;
		Q.pop();
		if(dp[cur][one]!=co) continue;
		
		// add 1
		if(chmin(dp[(cur+1)%N][1],co+A+(one?0:B))) {
			Q.push({-dp[(cur+1)%N][1],((cur+1)%N)*2+1});
		}
		// mult 2
		if(chmin(dp[(cur*2)%N][0],co+C)) {
			Q.push({-dp[(cur*2)%N][0],((cur*2)%N)*2+0});
		}
	}
	FOR(i,N) cout<<min(dp[i][0],dp[i][1])<<endl;
}

まとめ

Sの構築法を思いつけば、コードは短いね。