https://atcoder.jp/contests/zone2021/tasks/zone2021_c
前提知識
解説
https://atcoder.jp/contests/zone2021/submissions/22237545
二分探索で解く。
この部分に気が付くのが第一関門だが、自分もやっとやっと気が付いたので考察過程が共有できない。
「最小値の最大値」という問題（逆だっけ？）は二分探索で解けるという定石からひねり出した。
二分探索
いかに二分探索で解くかであるが、今回の問題は「チームの総合力としてありえる最大値」を求めよなので、
「チームの総合力がとある数値以上にできるか」という部分問題を解くことにする。
check(lim) := チームの総合力がlim以上にできるか
これが単調性を持つかは証明していないが、4以上にできるのなら5以上にできるのであってる。
check関数
この中身をどう書いていくかが問題。
チームの総合力がlim以上であるということは、チーム全体のパワー・スピード・テクニック・知識・発想力の最小値がすべてlim以上ということになる。
ここからパワーだけを考えると、3人選んだ時にパワーがlim以上であるメンバーが少なくとも1人いればいいことになる。
ここまでbreakdownして考えると、重要なのは、「lim以上であるか」どうかだけであることが分かり、それ以外の情報は考慮されない。
なので、各メンバーの各能力について、lim以上であるかどうかという観点で情報を圧縮しておく。
cnt[msk] := 能力についてlim以上であるかなら1, そうでないなら0で5bitの集合を作ったとき、能力集合がmskとなる人物の人数
このようにビットを使って人物を抽象化できる。
こうすると、「3人選んでチーム全体のパワー・スピード・テクニック・知識・発想力の最小値がすべてlim以上」というのは、
mskを3つ選んでORしたときに11111となる組合せがあるかどうかということに帰着させることができる。
この帰着が一番難しいので、よく考えてみてほしい。
少なくとも1人いればいいというのをORで表現している。
あとは、mskを3つ選ぶという行為は状態を圧縮しているので00000-11111で3つ選べばいいので全探索可能。
1人ですべてOKな場合とかもあるので、ちょっと注意しつつ実装すればAC。
int N, X[3030][5]; //--------------------------------------------------------------------------------------------------- int getMask(int i, int lim) { int res = 0; rep(j, 0, 5) if (lim <= X[i][j]) res += 1 << j; return res; } //--------------------------------------------------------------------------------------------------- int cnt[1 << 5]; bool check(int lim) { rep(i, 0, 1 << 5) cnt[i] = 0; rep(i, 0, N) cnt[getMask(i, lim)]++; rep(msk1, 0, 1 << 5) rep(msk2, 0, 1 << 5) rep(msk3, 0, 1 << 5) { if ((msk1 | msk2 | msk3) == (1 << 5) - 1 && 0 < cnt[msk1] && 0 < cnt[msk2] && 0 < cnt[msk3]) return true; } return false; } //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; rep(i, 0, N) rep(j, 0, 5) cin >> X[i][j]; int ok = 0, ng = inf; while (ok + 1 != ng) { int md = (ok + ng) / 2; if (check(md)) ok = md; else ng = md; } cout << ok << endl; }
