Google Code Jam Japan 2011 練習問題A - 平々毎々（アーカイブ）練習問題なら公開してもいいだろう。 問題はこちら。flipflopみたいなSnapperを数珠つなぎした時の出力を求める問題。 問題のサイズを見ると、Largeで1 ≤ N ≤ 30、0 ≤ K ≤ 10^8 なので、O(N * K)なアルゴリズムだと時間がかかってしまう。 そこで頭を使って問題を変換しないといけない。 この手合いであればビット演算でいけるんじゃないかなと予想を立てる。Nは最大で30なので、Nビット整数であればint32に収まる。 というわけで、N=4として、Kを増やしていった時の状態をビット列として書いてみる。 Snapperの状態としては、スイッチのon/offと通電のon/pffがある。そして、i回目のスイッチ状態は、i-1回目のスイッチ状態と通電状態で決まる(xorになる)。 K スイッチ 通電 0 0000 0001 1 0001 0011 2 0010 0001
Download details: Windows Server 2003 Resource Kit Tools
