CodeIQ 挑戦の記録 : 第77回「今週のアルゴリズム：バランスの良いカーテンフック」
CodeIQというサイトで問題に挑戦した記録です。
第77回「今週のアルゴリズム：バランスの良いカーテンフック」
問題文は「正解者発表」ページを参照下さい。
問題文を要約すると、カーテンライナーとフックの数が標準入力より与えられ、フックの掛かっているライナーと掛かっていないライナーの配置を考える。この時、フックの掛かっていないライナーが2個以上連続しない配置が何通りかを解答する。
考え方
今回は組み合わせの問題として考える。
フックの掛かっていないライナーが2個以上連続しない様に配置するには、フックの掛かっている方を先に並べ、その両隣にフックの掛かっていないライナーを配置し、その組み合わせを数える事とする。
フックの掛かっていないライナーを配置できる場所の個数をn、掛かっていないライナーの個数をkとすると、
n個よりk個を選ぶ組み合わせ
を求めれば良い事になる。
（例：3個の場所から2個を選ぶ組み合わせ。3通り）
提出したコードは下記 (Ruby)
- 実際に提出したのは下記をワンライナーにしたもの
- フックの数よりライナーの数の方が多いケースを想定せず最初WAだった。
おまけ
第76回「今週のアルゴリズム：壊れたピンチハンガー」
「正解者発表」
正解をもらいましたが、あまりにも時間のかかるコードでとてもお見せできるものではないので公開しません。
実装したアルゴリズムだけ書いておきます。（計算量見積もれない）
- 固定するハンガー(2個で1組)の数を1からハンガー全体のサイズの1/2までについて、
位置の組み合わせnCr通りx位置それぞれ縦・横で2のr乗通りの配置パターンを作成する。 - その全ての固定パターンに対して、1x2のハンガー組を何通り配置できるかを探索し、
1通りのものが出現したらその時点で探索を打ち切り、固定ハンガー組の数を出力する。
