[HackerRank] プログラミングコンテスト復習04 [Week of Code 24:XOR Matrix]

4問目
3問目よりもとっつきやすい問題ではあった。

(解けたとは言ってない。)

03: XOR Matrix

概要

ある規則に従って行列を埋める。
a(i, j) = a(i-1, j) xor a(i-1, j+1)
a(i, n-1) = a(i-1, n-1) xor a(i-1, 0)

方針

幾つか手計算していたら、パスカルの三角形を0と1で計算したものがベースとなっていることがわかった。
そのため、二項係数を短時間で計算するアルゴリズムとしてビットシフト計算やnCrを高速で計算するLucasの定理を作って、試した。
これで解を正しくだせるものの、配列が大きくなる(10⁵)になると配列から取り出しxorを計算する時間がかかりすぎて、指定の計算時間内に終わらない。
その方法がわからず全問正答とはいかず。

結果

Result: Wrong Answer
Score: 5.59pt

最高で23テスト中9テストしか通らず。

考察

10⁵のオーダーでも二項係数を計算するのは短時間で完了した。
計算時間を確認していると、配列から取り出すのに時間がかかるために10秒以内に計算が終わらず。
配列からの取り出しを短縮したいものの取り組み方がわからず、ギブアップとした。

この問題のおかげでビットシフトやLucasの定理など情報工学(?)の面白さを感じれたのが成果か。

コード(失敗作)

一番高得点だったビットシフトのコードを記載

def bit_tri(n):
    bit = 1
    for i in xrange(n-1):
        bit_shift = bit << 1
        bit = bit^bit_shift
    return map(int, format(bit, 'b'))

def get_a(j, n, m, a):
    kei = bit_tri(m)
    index = [i%n for i in xrange(j, j+m)]
    v = 0
    for k, i in zip(kei, index):
        v = v^k*a[i]
    return v

n, m = map(int, raw_input().split())
e = map(int, raw_input().split())
if n<m:
    ans = [0 for i in xrange(n)]
else:
    ans = [get_a(j, n, m, e) for j in xrange(n)]

print ' '.join(map(str, ans))