AtCoder Regular Contest 007 C - 節約生活
February 11, 2023文字数を\(n\)とすると複数のテレビを組合せたときの視聴パターンの重ね方は\(2^n\)個ある。 最大文字数は整数型のビット数より数分の1しかないので、ビット操作ですべての重ね方を試行することを考える。 各重ね方について、パターンを十分に連結した値の論理和に最大文字数以上連続する1があれば、その試行は要件を満たす。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#ifdef ONLINE_JUDGE
int main() {
string s;
cin >> s;
ll mask = 0;
int n = s.size();
for (int i = n - 1; i >= 0; i--) {
mask = mask << 1;
if (s[i] == 'o')
mask += 1;
}
mask = (mask << (2 * n)) | (mask << n) | mask;
int result = 10;
rep(i, 1 << n) {
ll temp = 0;
int count = 0;
rep(j, n) {
if (i & (1 << j)) {
count++;
temp |= (mask << j);
}
}
if (((temp >> (n * 2)) & ((1 << n) - 1)) == (1 << n) - 1) {
result = min(result, count);
}
}
cout << result << endl;
return 0;
}
#endif
問題のリンク