Matsushita's Blog

AtCoder ABC050 C - Lining Up

問題

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


という並びになり、同じ数字が2回登場する(0は1回)。つまり、ある数字が当てはまる箇所は2通り。N個の中から前半の半分が決まれば後半は選択していない方を選んでいく。後半を選択する通り数は1通り。よって、数列が作成できる通り数は2N/2となる。 これをダブリングを用いて計算量O(log N)で算出する。

ソースコード