Zenn
🦁

ABC348Fのbitset解について

2024/04/24に公開
C++
競プロ
idea

ABC348Fのbitset解がよくわからなかった

bitsetを用いた問題を解けたことがなく、解説を見ても意味不明だったので、少しずつステップを踏んで解説を理解することにした。

愚直解

void solve(){
	int n, m;
	cin >> n >> m;
	vector<vector<int>> a(n, vector<int>(m));
	rep(i, n)rep(j, m){
		cin >> a[i][j];
	}
	int ans = 0;
	rep(i, n){
		for(int j =i+1;j < n;j++){
			int cnt = 0;
			rep(k, m){
				if(a[i][k] == a[j][k])cnt++;
			}
			if(cnt % 2){
				ans++;
			}
		}
	}

	cout << ans << endl;
}

提出(TLE)

まずは愚直解から始めてみる。さすがにここはわかる。

ansの表現を行列の形式に寄せる

ans_{i, j} = \left\{ \begin{array}{} 1 & (A_i \text{ is similar to } A_j) \\ 0 & (otherwise) \end{array} \right.

ansが何を表しているのかよくわからなかったので、出力パートから逆算してみた。

void solve(){
	int n, m;
	cin >> n >> m;
	vector<vector<int>> a(n, vector<int>(m));
	rep(i, n)rep(j, m){
		cin >> a[i][j];
	}
	vector ans(n, vector(n, false));
	rep(i, n){
		rep(j, n){
			int cnt = 0;
			rep(k, m){
				if(a[i][k] == a[j][k])cnt++;
			}
			if(cnt % 2){
				ans[i][j] = true;
			}
		}
	}

	int ans_val = 0;
	rep(i, n){
		rep(j, n){
			ans_val += ans[i][j];
		}
		if(m%2){
			// mが奇数の場合、i番目とi番目について、X_i = X_i となる個数が奇数となる
			ans_val--;
		}
	}
	cout << ans_val / 2 << endl;
}

提出(TLE)

ansをbitsetに変更

やるだけ。

void solve(){
	int n, m;
	cin >> n >> m;
	vector<vector<int>> a(n, vector<int>(m));
	rep(i, n)rep(j, m){
		cin >> a[i][j];
	}
	vector<bitset<2000>> ans(n);
	rep(i, n){
		rep(j, n){
			int cnt = 0;
			rep(k, m){
				if(a[i][k] == a[j][k])cnt++;
			}
			if(cnt % 2){
				ans[i].set(j);
			}
		}
	}

	int ans_val = 0;
	rep(i, n){
		ans_val += ans[i].count();
		if(m%2){
			// mが奇数の場合、i番目とi番目について、X_i = X_i となる個数が奇数となる
			ans_val--;
		}
	}
	cout << ans_val / 2 << endl;
}

提出(TLE)

解説のアルゴリズム

j 番目を見るたびに、逐次 ans_{i,k} を更新していくことを考える。ans_{i, k} は、似ている個数を持つ必要は無く、似ている個数の偶奇だけを持てばよいので、bitsetの1要素（\simeq 1bit ?）で表現することができる。

具体的には、

  1. j 番目に値 X が登場する i の集合 appeared (解説 の bs) を O(N) で計算する
  2. 各 i(i = 1, 2, \cdots , N) について、ans_{i, k} の状態を更新する
    • ans_{i, k} が「似ている個数」を持ってると考えたとき、要素数分足す必要があり、これだとTLE（愚直解）
    • 必要なのが最終的な「似ている個数の 偶奇 」であればいいことを考えると、これは bitwise XOR で加算を表現できる。（この時に、bitsetの性質で約 64 倍高速化することが可能となっている）
void solve(){
	int n, m;
	cin >> n >> m;
	vector<vector<int>> a(n, vector<int>(m));
	rep(i, n)rep(j, m){
		cin >> a[i][j];
	}
	// ans[i] := j 番目まで見たときに、 i番目と同じ数の項の個数の偶奇が奇数となっている各A_k (k = 1, 2, ..., N)について、k番目のビットが立っている
	vector<bitset<2000>> ans(n);
	rep(j, m){
		vector<bitset<2000>> appeared(1000);
		rep(i, n){
			appeared[a[i][j]].set(i);
		}
		rep(i, n){
			ans[i] ^= appeared[a[i][j]];
		}
	}

	int ans_val = 0;
	rep(i, n){
		ans_val += ans[i].count();
		if(m%2){
			// mが奇数の場合、i番目とi番目について、X_i = X_i となる個数が奇数となる
			ans_val--;
		}
	}
	cout << ans_val / 2 << endl;
}

提出(AC,225ms)

感想

コンテスト直後は、bitsetを知らなかったから解かなかったものだと思い込んでいたけれども、「どの状態をどのように表現するか」について考えられないと解けないものだと分かった（単に劇薬的なアルゴリズムではなかった点については少しだけ安心できた？）。

Discussion