CodingBatで悩んだ問題に対するメモ書き（其の一）

2014-05-17 追記

はてなブログの LaTeX 数式表示がデフォルトで MathJax 化された - 余白の書きなぐりということなので、記事中の数式の書き方をなおした。本文も少し修正した）

　「其の一」とか書いたが続編なんか書きたくないぞ。

　最近、Pythonを勉強しようと思い、CodingBatで問題をちまちまと解き続ける生活をしている。今週の日曜日（12月15日）からはじめて現在Logic-1まで解き進めた。Logic-1までは対して悩むこともなく解き進められたのでこの調子でLogic-2も解いて行こうと挑戦してみたら早速第1問目(CodingBat Python Logic-2 make_bricks)で詰まってしまった。

　以下問題（と拙訳）。

We want to make a row of bricks that is goal inches long. We have a number of small bricks (1 inch each) and big bricks (5 inches each). Return True if it is possible to make the goal by choosing from the given bricks. This is a little harder than it looks and can be done without any loops.

goalインチの長さの煉瓦塀を作りたい。小さい煉瓦（各1インチ）と大きい煉瓦（各5インチ）がいくらかある。用意された煉瓦から適当に選び出して［注：用意された煉瓦全部を使わなくてもよいということだろう］目標の長さの煉瓦塀を作れるならTrueを返すようにせよ。この問題は見た目よりも若干難しい。それと問題はループなしで解くことが出来る。

　最終的には偶然が重なって解けたし答えの理屈もきちんとわかったので問題は解決している。しかし、この「わかった」内容をどこかに控えておかないと、たぶん寝て起きたら忘れてしまうだろうし、同じ問題でまた詰まってしまうのは避けたい。

　というわけでここに控える。はじめに断っておくとCodingBatでも言っているように他に解き方がいっぱいあるだろうし、私の解き方が最もふさわしいなんて言うつもりも全く無い。自分用のメモとして残しておくものである。

始めの一歩

小さい煉瓦が $s$ 個、大きい煉瓦が $b$ 個あるとして、長さ $l$ の煉瓦塀を作ることを考える。煉瓦をすべてを使う必要はない。

考え方は、大まかに大きい煉瓦で煉瓦塀をつくっていって、細かい調整は小さい煉瓦で行うという方針になる（書くまでもないだろうけど）。

場合分け

まず $s+5b \lt l \tag{1}$ となる場合は明らかに長さ $l$ の煉瓦塀を作れないのでFalse。この場合 $s$ と $b$ の値にもよるけど、煉瓦塀を作っていたら大きい煉瓦は与えられた個数を使い切ったが、最後の最後で小さい煉瓦の数が足りなくなった、というものに相当する。大きい煉瓦の数は足りていた、煉瓦塀の長さの端数が問題になった、というような感じか。

次に $s+5b \geqq l \tag{2}$ となる場合、これは大きい煉瓦が余ってしまうという場合に相当する。よって小さい煉瓦の数が重要になってくるわけだが、小さい煉瓦を5個集めると大きい煉瓦1個と等価であることを考えると、 $l \bmod 5$ （剰余）と $s$ を比較して $l \bmod 5 \gt s \tag{3}$ ならFalseとすればよい。つまり $l$ に対して $s$ が十分なだけあれば煉瓦塀は作れるという意味になる。