「今週のお題：寝過ごしても大丈夫？」問題解答 ( CodeIQ )

CodeIQ

はじめに

CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。

codeiq.jp

問題

今回は次のような問題でした。

  • 次のような条件で電車にのる時の乗車経路が何通りあるか出力する。
  • 路線は端から端までの駅数 n ( 環状線ではない )、駅には 1～n の番号がついている。
  • 駅数 n と発駅・着駅の番号がカンマ区切り1行で入力される。
  • 最初は、発駅から着駅方面に進み、もし寝過ごした ( 着駅を行き過ぎた ) 場合は折り返す
  • 何回折り返しても良い ( 一度も折り返さなくても良い ) が、折り返しに使った駅・発駅では折り返せない

詳細は次のCodeIQマガジンの記事をご覧ください。 codeiq.jp

解説

提出版は次のRuby(90)でした。

n,s,e=eval ?[+gets+?]
f,b=s<e ?[n-e+1,e-1]:[e,n-e]
a=t=1
a+=(t*=f-=1)+t*=b-=1while 0<t
p a

ちょっと問題の条件が掴みづらいところですが、順列の問題の一種と考えれば、単純な計算式に落とし込むことができます。

どういうことかというと、着駅を行き過ぎる度、折り返しに選べる駅の数が減っていくところが、丁度順列と同じだからです。

ただし、着駅を挟んでどちら側で折り返すか、これは寝過ごす度に交互に切り替わりますから、両側で折り返しに使える駅の数を考えることになります。 例にある 5,2,3 の入力 ( 駅数5、2番の駅発、3番の駅着 ) の場合、着駅の先に2駅、逆側は発駅を除いて1駅あるため、

  • 寝過ごさない … 1通り
  • 1～2回寝過ごす … 1×2, 1×2×1通り ( それぞれ2,1駅から選択 )
  • 3～4回寝過ごす … 1×2×1×(2-1), 1×2×1×(2-1)×(1-1)通り ( それぞれ(2-1),(1-1)駅から選択 )
    ※この時点で折り返せる駅の数の一方が0になったので終了

と、交互に候補を減らしながら乗算を行うことで場合の数が出ます。 どちらかの候補が0になればそれ以上の事象は起こり得ないということで、計算を打ち切ります。

実装上は、着駅の先の候補を f, 逆側を b とし、発駅・着駅の数字の大小 ( 最初に向かう方向 ) で 場合分けします。( ループでのデクリメントを考え、1多い数値にしておきます )

終わりに

実は、最初「発駅～着駅間では折り返しできない」となぜか勘違いしてWAしてしまいました。先入観って怖いですね。気を付けたいと思います。