私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「スムーズな電車の乗り降り」（CodeIQ）を参照してください。
電車には進行方向の左右にドアがあり、駅のホームの配置によってどちらかのドアが開きます。
降りる駅で、乗った側のドアと同じドアが開くのであれば、乗った側のドアのそばに立っておくと便利です。
しかし、乗った側のドアが開いたのに降りないと、他の乗客の邪魔になります。
そこで、乗ったときはそのドアのそばに立ち、以下の行動を取ることにします。
・乗った側のドアが開いた場合は、その駅で降りる
・反対側のドアが開き続けた場合は、乗った側のドアが開くまで乗り続ける
電車が片道を走行する間に、二人の乗客がそれぞれ、別々の駅から乗って別々の駅で降ります。
このとき、この二人がそれぞれ反対側のドアで上記の行動を取ることにします。
全部で n 個の駅があったとき、このような行動ができる「ホームの配置」と、「乗客の動き」の組み合わせが何通りあるかを求めてください。
（ただし、1人目は進行方向の左側のドアから、2人目は右側のドアから乗降するものとします。）
例えば、n = 4 でA駅からD駅に電車が動くとき、以下の6通りがあります。
ホームの配置（開くドア） 乗客の動き A駅 B駅 C駅 D駅 1人目 2人目 左 左 右 右 A→B C→D 左 右 左 右 A→C B→D 左 右 右 左 A→D B→C 右 左 左 右 B→C A→D 右 左 右 左 B→D A→C 右 右 左 左 C→D A→B
しかし、以下のようなホームの配置の場合は、上記の行動ができません。
ホームの配置（開くドア） 乗客の動き A駅 B駅 C駅 D駅 1人目 2人目 左 左 右 左 A→B C→？ 左 左 右 左 B→D C→？
なお、路線は環状にはなっておらず、乗客も折り返すことなく一方向で乗降するものとします。
そのほかの条件は以下になります。
※降りた駅でそのまま再度乗ることはありません
※一度降りてから別の駅で再度乗ることはありません
※乗った駅でそのまま降りることはありません
※必ず二人とも電車に乗る（一方でも電車に乗らないことはない）こととします
※駅では両側のドアが同時に開くことはありません
標準入力から n が与えられたとき、「ホームの配置」と「乗客の動き」の組み合わせを求め、その数を標準出力に出力してください。
なお、与えられる n は14以下の整数とします。
【入出力サンプル】
標準入力
4
標準出力
6
Rubyで解答しています。
#!/usr/bin/ruby
def count(arr)
ret = 0
for i in 0..(arr.size-4)
l = arr[i..-1].count("L")
r = arr[i..-1].count("R")
if l >= 2 && r >= 2 then
if arr[i] == "L" then ret += r-1
else ret += l-1
end
end
end
return ret
end
def solve(n)
cnt = 0
["L", "R"].repeated_permutation(n){|str|
l = str.count("L")
r = str.count("R")
if l >= 2 && r >= 2 then
cnt += count(str)
end
}
return cnt
end
# main
while line = gets
line.strip!
if line.empty? then next end
p solve(line.to_i)
end
問題の意味が読み取りづらいです。n=5の場合を例にしてくれれば分かり易かったと思うのですが。
なので補足しておきます。
例えばn=5の時の各駅に列車が停車した時、開く扉のパターンのうち1つに「左、左、右、左、右」というのがあります。この様な駅のパターンに対して乗客の乗り降りは次の2パターンがあります。
| 扉 | 左 | 左 | 右 | 左 | 右 | パターン1 | A↑ | A↓ | B↑ | B↓ | パターン2 | A↑ | B↑ | A↓ | B↓ |
|---|
私のプログラムは各駅に停車した列車の開く扉のパターンを総当たりで求め、それに対してAとBが乗り降りできるパターンを数え上げるという単純なものです。
扉のパターンに対して乗り降りのパターンの数え方です。
駅数が6のうち1つを例に説明します。
| 駅 | 1 | 2 | 3 | 4 | 5 | 6 | パターン数 |
|---|---|---|---|---|---|---|---|
| 扉 | 左 | 左 | 右 | 左 | 右 | 右 | パターン1 | A↑ | A↓ | B↑ | B↑ | 2 | パターン2 | A↑ | B↑ | A↓ | B↑ | 2 |
入力値を数値に変換し、solve()に渡します。
solve()が結果を返すのでそれを印字して終わります。
扉のパターンを列挙し、count()でそれぞれのパターンに対する乗降パターン数を数え、足し合わせます。左右どちらかの扉が1以下の場合、問題の条件を満たすことがないので無視します。
合計値を結果として返却します。
arrの駅パターンに対して乗降パターンが何通りあるかを数えます。
arrの先頭から順番にチェックして"L"（左扉）ならAが乗車してきたものとして、Bの乗降パターンを加算足ます。考え方に書いた通り、"R"（右扉）の数-1がBの乗降パターンになります。
ある駅以降の左側の扉の数が1以下になったら問題の条件を満たせないので無視します（プログラムでは右扉も同様にチェックしていますが無意味です）。
合計値を結果として返します。
あまり頭良さそうなプログラムではありません。少なくともcount()の処理はarrに対してループする必要はなく、計算だけで求められます。
この問題は題意がよくわからなくて、「こういう意味なのかなぁ」と思いながらテストケースを通していたらできた（1回リジェクトされています）という状態でした。このプログラムは問題の意味を確認するために遅くてもどういう理屈かわかりやすいプログラムを作っていたら時間的にも間に合ってしまったのでそのまま投稿してしまったという代物、というのが言い訳です。