AtCoder ARC #119 : D - Grid Repainting 3

うーむ。
https://atcoder.jp/contests/arc119/tasks/arc119_d

問題

赤青で塗られたR*Cのグリッドが与えられる。
ここで以下の作業を繰り返す。

• 赤いセルを1つ選び、そのセルを含む列か行のいずれかを、すべて白く塗る

最終的に白いセルの数が最大になる手順を1つ答えよ。

解法

まず、色を塗る作業を別の言い方に置き換えてみる。
行に対応するR点と、列に対応するC点からなる二部グラフを考える。
赤いセルに対し、対応する行に対応する点と列に対応する点の間に辺を張る。

作業とは、辺を1つ以上持つ点を選び、点と辺をまとめて削除することを示す。
もしこのグラフが木である場合、1つ残す頂点を定めると、その点を根とした根付き木とみなしたとき、葉から順に選択することでその点以外をすべて削除できる。

そこで、この問題は以下のように解く。
まず、元のグラフに対し最小全域木を求める。
次に、各連結成分について、列と行どちらに対応する点を残した方が、最後白マス数が増えるか算出する。
その結果に応じて、各連結成分の根となと点を定め、後は葉から順に消していく。

int P,A,B;
ll mo;
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>>P>>A>>B;
	
	if(P==2) {
		cout<<"Yes"<<endl;
		cout<<"1 1"<<endl;
		return;
	}
	
	mo=P;
	set<int> S;
	if(A>1) S.insert(A);
	if(B>1) {
		if(modpow(B)!=A) S.insert(B);
	}
	
	FORR(x,S) {
		ll cur=1;
		FOR(i,P-2) {
			cur=cur*x%mo;
			if(cur==1) break;
		}
		if(i==P-2) {
			cout<<"Yes"<<endl;
			cur=1;
			FOR(i,P) {
				cout<<cur<<" ";
				cur=cur*x%mo;
			}
			cout<<endl;
			return;
		}
	}
	if(S.size()<=1) {
		cout<<"No"<<endl;
		return;
	}
	int x1=*S.begin();
	int x2=*S.rbegin();
	int r1=modpow(x1);
	int r2=modpow(x2);
	set<ll> T[2];
	vector<ll> V[2];
	
	FOR(j,2) {
		ll cur=1;
		V[j].push_back(1);
		FOR(i,P) {
			if(j==0) cur=cur*x1%mo;
			else cur=cur*x2%mo;
			if(cur==1) break;
			T[j].insert(cur);
			V[j].push_back(cur);
		}
	}
	
	FOR(k,2) {
		for(int tl=2;tl<=V[0].size();tl+=2) if((P-1)%tl==0) {
			int tw=(P-1)/tl;
			if(tw>V[1].size()) continue;
			
			vector<ll> R;
			set<ll> A;
			ll cur=1;
			FOR(y,tl) {
				R.push_back(cur);
				A.insert(cur);
				if(y<tl-1) cur=cur*x1%mo;
			}
			cur=cur*x2%mo;
			for(y=tl-1;y>=0;y--) {
				if(R.size()!=A.size()) break;
				FOR(x,tw-1) {
					R.push_back(cur);
					A.insert(cur);
					if(R.size()!=A.size()) break;
					if(x<tw-2) {
						if(y%2==1) {
							cur=cur*x2%mo;
						}
						else {
							cur=cur*r2%mo;
						}
					}
				}
				if(y) cur=cur*r1%mo;
			}
			if(A.size()==P-1) {
				R.push_back(1);
				cout<<"Yes"<<endl;
				FORR(r,R) cout<<r<<" ";
				cout<<endl;
				return;
			}
			
		}
		swap(x1,x2);
		swap(r1,r2);
		swap(T[0],T[1]);
		swap(V[0],V[1]);
	}
	
	cout<<"No"<<endl;
}

まとめ

うーん、これは解けておきたかった。