「パスカルの 三角形では ありません（字余り）」問題解答(CodeIQ)

はじめに

CodeIQというところでプログラミング問題に挑戦しましたので、ネタバレです。

codeiq.jp

問題

次の図のように、2次元に規則的に数値が配置されているとき、指定された座標にある数値を出力するという問題です。

座標は、英小文字(縦)・英大文字(横) 1文字ずつの組み合わせで示されます。上限はそれぞれ、z,Z です。
なので、例えばcFという入力に対しては111と出力する、となります。

解説

整理

まずは、この配置された数値の規則性を解かなければ話が先に進みません。

が、ちょっと見てみると、結構わかりやすい規則性であることが分かります。
横A～Z、縦a～zをそれぞれ1～26に置き換え、上と左 ( 横・縦の座標 0 ) に 0 のマスを追加すると、次の図のように上1マス・左2マスの3項分の合計として数値が決まっていることが分かります。

なお、図中の黄色いマスは初期値に相当する部分ですね。

ということで、条件を整理すると、次の通り ( なお、数式中の右肩の数値は指数ではなくて横の位置を示す添え字と見てください )。

• $x^c_0=0$
• $x^0_r=0,\,\,x^1_r=1$
• $x^c_r=x^c_{r-1}+x^{c-2}_r+x^{c-1}_r\,\,( r\ge 1,\,\,c\ge 2 )$

結論

さて整理ができたところで、いきなり結論です。

この数値$x^c_r$は

• $x^c_r=\sum_{\frac{c}{2}+1\le k\le c}^{} {}_{k -1}C_{c-k}\times{}_kH_r $
  ( Cは組み合わせ、Hは重複組み合わせ ${}_nH_m={}_{n+m-1}C_m={}_{n+m-1}C_{n-1}$ )

という和で表すことができ、Σの各項は前項との差分のみの計算で求められるため、座標横c,縦rに対して、計算量$O(c)$と、メモ化再帰等で漸化式を素直に計算した場合の$O(cr)$に比べて減らすことができます。

提出したRubの実装は次の通り ( なお、今回は特にgolfしてません )。

r,c=gets.bytes.map{|e|e%32}
s=0
a=h=1
1.upto(c) do |k|
  if k-1>=c-k
    if k-1==c-k+1
      a=k-1
    elsif k-1>c-k+1
      a=a*(k-1)*(c-k+1)/((k*2-c-1)*(k*2-c-2))
    end
    s+=a*h
  end
  h=h*(r+k-1)/k
end
puts s

詳細

整理した条件を再掲します。

• $x^c_0=0$
• $x^0_r=0,\,\,x^1_r=1$
• $x^c_r=x^c_{r-1}+x^{c-2}_r+x^{c-1}_r\,\,( r\ge 1,\,\,c\ge 2 )$

これをさらに r に対してまとめると、

• $x^c_r=\sum_{k=1}^r (x^{c-1}_k+x^{c-2}_k)\,\,( r\ge 1,\,\,c\ge 2 )$

と、和の形で表すことができます ( 階差数列の整理と見てください )。
ここでΣを書くのが面倒なので、独自ながら$\sigma z_r=\sum_{k=1}^r z_k$ のような略記を行うものとして、次のように表し直します。

• $x^c_r=\sigma x^{c-2}_r+\sigma x^{c-1}_r$

続いて、重複組み合わせ H に対して、

• $\sum_{k=1}^n {}_mH_k = {}_{m+1}H_n$

であることを利用します。先ほどの$\sigma$を使えば、

• $\sigma {}_mH_n={}_{m+1}H_n$

ということです。
これは例えば、$m=3$ の時であれば、

$$ \begin{eqnarray} &\,&\frac{1\cdot 2}{2\cdot 1}+\frac{2\cdot 3}{2\cdot 1}+\cdots+\frac{10\cdot 11}{2\cdot 1} \\ &= &\frac{1\cdot 2\cdot(3-0)}{3\cdot 2\cdot 1}+\frac{2\cdot 3\cdot(4-1)}{3\cdot 2\cdot 1}+\cdots+\frac{10\cdot 11\cdot(12-9)}{3\cdot 2\cdot 1} \\ &= &\frac{-0\cdot 1\cdot 2+1\cdot 2\cdot 3}{3\cdot 2\cdot 1}+\frac{-1\cdot 2\cdot 3+2\cdot 3\cdot 4}{3\cdot 2\cdot 1}+\cdots+\frac{-9\cdot 10\cdot 11+10\cdot 11\cdot 12}{3\cdot 2\cdot 1} \\ &= & \frac{10\cdot 11\cdot 12}{3\cdot 2\cdot 1} \\ \end{eqnarray} $$

というように、$m-1=2$項ずつの積の和が、$m=3$項の積にまとめられることに相当します。

ここで、${}_1H_r=1$ であることから $x^1_r={}_1H_r$ となり、上で出てきた
$x^c_r=\sigma x^{c-2}_r+\sigma x^{c-1}_r,\,\,\,\,\sigma {}_mH_n={}_{m+1}H_n$
を利用すると、

$$ \begin{eqnarray} x^0_r&\,& &=&0 \\ x^1_r&\,& &=&1\cdot {}_1H_r \\ x^2_r&=&\sigma x^0_r+\sigma x^1_r &=& &1&\cdot {}_2H_r \\ x^3_r&=&\sigma x^1_r+\sigma x^2_r &=& &1&\cdot {}_2H_r+&1&\cdot{}_3H_r \\ x^4_r&=&\sigma x^2_r+\sigma x^3_r &=& &\,& &2&\cdot{}_3H_r+&1&\cdot {}_4H_r \\ x^5_r&=&\sigma x^3_r+\sigma x^4_r &=& &\,& &1&\cdot{}_3H_r+&3&\cdot {}_4H_r+&1&\cdot {}_5H_r \\ \end{eqnarray}\\ \cdots $$

というように、$x^c_r$ は ${}_kH_r$ の線形和として表すことができることが分かります。
この係数を $a^c_k$ すなわち、

• $x^c_r=\sum_{k\ge 1}^{} a^c_k\times {}_kH_r$

であるとするならば、その漸化式は

• $a^c_k=a^{c-2}_{k-1}+a^{c-1}_{k-1}$

これは、パスカルの三角形の中で成立する関係式の変形版に他なりません。
実際、$a^c_k$ を並べてみると、

というように、パスカルの三角形を横倒しにして雪崩れさせた形状になっています。

ここから冒頭の

• $x^c_r=\sum_{\frac{c}{2}+1\le k\le c}^{} {}_{k -1}C_{c-k}\times{}_kH_r $

が成立することが分かります。

…「パスカルの三角形ではありません」と言いつつこんな所に隠しているとは、出題者の@Nabetaniさんもお人が悪い…というべきでしょうか??

補足

次の式の簡易な証明

• $\sum_{k=1}^n {}_mH_k = {}_{m+1}H_n$

まず、重複組み合わせの性質として

• ${}_xH_y={}_{x+y-1}C_{y-1}$

パスカルの三角形の性質として

• ${}_{x+1}C_y={}_xC_{y-1}+{}_xC_y \Leftrightarrow {}_xC_y={}_{x+1}C_y-{}_xC_{y-1}$

これらより

$$ \begin{eqnarray} {}_xH_y&=&{}_{x+y-1}C_{y-1} \\ &=&{}_{x+y-1+1}C_{y-1}-{}_{x+y-1}C_{y-1-1} \\ &=&{}_{(x+1)+y-1}C_{y-1}-{}_{(x+1)+(y-1)-1}C_{(y-1)-1} \\ &=&{}_{x+1}H_y-{}_{x+1}H_{y-1} \end{eqnarray} $$ ゆえに、 $$ \begin{eqnarray} \sum_{k=1}^n {}_mH_k &=& {}_mH_1 + \sum_{k=2}^n {}_mH_k \\ &=& {}_mH_1 + \sum_{k=2}^n ( {}_{m+1}H_k-{}_{m+1}H_{k-1} ) \\ &=& {}_mH_1 + {}_{m+1}H_n - {}_{m+1}H_1 \\ &=& {}_{m+1}H_n \end{eqnarray} $$

おまけ

ちなみに、この問題、Brainf**kでも提出しました。

ええと、詳しくは把握してないのでざっくり説明すると、

• 数値は任意桁数のBCDとして管理
• BCDの各桁は、2要素5セルのグループ×26グループ(固定)×桁数の二次元配列として配置する
• ただし26グループをフルに使うとは限らない。あくまで桁と桁の距離を固定するため
• メインループは横方向の移動に相当。2列分の数値 ( グループの中の2要素がそれ ) を常に保持し、新しい列へと更新していく。
• 縦の座標を元に初期配列の長さ ( グループ数 ) を決定し、その長さ分だけ配列を操作する。

例えばcFという入力に対しては、全部の桁をまとめて考えると、次のようにグループを更新していくことになり、端のグループが答えを保持することになります。

実際にどのように更新するかは、次の図のような感じで。前のグループの数値を次々と累積していくように更新します。赤枠で囲った数値が次の操作対象、オレンジ色のセルが加算により更新されたセルです ( 1操作で2セル更新することもあります )。

…まあ、実際は更新の時に割り算 ( 桁上がりの処理 )、桁上がり発生情報の伝播 ( 後の桁拡判断のため ) 等々もやってるわけですが。面倒臭いので(以下略)

終わりに

解いたのは2016年始めで、当初締め切りが3月だったので、まあゆっくり記事にするかな…と思っていたのですが。締め切りが8月末までに延びたのですね。絶対忘れると思ったので、記事自体はもう3月中に書いてしまいました。はっきり言ってBrainf**kはどうやって組んでるのか自分でもさっぱりわかりません。