AtCoder ABC #306 (トヨタ自動車プログラミングコンテスト2023#3) : Ex - Balance Scale

なるほど…。
https://atcoder.jp/contests/abc306/tasks/abc306_h

問題

N個の重りがあり、それぞれの重さを任意に設定できるとする。
M通りの重りの対が指定される。
各対における重さの大小判定の組を考えたとき、何通りの組が構築可能か。

解法

重りに対応するN点の有向グラフを考える。
指定された重りの対に対応する大小関係を有向辺で表すとき、このグラフがDAGであればよいことになる。

点(U,V)の関係は、以下のいずれかとなる。

• U→Vに有向辺がある
• V→Uに有向辺がある
• UとVを縮約する

dp(mask) := 大きい順にmaskに相当する頂点に対応する重りの重さを定めたときの、大小判定の組のあり得る組み合わせ数
とする。同じ重さの重りの集合を、順次maskに追加していくことを考える。

重さの大小関係が異なる重りの組であっても、それが判定対象外の対なら、求める組み合わせの数に影響しない。
これをもとに、包除原理の要領で、そのような多重数え上げを回避しよう。
同じ重さとする重りの集合に対し、その集合内の重りの間の判定組はすべて縮約関係とした場合、連結成分数の偶奇に応じて組み合わせを加減算するとよい。

int N,M;
vector<pair<int,int>> E;

ll dp[1<<17];
const ll mo=998244353;

template<int um> class UF {
	public:
	vector<int> par,rank,cnt,G[um];
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit(int num=um) {int i; FOR(i,num) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<17> uf;

int num[1<<17];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		E.push_back({x-1,y-1});
	}
	
	int mask;
	FOR(mask,1<<N) {
		num[mask]=1^(__builtin_popcount(mask)%2);
		uf.reinit(N);
		FORR2(a,b,E) {
			if((mask&(1<<a))&&(mask&(1<<b))) {
				if(uf[a]!=uf[b]) {
					uf(a,b);
					num[mask]^=1;
				}
			}
		}
	}
	dp[0]=1;
	FOR(mask,1<<N) {
		for(int add=mask;add>0;add=(add-1)&mask) {
			if(num[add]) {
				dp[mask]+=mo-dp[mask^add];
			}
			else {
				dp[mask]+=dp[mask^add];
			}
		}
		dp[mask]%=mo;
	}
	cout<<dp[(1<<N)-1]<<endl;
		
}

まとめ

そこで包除原理を使うのか…って感じ。