読者です 読者をやめる 読者になる 読者になる

CodeIQ 挑戦の記録 : 第77回「今週のアルゴリズム:バランスの良いカーテンフック」

f:id:ibeckuu:20160127231417p:plain

CodeIQというサイトで問題に挑戦した記録です。

第77回「今週のアルゴリズム:バランスの良いカーテンフック」

問題文は「正解者発表」ページを参照下さい。

問題文を要約すると、カーテンライナーとフックの数が標準入力より与えられ、フックの掛かっているライナーと掛かっていないライナーの配置を考える。この時、フックの掛かっていないライナーが2個以上連続しない配置が何通りかを解答する。

f:id:ibeckuu:20160127213416p:plain f:id:ibeckuu:20160125040217p:plain

考え方

今回は組み合わせの問題として考える。
フックの掛かっていないライナーが2個以上連続しない様に配置するには、フックの掛かっている方を先に並べ、その両隣にフックの掛かっていないライナーを配置し、その組み合わせを数える事とする。

f:id:ibeckuu:20160127001048p:plain

フックの掛かっていないライナーを配置できる場所の個数をn、掛かっていないライナーの個数をkとすると、
n個よりk個を選ぶ組み合わせ {_nC_k} を求めれば良い事になる。

(例:3個の場所から2個を選ぶ組み合わせ。3通り)

f:id:ibeckuu:20160127214519p:plain

提出したコードは下記 (Ruby)

  • 実際に提出したのは下記をワンライナーにしたもの
  • フックの数よりライナーの数の方が多いケースを想定せず最初WAだった。

おまけ

第76回「今週のアルゴリズム:壊れたピンチハンガー」

「正解者発表」
正解をもらいましたが、あまりにも時間のかかるコードでとてもお見せできるものではないので公開しません。

実装したアルゴリズムだけ書いておきます。(計算量見積もれない)

  • 固定するハンガー(2個で1組)の数を1からハンガー全体のサイズの1/2までについて、
    位置の組み合わせnCr通りx位置それぞれ縦・横で2のr乗通りの配置パターンを作成する。
  • その全ての固定パターンに対して、1x2のハンガー組を何通り配置できるかを探索し、
    1通りのものが出現したらその時点で探索を打ち切り、固定ハンガー組の数を出力する。