JOI 2022/2023 春季トレーニング Day 2
議会 (Council) 解説
解説担当 : tatyam

1

問題概要

人の人がいて， 個の案に投票を行う．のとき，人 は案 に賛成票を投じる．
について，以下の問題を解け．
を選び，人 と人 を投票から除外する．
過半数 (票以上) の賛成票を獲得する案の個数の最大値は？
2

小課題 (JOI)

番号 配点
1. 点
2. 点
3. 点
4. 点
5. 点
6. 点
7. 点

制約

計算量の例

3

小課題 (JOIG)

番号 配点
1. 点
2. 点
3. 点
4. 点
5. 点
6. 点
7. 点

制約

計算量の例

4

小課題

小課題くらいの計算量で解けば良い．

5

小課題

小課題くらいの計算量で解けば良い．
議長 を全探索 :副議長 を全探索 :それぞれの案に何票集まったかを集計 :全部合わせて6

小課題

小課題議長 を全探索 :副議長 を全探索 :それぞれの案に何票集まったかを集計 :議長と副議長の 人しか変わらないのに，毎回集計し直すのは無駄！
7

小課題

小課題

それぞれの案に何票集まっているかを前計算 :その後，議長 を全探索 :副議長 を全探索 :議長と副議長の分を取り除く :全部合わせて8

小課題

小課題

それぞれの案に何票集まっているかを前計算 :その後，議長 を全探索 :副議長 を全探索 :議長と副議長の分を取り除く :全部合わせて9

小課題

実装テクニック : 整数をビット列として扱おう

ビット演算 | & ^ << >> を使って，整数をビット列として扱うことができる．
議長と副議長を決めたときに，成立する案の個数をで求めていたが，これをにできる．
10

小課題

実装テクニック : 整数をビット列として扱おうをビット列で入力する

vector<int> A(N);
for(int i = 0; i < N; i++) for(int j = 0; j < M; j++) {int a;
cin >> a;A[i] |= a << j;}

11

小課題

考察

各案は議長・副議長に関わらず可決議長・副議長のどちらかが反対なら可決議長・副議長の両方が反対なら可決議長・副議長に関わらず否決の 通りに分けられる．そのうち中央の つのみが重要である．
12

小課題

実装テクニック : 整数をビット列として扱おう
可決票数 票以上の賛成票を得ている案の集合
可決票数 票の賛成票を得ている案の集合
可決票数 票の賛成票を得ている案の集合をそれぞれ整数で持つ
for(int j = 0; j < M; j++) {if(vote[j] >= N / 2 + 2) two |= 1 << j;if(vote[j] == N / 2 + 1) one |= 1 << j;if(vote[j] == N / 2) zero |= 1 << j;}

13

小課題

実装テクニック : 整数をビット列として扱おう
議長 と副議長 を決めたら，可決される案の集合がで求められる

int accept = two | one & ~(A[i] & A[j]) | zero & ~(A[i] | A[j]);あとは，これの立っているビットの個数を数えれば良い．
14

小課題

popcount

C++20
どうして…

15

小課題

popcount
std::bitset::countを使う

int popcnt(int x) { return bitset<32>(x).count(); }__builtin_popcountを使う

int popcnt(int x) { return __builtin_popcount(x); }これらは通常賢いビット演算をしている __popcountdi2 にコンパイルされるが，今回はコンパイルオプションに -march=native が指定されていたので，POPCNT 命令にコンパイルされる
16

小課題

popcount

自分で実装する

int popcnt(int x) {int ans = 0;
while(x) {ans += x & 1;
x >>= 1;}
return ans;}

計算量は
17

小課題

popcount

全部前計算しておく

int popcnt(int x) {static array<int, 1 << 20> table = []{//}();
return table[x];
}

前計算する

計算量は
18

小課題

クイズ

どっちが速い？

[A][B]

int popcnt(int x) {int ans = 0;
while(x) {ans += x & 1;
x >>= 1;}
return ans;}

int popcnt(int x) {static array<int, 1 << 20> table = []{//}();
return table[x];}計算量は前計算する計算量は19

小課題

答え[A]

int popcnt(int x) {int ans = 0;
while(x) {ans += x & 1;
x >>= 1;}
return ans;}

キャッシュの効かないメモリアクセスは，ビット演算や足し算に比べて非常に遅い！！

計算量は
20

小課題

popcnt

賢いビット演算int popcnt(int x) {x = (x & 0x55555555) + (x >> 1 & 0x55555555);
x = (x & 0x33333333) + (x >> 2 & 0x33333333);
x = (x & 0x0f0f0f0f) + (x >> 4 & 0x0f0f0f0f);
x = (x & 0x00ff00ff) + (x >> 8 & 0x00ff00ff);
return (x & 0x0000ffff) + (x >> 16);
}

計算量は
21

小課題

小課題
なんとる．のとき，の 種類のタイプの人間がい

22

小課題

こんな例を考える．
人
人
人
人
人
合計

案 案

可決票数 : 票

23

小課題

人 が議長の場合と人 が議長の場合で，状況が全く同じ．
案 案
案 案
人
人
人
人
人
人
人
人
合計
合計
つまり，答えも同じ．
24

小課題

結局，「議長と副議長が 種類のタイプのうちどのタイプの人間か？」が分かれば可決される案も分かる．
副議長が :
議長が :この種類を調べれば良い．
25

小課題

小課題

が小さめ

なので，同じタイプの人間を圧縮することでを小さくできる．
小課題 で通りを調べたのと同様に，を全部調べることができる．
計算量は通り

26

小課題

小課題

どうにかして計算量をにしたい．

27

小課題

小課題

を決めたとき，可決される案の集合は以下のように計算された．

accept := two | one & ~(A[i] & A[j]) | zero & ~(A[i] | A[j])ここで を固定すると，によって可決されるか変わる案 (可決票数 票)に関わらず可決される案 (可決票数 票以上)の つを持てば良い．
28

小課題

小課題

を固定すると，によって可決されるか変わる案 (可決票数 票)に関わらず可決される案 (可決票数 票以上)の つを持てば良い．
ONE := two | (one & ~A[i])ZERO := (one & A[i]) | (zero & ~A[i])accept := ONE | (ZERO & ~A[j])

29

小課題

小課題
accept := ONE | (ZERO & ~A[j])を最大化したい．
つまり， popcnt(ZERO & ~A[j]) を最大化したい．
案の全体集合を ZERO に絞ったときの， の個数が (人 を除いて) 最も多い人を探したい．
popcnt(accept)

30

小課題

小課題

すべてのであるようなの組 ( 個) について，以下が求まれば良い．に含まれる案に反対で，に含まれる案に賛成であるような人の数 (に含まれない案については 賛成 / 反対 どちらでもよい)
これは，高速ゼータ変換 ( 次元累積和) をして，の部分だけ戻すことを全てのについて行えば，時間になる．
31

小課題

小課題

高速ゼータ変換をどうにかして計算量をにしたい．

32

小課題

小課題
accept := ONE | (ZERO & ~A[j])→ わかりやすさのため A[j] を反転させておく．

各に対し，を求める問題である．
33

小課題

小課題の制約が面倒なので，一旦忘れるととなる．
34

小課題

をまで減らしたときの集合の大きさ (popcount) の最大値であるので，各 から要素を減らしていったときに現れる集合を前計算しておく．
これは下位集合への累積 OR ででできる．問題はとなった．
35

小課題

今度は，各 から要素を増やしていって，まで増やしたときの元々の集合の大きさ (popcount) の最大値という問題である．
したがって，上位集合への chmax をすることで，各に対する答えがで求められる．
36

小課題

まとめの制約を忘れると，
1. bool 配列 dp1[a] を作る
2. 各 に対し， dp1[A[j]] に を代入
3. 下位集合に累積 OR
4. int 配列 dp2[b] を作る
5. 各 に対し， dp1[b] == 1 であれば， dp2[b] に popcnt(b) を代入
6. 上位集合に累積 chmax
自分自身の分を取り除くには？
37

小課題

自分自身の分を取り除くには？
→ 個数を数えれば良い！
1. int 配列 dp1[a] を作る
2. 各 に対し， dp1[A[j]] に を加算
3. 下位集合に累積和
4. int 配列 dp2[k][b] を作る (popcount の値ごとに個数を数える)
5. 各 に対し， dp2[popcnt(b)][b] に dp1[b] を加算
6. popcount の値ごとに，上位集合に累積和
38

小課題

自分自身の分を取り除くには？
1. int 配列 dp1[a] を作る
2. 各 に対し， dp1[A[j]] に を加算
3. 下位集合に累積和
4. int 配列 dp2[k][b] を作る (popcount の値ごとに個数を数える)
5. 各 に対し， dp2[popcnt(b)][b] に dp1[b] を加算
6. popcount の値ごとに，上位集合に累積和自分自身の影響は簡単に数えられるので，その分を引けば良い．
計算量はにもなりますが，省略します．

39

統計情報

統計情報(JOI)点数

O O O O O O OO O O O O - O O O O - - O - O O - - O O O - - - O O - - - - - - - - - - -人数 累積人数

40

統計情報

統計情報

(JOIG)点数O O O O - - O O O - - - O O - - - - -人数 累積人数41