SRM569 Div1 Easy - TheDevice
ちょっと面白かった
問題
長さmのビット列がn個ある
これらのうち2個を選んで機械に入れると、各ビットごとにそれらのor / and / xor和のどれかを計算して出してくれる
この機械の各ビットがor / and / xor和のどれを出しているのか特定したい
今あるn個のビット列だけで特定できないこともある
特定するために追加する必要のあるビット列の個数の最小値を求めよ
1 <= n <= 50
1 <= m <= 50
解法
01 -> 0ならand, 1ならorかxor
11 -> 0ならxor, 1ならorかand
というように特定できるから、試す必要のあるビットの組み合わせはこの2通り
よってiビット目を特定するために
・iビット目が0の列が最低1個
・iビット目が1の列が最低2個
これだけ必要になる
ビットごとに足りない列の個数を求め、それらの最大値が答えになる
class TheDevice { public: int minimumAdditional(vector<string> s) { int n = s.size(), m = s[0].size(), x[55] = {}, y[55] = {}; rep(i,n) rep(j,m) (s[i][j]=='0' ? x : y)[j]++; int res = 0; rep(i,m) chmax(res, max(1-x[i],0) + max(2-y[i],0)); return res; } };
https://community.topcoder.com/stat?c=problem_statement&pm=12388&rd=15489