AtCoder Grand Contest 043 B - 123 Triangle - アルゴリズム忘備録

1,2,3->0,1,2と読み替えて良い。(N>=2、かつ2段目以降は+1分が相殺されるため)

こういう問題はまずは偶奇を見る。

するとパスカルの三角形的に考えて、Σ n-1Ck a[k] の偶奇であることがわかる。これが奇数なら答えは1であることが確定する。

次に偶数のとき、答えは0か2になる。a[i]の中に1が入ってる場合を考えると、0, 1, 2との差分は必ず1か0になる。実験するとわかるが、どこかに2の要素があったとしても1がどこからか近づいてきて2を消す挙動をする。そのため、1がある場合は必ず答えが0である。

次に0, 2のみの場合を考える。これは2->1と読み替えるとさっきの偶奇の問題 Σ n-1Ck a[k] に帰着する。

本番ではnCkの偶奇の計算がTLEして通せず。実はこれは非常に軽い判定法があるらしい。

n == ( r | (n - r) ) ? 1 : 0

これを実装したら通った。計算量はO(N)。