プロジェクトオイラー解説問162 - c21coterie @ ウィキ

只今解説準備中

Problem 162 「16進数」 †

---

問題

16進法では, 数は以下の16個の数字によって表される
0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F

16進数の AF は, 10進法での 10x16 + 15 = 175 と等しい.
3桁の16進数 10A, 1A0, A10, A01 には, 0, 1, A の全てが現れている.
10進数で書くときと同様に, 先頭の0は書かないことにする.

0, 1, A がそれぞれ少なくとも1回は現れるような16桁までの16進数はいくつ存在するか?
16進数で答えよ.
(A,B,C,D,E,F は大文字とし, 先頭や末尾の16進数であることを表す記号や先頭の0は許されない. つまり, 1A3F ならOK. 1a3f, 0x1a3f, $1A3F, #1A3F, 0000001A3Fは許されない. )

---

解法
一桁ずつ伸ばしながら組み合わせ数を計算していきます。
ｎ桁目で重要となるのはｎ桁目までに。
0が0回でたか１回以上出たかの２通り
1が0回でたか１回以上でたかの２通り
Aが0回でたか１回以上でたかの２通り
の2*2*2の全８通りで管理すればよいと分かります。

memo[16][2][2][2]=memo[ｎ桁目][ｎ桁目までに0が出た回数０回か１回以上][ｎ桁目までに1が出た回数0回か１回以上][ｎ桁目までにＡが出た回数０回か１回以上か]
で組み合わせ数を管理して漸化式を立てれば完了です。

漸化式は私の場合Ｐｒｏｌｏｇで半自動生成しましたが。
式にするとかなりめんどくさいことになります。
ループやコードなどを使って半自動化することをお勧めします。

それでも参考になると思いますので漸化式を全部書いてみましょう。

---

漸化式

memoの値は最初すべて0設定
memo[1][0][1][0]=1
memo[1][0][0][1]=1
memo[1][0][0][0]=13
と設定してから計算開始。

memo[n+1][0][0][0]=memo[n][0][0][0]*13
memo[n+1][1][0][0]=memo[n][1][0][0]*14+memo[n][0][0][0]
memo[n+1][0][1][0]=memo[n][0][1][0]*14+memo[n][0][0][0]
memo[n+1][0][0][1]=memo[n][0][0][1]*14+memo[n][0][0][0]

memo[n+1][0][1][1]=memo[n][0][1][1]*15+memo[n][0][0][1]+memo[n][0][1][0]
memo[n+1][1][0][1]=memo[n][1][0][1]*15+memo[n][1][0][0]+memo[n][0][0][1]
memo[n+1][1][1][0]=memo[n][1][1][0]*15+memo[n][1][0][0]+memo[n][0][1][0]

memo[n+1][1][1][1]=memo[n][1][1][1]*16+memo[n][1][0][1]+memo[n][1][1][0]+memo[n][0][1][1]

最後に
memo[16][1][1][1]を答えとすればよい。

---

書いてみましたがなんだかめんどくさくてきちんと漸化式が立っているか自信がありません。
簡単な問題ですし好みの方法で頑張ってください。