kmjp's blog

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

AtCoder ABC #238 (モノグサプログラミングコンテスト2022) : Ex - Removing People

近いところまで考察できていたのに、詰め切れず…。
https://atcoder.jp/contests/abc238/tasks/abc238_h

問題

N人の人が距離1ずつ離れて等間隔で円環状に並んでいる。
各人時計回りか反時計回りいずれかを向いており、その向きは入力として与えられる。

以下の処理を行うとき、手順はN!通りあるが、コストの総和の期待値を求めよ。

  • 残った人が2人以上いる場合、そのうちだれかを等確率で選ぶ。
    • 選んだ人の向いている向きの先にいる最寄りの人を取り除く。
    • その際、取り除いた人までの距離をコストとする。

解法

人を取り除く手順を考えると、同じ人が複数回選ばれたりしてややこしい。
逆に、1人の状態から巻き戻すことを考えよう。
以下の2関数を考える。なお、人の番号は適宜Nで割った余りで考えると楽。

f(L,R) := L番とR番の人が円環状に配置済みで、その間に人がいないような状態に対する、その後の中の人の埋め方の組み合わせ
g(L,R) := (同上)な状態に対する、その後の中の人の埋め方におけるコストの総和

最後に残る人xを総当たりし、g(x,x+N)の総和を取ってN!で割れば解となる。
あとはf(L,R)とg(L,R)を求めよう。

  • L+1=Rなら、間に人はいないのでf(L,R)=1, g(L,R)=0
  • そうでない場合、次に埋まる人Mを総当たりする。MはL番とR番どちらの人に消されるかを考えると、
    • M番がL番とR番どちらに消されうるかをc通り、それぞれのコストの総和をdとすると、以下で計算できる。
    • f(L,R) += f(L,M)*f(M,R)*c*Comb(R-L-2, M-L-1)
    • g(L,R) += (f(L,M)*f(M,R)*d + c*(f(L,M)*g(M,R) + g(L,M)*f(M,R)))*Comb(R-L-2, M-L-1)
int N;
string S;
const ll mo=998244353;
const int NUM_=400001;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];

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;
}

ll comb(ll N_, ll C_) {
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}
ll hcomb(ll P_,ll Q_) { return (P_==0&&Q_==0)?1:comb(P_+Q_-1,Q_);}

ll pat[603][603];
ll sum[603][603];

ll dfs(int L,int R) {
	if(pat[L][R]>=0) {
		return sum[L][R];
	}
	
	ll& p=pat[L][R];
	ll& s=sum[L][R];
	p=s=0;
	
	if(L+1==R) {
		p=1;
	}
	else {
		for(int M=L+1;M<R;M++) {
			int pa=(S[L]=='R')+(S[R]=='L');
			int co=(S[L]=='R'?M-L:0)+(S[R]=='L'?R-M:0);
			dfs(L,M);
			dfs(M,R);
			(p+=pat[L][M]*pat[M][R]*pa%mo*comb(R-L-2,M-L-1))%=mo;
			(s+=(pat[L][M]*pat[M][R]%mo*co+pa*pat[L][M]*sum[M][R]+pa*sum[L][M]*pat[M][R])%mo*comb(R-L-2,M-L-1))%=mo;
		}
	}
	return s;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	inv[1]=fact[0]=factr[0]=1;
	for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
	for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;

	cin>>N>>S;
	S+=S;
	
	MINUS(pat);
	
	ll ret=0;
	FOR(x,N) ret+=dfs(x,x+N);
	ret=ret%mo*factr[N]%mo;
	cout<<ret<<endl;
	
}

まとめ

逆順に巻き戻すことも、間を埋めることも考えられたのに、その際の組み合わせ計算を詰め切れなかったのが残念。