Codeforces ECR #091 : G. Circular Dungeon

ECRの最終問題の割に、実装は軽め。
https://codeforces.com/contest/1380/problem/G

問題

N個の部屋が円形に並んでいる。
各部屋には宝箱が1個ずつ置かれている。

以下のように部屋を探索することを考える。
初期位置はランダムで決定される。
以後、部屋の宝箱を開き、罠でなければ宝を得て次の部屋へ進む。
罠であれば探索を終了する。

各宝箱に入れる宝の価値が与えられる。
各部屋に置く宝を任意に配置でき、またN個中K個の罠である宝箱を任意に指定できるとする。
K=1～Nの各値について、探索終了までに得られる宝の価値の総和を最小化するように宝と罠を配置したとき、その期待値を求めよ。

解法

価値の高い宝ほど、探索されないことが望ましい。
まず最上位K個の宝を罠として設置する。
最下位K個の宝をその手前に、次の下位K個の宝をその手前に…
と配置していき、各宝箱を通る確率と価値の重みづけ平均を取ろう。

最初に累積和を取れば、各Kに対しO(N/K)で処理できるので、全体でO(NlogN)で計算できる。

int N;
int C[303030];
ll S[303030];
const ll mo=998244353;


ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>C[i];
	sort(C,C+N);
	FOR(i,N) S[i+1]=S[i]+C[i];
	
	ll re=modpow(N);
	
	for(i=1;i<N;i++) {
		int lef=N-i;
		int cur=1;
		ll sum=0;
		while(lef) {
			int num=min(lef,i);
			(sum+=(S[lef]-S[lef-num])%mo*cur)%=mo;
			lef-=num;
			cur++;
		}
		cout<<sum*re%mo<<" ";
	}
	cout<<0<<endl;
	
}

まとめ

ECR最終問の割にシンプルだね。