yukicoder : No.3221 Count Turns

これはすんなり行けた。
https://yukicoder.me/problems/no/3221

問題

N要素の整数列Aが与えられる。
また、N要素の整数列B,Cがあり初期値はすべて0である。
加えて整数H,Tが与えられる。

以下をT回行った後のCの値を出力せよ。

• Bの最大値がH未満の間、B[i]にA[i]を足すことを繰り返す。
• Bの最大値を取る要素B[i]に対し、C[i]をインクリメントしてB[i]=0とする。

解法

B[i]にA[i]を加算したとき、次にB[i]がH以上となるのは、D[i]回の時だとする。
その時、(D[i], その時のB[i]の値, i)のタプルを考える。第1要素が最小のもののうち、第2要素が最大で、かつ第3要素が最小のものが、C[i]をインクリメントする対象となる。
よって上記タプルをsetで管理しつつ、T回対象を選び、そのつどタプルを更新していけばよい。

int N,H,T;
ll A[101010],R[101010],C[101010];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>H>>T;
	set<array<ll,3>> S;
	ll turn=0;
	FOR(i,N) {
		cin>>A[i];
		R[i]=(H+A[i]-1)/A[i];
		S.insert({R[i],-R[i]*A[i],i});
	}
	
	FOR(i,T) {
		auto v=*S.begin();
		turn=v[0];
		x=v[2];
		S.erase(S.begin());
		C[x]++;
		S.insert({turn+R[x],-R[x]*A[x],x});
	}
	FOR(i,N) cout<<C[i]<<" ";
	cout<<endl;
	
}

まとめ

すんなり行って良かったね。