解説 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

問題のリンク