Google Code Jam 2020 round1A-Pascal Walk

codingcompetitions.withgoogle.com
実装は時間があれば書きます（）
問題
「パスカルの三角形の最上段の頂点からスタートし、移動先に書かれた数字を足していったとき、和がNとなるような移動方法を答えよ。
ただし、同じ場所に2回移動することはできず、移動可能なのはパスカルの三角形内で隣接している場所に限る。」

パスカルの三角形は下図のようなもので、最上段を0段、ある段の数字を左から0個目、1個目、、、と数えるとしたとき、
n段目の左からk個目の数字はnCkとなります。

解法は大きく分けて二つあります（ツイッター見て分かりました）

解法１．
n段目の数をすべて足した和が、nC0+nC1+...+nCn=2^nとなることを利用します。
作りたい数pがあったときに、pを2進数表示すると1001011であるとしましょう。
すると、ビットが立っている場所に対応する段の数字をすべて集めていけば良いと分かります。
しかし、集める必要が無い段についても、その段を通過するときに1を集めなければいけません（下図）。

したがって、
N＝（ビットが立っている段の数字をすべて足したもの）＋（ビットが立っていない段を通過するときに足した1）
となります。なので、あらかじめ（通過する必要がある段の数の最大値M）を求めておき、N-Mを2進数表示してビットが立っている段を調べればよいです。
N<=10^9<2^30　より、Mは30以下となることが分かります。したがって、N-30を2進数表示すればよいです（N<=30の場合は1だけを集めていけばよいですね）。

解法２．
DEGwerさんの解法です。

赤色で囲われた部分を上から貪欲にとっていき、限界までとった後、水色で囲われた部分をしたから貪欲にとっていくという解法です。
nCk=C(n, k)としておきます。
n段目について、赤色の部分はC(n, Floor(n/2))、水色の部分はC(n, Floor(n/2)+1)となります。

a(n)=C(n, Floor(n/2)), b(n)=C(n, Floor(n/2)+1)

とおきます。
まず、赤色で囲われた部分を上から貪欲にとり、Nから引いていきます。
p段目まで引くことができたとき、

L=N-∑(i=0~p) { a(i) }
0<=L<=a(p+1)-1

となります。
さて、次はp段目から貪欲にb(i) (1<=i<=p)をとっていきます。この解法が成り立つことを示すためには、
「b(i) (1<=i<=p)をいくつか選び、その和がL (0<=L<=a(p+1)-1)となるようにできる」
ことを示す必要があります。数学的帰納法を使いましょう。

命題T(k)：b(i) (1<=i<=k)からいくつか選び、その和がS (0<=S<= ∑(m=1~k) { b(m) } )となるようにできる
命題V(k)：b(i) (1<=i<=k)からいくつか選び、その和がS (0<=S<= b(u+1)-1 )となるようにできる

と定めます。
先にV(k)について証明しましょう。
k=1のとき、b(1)=1C1=1であり、b(2)=2C2=1より可能です。
k=uのときV(u)が成り立つと仮定すると、
・0<=S<=b(u+1)-1 は表すことができ、
・S=b(u+1) は、b(u+1)だけを選べばよく、
・b(u+1)+1<=S<=2*b(u+1)-1 は、b(u+1)と、b(i) (1<=i<=u)からいくつか選んできたものの和で表すことが出来ます。
あとは、2*b(u+1)-1>=b(u+2)-1　つまり　2*b(u+1)>=b(u+2)　を示せばよいですが、これは

C(n. k)=C(n-1, k)+C(n-1, k-1)

という有名な公式を使えば示すことが出来ます。
これらからV(u+1)も真なので、命題T(p)が成り立つことを利用できます。

続いて、T(k)も証明します。
k=1のとき、b(1)=1より明らかです。
k=uのときT(u)が成り立つとすると、
・0<=S<=b(u+1)-1　は表すことができ、
・b(u+1)<=S<=∑(m=1~u+1) { b(m) }　についても表すことが出来ると分かります。
したがって、T(k)の証明もできました。

あと証明すべきなのは、

∑(m=1~p) { b(m) } >=a(p+1)-1

ですね。∑(m=1~p) { b(m) }>=a(p+1)-1　…（＊）を示しちゃいます。
またまた数学的帰納法です。
命題W(p)：（＊）
とします。
p=1のとき、b(1)=1、a(2)=2C1=2よりW(1)は成り立ちます。
p=uのとき、W(u)が真であるとすると、

∑(m=1~u) { b(m) }>=a(u+1)-1

が成り立ちますね。
p=u+1を考えたとき、

∑(m=1~u+1) { b(m) } - { a(u+2)-1 }

=∑(m=1~u) { b(m) }+b(u+1) - { a(u+2)-1 }

>=a(u+1) - a(u+2) + b(u+1)

>=0 （uを偶数か奇数かで場合分けして、C(n, k)=C(n-1, k)+C(n-1, k-1)を使うだけです）

となり、W(u+1)も真なので、W(p)が真であることが分かりました。

これで、この解法の正当性を示すことができました（これを思いつくのはすごい）。