C: 節約生活 - AtCoder Regular Contest 007
最大10の周期でxoxooxoxxという並びが繰り返す。この周期と同じ周期を幾つか用いて、それぞれ任意の数だけずらして重ねたときに少なくとも1個の○が存在するようにしたい。最小でこの周期を何個使えばいいか。
周期の長さを持つ01bitでoxを表現する。これを幾つかローテーションしてandをとったときに0になる最小の個数を求めればよい。周期は最大10個なので、全探索で十分に間に合う。O(N*2^N)。
最大10の周期でxoxooxoxxという並びが繰り返す。この周期と同じ周期を幾つか用いて、それぞれ任意の数だけずらして重ねたときに少なくとも1個の○が存在するようにしたい。最小でこの周期を何個使えばいいか。
周期の長さを持つ01bitでoxを表現する。これを幾つかローテーションしてandをとったときに0になる最小の個数を求めればよい。周期は最大10個なので、全探索で十分に間に合う。O(N*2^N)。