「プロジェクトオイラー解説問162」の編集履歴(バックアップ)一覧はこちら
プロジェクトオイラー解説問162 - (2013/12/13 (金) 12:17:00) の1つ前との変更点
追加された行は緑色になります。
削除された行は赤色になります。
只今解説準備中
*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は許されない. )
----
解法
一桁ずつ伸ばしながら組み合わせ数を計算していきます。
その時n桁目で重要となるのは。
0が0回でたか1回以上出たかの2通り
1が0回でたか1回以上でたかの2通り
Aが0回でたか1回以上でたかの2通り
の計8通りで管理すればよいと分かります。
memo[16][2][2][2]で組み合わせ数を管理して漸化式を立てれば完了です。
只今解説準備中
*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は許されない. )
----
解法
一桁ずつ伸ばしながら組み合わせ数を計算していきます。
その時n桁目で重要となるのはn桁目までに。
0が0回でたか1回以上出たかの2通り
1が0回でたか1回以上でたかの2通り
Aが0回でたか1回以上でたかの2通り
の計8通りで管理すればよいと分かります。
memo[16][2][2][2]=memo[n桁目][n桁目までに0が出た回数0回か1回以上][n桁目までに1が出た回数0回か1回以上][n桁目までにAが出た回数0回か1回以上か]
で組み合わせ数を管理して漸化式を立てれば完了です。