Q59 取られたら取り返す！

JavaScriptのソース

Solve( 3, 4, 2); //         6
Solve(11,25,24); //3027042304

function Solve(pN , pA , pB)
{
    //場合の数[Aの得点][Bの得点]なDP表
    var PrevDP = DeriveDPArr(pA , pB);
    PrevDP[0][0] = 1;
    
    var Answer = 0;
    while(true){
        var WillBreak = true;
        var CurrDP = DeriveDPArr(pA , pB);
        
        for(var I = 0 ; I <= pA ; I++){
            for(var J = 0 ; J <= pB ; J++){
                if(PrevDP[I][J] == 0) continue;

                //Aが得点する場合
                var NewI = I + 1;
                if(NewI == pA && J == pB) Answer += PrevDP[I][J];

                if((pN <= NewI && NewI - J >= 2) == false){
                   CurrDP[NewI][J] += PrevDP[I][J];
                   WillBreak = false;
                }

                //Bが得点する場合
                var NewJ = J + 1;
                if(I == pA && NewJ == pB) Answer += PrevDP[I][J];

                if((pN <= NewJ && NewJ - I >= 2) == false){
                    CurrDP[I][NewJ] += PrevDP[I][J];
                    WillBreak = false;
                }
            }
        }
        if(WillBreak) break;
        PrevDP = CurrDP;
    }
    document.write('N=' , pN , ',A=' , pA , ',B=' , pB , ' だと' , Answer , '通り<br>');
}

function DeriveDPArr(pA , pB)
{
    var DPArr = new Array(pA + 1);
    for(var I = 0 ; I <= pA ; I++){
        DPArr[I] = new Array(pB + 1);
        DPArr[I].fill(0);
    }
    return DPArr;
}

実行結果

N=3,A=4,B=2 だと6通り
N=11,A=25,B=24 だと3027042304通り

解説

動的計画法で解いてます。