私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「パスカルの 三角形では ありません（字余り）」（CodeIQ）を参照してください。
問題を引用します。
右図のように数が並んでいます。
A B C D E F G H a 1 1 2 3 5 8 13 21 b 1 2 5 10 20 38 71 130 c 1 3 9 22 51 111 233 474 d 1 4 14 40 105 256 594 1324 e 1 5 20 65 190 511 1295 3130 f 1 6 27 98 315 924 2534 6588 g 1 7 35 140 490 1554 4578 12720 h 1 8 44 192 726 2472 7776 22968
「cF」のようにマスを指定するので、それに対応する数（入力が「cF」なら111）を出力するプログラムを書いてください。
Pythonで解答しています。
#!/usr/local/bin/python3 # -*- coding:utf-8 -*- import fileinput def makeTable(): tbl = [ [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [ 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26] ] for i in range(2,26): line = [] for j in range(26): if j == 0: line.append(tbl[i-1][j]+tbl[i-2][j]) else: line.append(line[j-1] + tbl[i-1][j]+tbl[i-2][j]) tbl.append(line) return tbl if __name__ == "__main__": tbl = makeTable() for line in fileinput.input(): if not line.strip(): continue row = ord(line.strip()[0])-0x61 col = ord(line.strip()[1])-0x41 print(tbl[col][row]) # 問題とは行列が入れ替わっている
私はこの問題を数回ギブアップしかけました。
一目見て、A列、B列、……、で規則性のある数列になっており、列同士も何か関係がありそうです。手計算でE列まで一般項を求める式を作ったのですが、列同士の規則性がわからず、「これは無理か……」と思って問題をもう一度見たら「想定時間5分」の記述が。「マジか？ 無理ゲーすぎんだろw」と思いましたが、ふと、「今まで考えてたように数列の一般項を求める式を探していたら5分は絶対無理。ということはもっと簡単に法則が見つかるはず」と思い、もう一度表を見たらすぐに法則がわかりました。
図で説明した方がわかりやすいでしょう。
| A | B | C | D | E | F | G | H | |
|---|---|---|---|---|---|---|---|---|
| a | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 |
| b | 1 | 2 | 5 | 10 | 20 | 38 | 71 | 130 |
| c | 1 | 3 | 9 | 22 | 51 | 111 | 233 | 474 |
| d | 1 | 4 | 14 | 40 | 105 | 256 | 594 | 1324 |
| e | 1 | 5 | 20 | 65 | 190 | 511 | 1295 | 3130 |
| f | 1 | 6 | 27 | 98 | 315 | 924 | 2534 | 6588 |
| g | 1 | 7 | 35 | 140 | 490 | 1554 | 4578 | 12720 |
| h | 1 | 8 | 44 | 192 | 726 | 2472 | 7776 | 22968 |
青のマス（dD）の値はピンクと赤のマス（aB〜dC）の合計です。
同様に緑のマス(cD)はピンクのマスの合計です。
ということは、青のマスは緑のマスに赤のマスを加えた値です。
つまり、AとB列は特殊ですがそれ以外の列については求めようとするマスの列と同じ行で左側2列と同列で1つ前の値を加えたものになります。
前述の通りに考えると再帰で計算できます。出題者のコメントにもメモ化再帰が普通と思うとありました。
しかし、私は表引きで実装しています。
何故再帰で計算せず表引きにしたのかを最も説明すべきですが、先にプログラムを説明しておきます。
前述の説明通りのことをA〜Zまで26行、26列やるだけです。
プログラムでは行列を入れ替えています。これは単にこちらの方が扱いやすいからです。そして、AB列のデータは初期値として定義しています。AB列は自分の左に2列分の値を持たないため、計算でやろうとしても特殊な処理が必要になります。それならば、初期値として定義したほうが処理が楽になります。
1列めと2列目が最初から求まっているので実際のプログラムは3列目から26列目までを計算して表を作っています。
表さえ作ってしまえばあとは入力から相当する場所の値を取り出すだけです。
さて、何故表引きでやったかです。
まず、計算量ですがこの問題は表を丸々求めても高々262の計算しか必要ありません。メモリについても私のプログラムのように最初に1回だけ作成するようにすれば無駄はありません。JavaやC/C++ならstaticに確保してしまえば全く無駄がありません。
次に計算コストです。もし、この問題のテストパターンが「コマンドライン引数に渡す」なら計算量削減のため再帰で計算すべきでしょう。しかし入力は「標準入力に渡す」となっています。実際にはテストパターン1件ごとにプログラムが実行し直されていたようですが、そんなことはやってみるまでわかりません。テストはプログラムを終了せずに繰り返し標準入力に与えられるかもしれません。
プログラムを終了せず複数回実行される場合、全体としての計算コストは私の様に表引きにした方が少なくて済む上、メモリ効率も良くなります。
計算コストは再帰で計算する場合は毎回O(n2)です。
表引きの場合は表を作る時にO(n2)ですが、それ以降はO(1)です。
およそテストパターン4つが一回のプログラム実行で投入されると、計算量で再帰で毎回計算する場合と表引きで等しくなります。それより多くなると表引きの方が計算量が少なくなります。
今回の問題のテストパターンは確か12か13パターンありました。当然その中には「zZ」というパターンもありましたから、1回のプログラム実行でテストされていたら表引きの方が圧倒的に早く終わることになります（zZは再帰でも全パターン計算した結果なので、表を作るのと同じだけコストがかかります。ということは表引きではそれ以外の11か12パターンを全く計算しなくて済む分だけ高速になります）。
競技プログラミングとかの場合だとこの問題のような場合でも再帰で計算するのが正解かもしれません。しかし、実際の業務で使用されるプログラムの場合、1つのプロセスがずっと動き続けて同じ処理を別の入力パターンで何度も繰り返すというのはよくあることです。そのような場合、私が今回やったように起動時のタイミングで1回だけで計算を終わらせてしまい、その後は結果を参照するだけという作りにするのが優れていることはよくあります。