yukicoder : No.2230 Good Omen of White Lotus

これも割と典型？
https://yukicoder.me/problems/no/2230

問題

H*Wのグリッドがある。
各セルでは、それぞれ1/Pの確率で白い花が咲く。
ただし、指定されたN個のセルでは、2/Pの確率で白い花が咲く。
各セルに花が咲いているかどうかは事前に知ることはできない。

左上のセルから、右または下の隣接セルをたどることを繰り返し、右下セルに移動することを考える。
最適な移動経路を取ったとき、白い花の咲いたセルを1個でも通る確率の最大値を求めよ。

解法

N個の指定セルをできるだけ多く通ればよい。
指定セルをrow-major orderで並べ変え、順にそのセルを通るときの最大指定セル通過数を数え上げよう。
区間最大値を取れるSegTreeで、columnごとに通過数最大値を更新していけばよい。

もし最大n個の指定セルを通れる場合、花の咲きうるセル数をm=H+W-3として、1-(1-1/P)^(m-n)*(1-2/P)^nが解。

int H,W,N,P;
vector<pair<int,int>> V;

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=0;
	V comp(V l,V r){ return max(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=comp(v,val[entry]); //上書きかチェック
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_1<int,1<<20> st;
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>>H>>W>>N>>P;
	FOR(i,N) {
		cin>>x>>y;
		V.push_back({x,y});
	}
	sort(ALL(V));
	int ma=0;
	FORR2(x,y,V) {
		k=st.getval(0,y+1)+1;
		ma=max(ma,k);
		st.update(y,k);
	}
	
	int ng=H+W-3-ma;
	//全部アウト
	ll ret=1;
	FOR(i,ma) ret=ret*(mo+1-2*modpow(P)%mo)%mo;
	FOR(i,ng) ret=ret*(mo+1-modpow(P)%mo)%mo;
	
	cout<<(mo+1-ret)%mo<<endl;
	
}

まとめ

全移動パターンの期待値でもいいような気がけど、どっちが簡単だろ。