SRM 642 Div2 Medium LightSwitchingPuzzle

問題

SRM 642 - TopCoder Wiki

N個のライトが一列に並んでいて,onとoffの状態がある. i番目のライトのスイッチを押すとi2*i3*iのライトも同時にon, offが切り替わる. 今,全てのライトを消したい時,スイッチを押す最小回数を求める問題.

解答

  • 1番目のライトがついていた時,消す方法は,1番目のスイッチを押すしかない.
  • 2番目のライト以降についても同様のことが言える.
  • つまり,先頭から順にスイッチを押すかどうか判定していくことで最小の回数を求めることが出来る.
class LightSwitchingPuzzle
{
public:
  int n;
  vector<bool> s;
  int calc(int idx) {
    // for (auto c:s) cout << c << ", ";
    // cout << endl;
    if (idx > n) return 0;
    if (s[idx-1]) {
      for (int i = 1; i * idx <= n; i++) {
        s[i * idx-1] = !s[i * idx-1];
      }
      return 1 + calc(idx+1);
    }else {
      return calc(idx + 1);
    }
  }
  int minFlips(string state)
    {
      n = state.size();
      for (auto x:state) {
        if (x == 'Y') s.push_back(true);
        else s.push_back(false);
      }
      return calc(1);
    }
};