Q20 酔っ払いの帰り道

PHPのソース

<?php
Solve( 5, 2, 3); //7
Solve(15, 3,10); //1274766

//駅数,乗車駅,降車駅を引数として解を返す
function Solve($pEkiCnt , $pJyousya , $pKousya)
{
    $OddVector  = ($pJyousya < $pKousya  ? 1 : -1);
    $EvenVector = ($pKousya  < $pJyousya ? 1 : -1);

    //折り返し候補数(奇数回目)を求める
    $I = $pKousya;
    $KouhoOddCnt = 0;
    while(0 < $I && $I <= $pEkiCnt){
        if($I != $pJyousya && $I != $pKousya)
            $KouhoOddCnt++;
        $I += $OddVector;
    }

    //折り返し候補数(偶数回目)を求める
    $I = $pKousya;
    $KouhoEvenCnt = 0;
    while(0 < $I && $I <= $pEkiCnt){
        if($I != $pJyousya && $I != $pKousya)
            $KouhoEvenCnt++;
        $I += $EvenVector;
    }

    $Answer = 0;
    for($I = 0 ; $I <= PHP_INT_MAX ; $I++){
        $PatternCnt = DerivePatternCnt($I , $KouhoOddCnt , $KouhoEvenCnt);
        if ($PatternCnt == 0) break;
        $Answer += $PatternCnt;
    }
    printf('駅数%d,乗車駅%d,降車駅%dでは%d通り',$pEkiCnt , $pJyousya , $pKousya,$Answer);
    echo PHP_EOL;
}

//乗り過ごし回数,折り返し候補数(奇数回目),折り返し候補数(偶数回目)を引数として場合の数を返す
function DerivePatternCnt($pN , $pKouhoOddCnt , $pKouhoEvenCnt)
{
    if($pN == 0) return 1;

    $IsOK = true;
    $PatternCnt = 1;
    for($I = 1; $I <= $pN ; $I++){
        if($I %2 == 1){
            if($pKouhoOddCnt == 0){
                $IsOK = false; break;
            }
            $PatternCnt *= $pKouhoOddCnt--;
        }
        else{
            if($pKouhoEvenCnt == 0){
                $IsOK = false; break;
            }
            $PatternCnt *= $pKouhoEvenCnt--;
        }
    }
    return $IsOK ? $PatternCnt : 0;
}

実行結果

駅数5,乗車駅2,降車駅3では7通り
駅数15,乗車駅3,降車駅10では1274766通り

解説

乗り過ごし回数で場合分けして
和の法則を使ってます。