問題
C: Lining Up - AtCoder Beginner Contest 050 | AtCoder
解法
「自分の左に並んでいた人数と自分の右に並んでいた人数の差の絶対値」の並びを見てみる。
N = 5 の時
4, 2, 0, 2, 4
N = 8 の時
7, 5, 3, 1, 1, 3, 5, 7
という並びになり、同じ数字が２回登場する(0は１回)。つまり、ある数字が当てはまる箇所は２通り。N個の中から前半の半分が決まれば後半は選択していない方を選んでいく。後半を選択する通り数は１通り。よって、数列が作成できる通り数は2N/2となる。 これをダブリングを用いて計算量O(log N)で算出する。
