No Caffeine, No Life

プログラミング(主にPython)

数学パズル Q23 ブラックジャックで大儲け!?: メモ化再帰(深さ優先探索)

通常の再帰深さ優先探索)での解答例:

メモ化して高速化した例:

広告を非表示にする

数学パズル Q68 隣り合わないのがマナー?: メモ化再帰

通常の再帰を使った解答例:

高速化するために、メモ化再帰を用いた解答例:

テキストにあるとおり、条件を配列に落とし込む際に「番兵」という考え方を遣っている(WALLというところ)。番兵については、下記を参考:

http://blog.codebook-10000.com/entry/20130816/1376656553

広告を非表示にする

数学パズル Q24 完璧に打ち抜くストラックアウト: メモ化再帰とビット演算

いわゆる「2抜き」を許した場合のストラックアウト。

テキストにあるような、配列を用いて打ち抜く場合を列挙したやり方だと(しょうもないことに)Pythonでうまく書けなかったので、ここでは、打ち抜く場合のそれぞれをビット列で表現しています。(例:0b000000011 = 1と2を打ち抜く)

ロジックはテキスト通りです:

広告を非表示にする

数学パズル Q38 7セグメントコードの反転:ビット演算

まず全探索をする解答例:

これだと10!分の探索をしていることもありかなり時間がかかる(自分の手元では40秒ほど)。

 

10!の探索には変わりないが、0-9のセグメントの変化をあらかじめテーブルに保存しておき、利用することを考える。この場合、文字列を扱う操作が減る分速くなることが期待される。

 

これで手元では8秒ほどに。。。(でも競技プログラミングでは全くダメ)

 

permutationを使わずに再帰的に解くことを考える:

 

pythonにおける変数のスコープについては下記を参照:

http://www.isl.ne.jp/pcsp/python/python25.html

広告を非表示にする

数学パズル Q41 美しい?IPアドレス: ビット表現で遊ぶ

2進数で対称になる数、を考えると16ビットの数を反転し、追加して32ビットの数を得ることを考える。これを10進数に変換したときに、0-9の数を1個ずつ使っていればよい。

その場合の解答例:

実際には16ビットではなくて8ビットで十分。その場合は、下記のようになる:

広告を非表示にする