問題概要
直線上に並んだ 個の電灯がある．電灯は端から順に，
と番号付けられていて，各電灯はオンまたはオフの二つの状態のいずれかをとる．
Leo は，全ての電灯をオフにしたい．Leo は 個のスイッチをもっていて，電灯と同様に
と番号付けられている．
番のスイッチを押したとき，
の番号をもつ電灯の状態が切り替わる．
電灯の初期状態を表す文字列 が与えられる．
は 'Y', 'N' の 2 種類の文字からなり，
が 'Y' のとき，
番の電灯の状態がオンであることを表し，'N' のときはオフであることを表す．
Leo が全ての電灯をオフにするために，少なくとも何回スイッチを押す必要があるか，求めよ．
解法
同じスイッチを 2 回押したとき， 1 回目に押したときの変化分が元に戻るだけなので，同じスイッチを 2 回以上押す行為に意味はありません．従って，問題は，「押さなければならないスイッチの個数を求めよ」と言い換えられます．
では，押さなければならないスイッチとはどのようなスイッチであるか考えていきます．まず，状態がオンである電灯の内，最も番号の小さい電灯の番号を とおきます．この電灯をオフにすることができるスイッチは，
の約数である番号をもつスイッチです．そのような番号の内，
と異なるものの 1 つを
とします（すなわち，
です）．スイッチ
を押して電灯
をオフにしたとします．このとき，仮定より，電灯
の状態はオンになります．電灯
を再びオフにするためには
の約数である番号をもつスイッチを操作する必要がありますが，そのような値は
の約数でもあるので，スイッチ
の操作によって変化した状態が全て元に戻ってしまいます．従って，
未満の番号をもつスイッチを操作しても無駄であり，電灯
をオフにするためにはスイッチ
を操作しなければならないことが分かります．
以上のことを繰り返し適用すると，オンであるような電灯が残っている間，その内最小の番号をもつ電灯に対応するスイッチを押すというアルゴリズムが得られます．スイッチの操作のシミュレートに一回あたり かかり，スイッチを押す回数も
であるので，このアルゴリズムは
時間で実行できます．
コード
using VI = vector< int >; using VVI = vector< VI >; #define REP( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i ) #define ALL( c ) ( c ).begin(), ( c ).end() #define BI back_inserter class LightSwitchingPuzzle { public: int minFlips( string state ) { const int N = state.size(); VI as; transform( ALL( state ), BI( as ), bind( equal_to< char >(), _1, 'Y' ) ); int res = 0; REP( i, 1, N + 1 ) { if ( !as[ i - 1 ] ) { continue; } ++res; for ( int j = 1; i * j <= N; ++j ) { as[ i * j - 1 ] ^= 1; } } return res; } };
