はじめに
AtCoder さんの問題をお借りして Excel を使用した解法をご紹介すると共に、Excel が優れた関数型プログラミングツールであることを提示したいと思います。
今回のお題
AtCoder Beginner Contest 129 C - Typical Stairs
Difficulty: 795
下準備
最初にシートを準備し、セルA4に=ROW()と入力します。
Enterを押下すると4が表示されます。
ROW()は行番号を返すワークシート関数です。
このままでは、0や負の数が使えませんので、オフセットとして=ROW()-4と入力しセルA10までコピーしてください。
次にセルB5:B10に1を入力しておきます。
フィボナッチ数列
*フィボナッチ数列 - wikipedia*と言えば、プログラミングの再帰的処理の例としてよく紹介されます。
まず、フィボナッチ数列の初期値として、セルC4:C5に1を入力します。
次にセルC6に=C4+C5若しくは=SUM(C4:C5)と入力しセルC7:C10へコピーします。
これにて、フィボナッチ数列の生成が完了しました。
ABC 129 C 入力例 1
AtCoder Beginner Contest 129 C - Typical Stairs を動的計画法で解きたいと思います。
B列はその段の床の状態を表し、1はその段の床が壊れていないものとし0はその段の床が壊れているものとします。
まず、セルC5を=MOD(B5*(C3+C4),1000000007)と修正します。
MOD(数値,除数)は余りを求めるワークシート関数です。
=IF(B5=1,MOD(C3+C4,1000000007),0)という式でもOKです。
次に、セルC5をC6:C10にコピーします。
最後に、セルB7に0を入力します。
これにて、出力例 1 の移動方法の総数: 4を求めることができました。
ABC 129 C 入力例 2
A:C列を 14 行目までコピペし、セルB8:B9に0を入力します。
セルC14の0が解答になります。
ここで仮に高橋君は一歩で 1段か 2段上ることができるの条件を高橋君は一歩で 1段か 2段か 3段上ることができるに変更したとします。
この場合、セルC5の式を=MOD(B5*(C3+C4),1000000007)から=MOD(B5*(C2+C3+C4),1000000007)に修正しコピペすることにより対応可能です。
一歩で 3段上ることができますので、連続した壊れた床をジャンプしています。
実装例
C++ による実装の例は、editorial や、Ruby による実装の例は、*＿こちら＿*をご覧ください。
まとめ
- 再帰や動的計画法は分かりづらい面もありますが、処理自体はシンプルです
- Excel が優れた関数型プログラミングツールであることを提示しました