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 |
3 | 0011 | 0111 |
4 | 0100 | 0001 |
というわけで、スイッチ状態のビット列はKの2進表記となる(数学的な証明は省略する)。さあ、これで答えを出力するのにK回ループする必要がなくなった。
通電状態はどうなるかというと、スイッチ状態がONのSnapperが連続していた場合はその次のSnapperまで通電するから、N回ループする中で連続する1の数を数えてもいい(Nは最大で30なので大したコストではない)。
ただ、この手のビット演算には定石があって、スイッチ状態のビット列に1を足したものと元のビット列とのxorを取ると、通電状態のビット列が求められる。
いくつかのビットパターンで試してみよう。
s | 0000 |
s+1 | 0001 |
(xor) | 0001 |
s | 0110 |
s+1 | 0111 |
(xor) | 0001 |
s | 0100111 |
s+1 | 0101000 |
(xor) | 0001111 |
つまり、1を足すと、最初に0が出てくるところまでのビットが反転するから、xorをとると反転しなかったビットが0になるというわけ。
using System; class Program { static void Main(string[] args) { var head = Console.ReadLine(); var testCount = int.Parse(head); for (var i = 0; i < testCount; i++) { var line = Console.ReadLine().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries); var n = int.Parse(line[0]); var k = int.Parse(line[1]); var result = Solve(n, k); Console.WriteLine("Case #{0}: {1}", i + 1, result ? "ON" : "OFF"); } } private static bool Solve(int n, int k) { int p = k ^ (k + 1); return (p >> n) % 2 == 1; } }