CodeQUEEN 2026 決勝 F ピアノの練習

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("5 2 1 2 2");
            //7
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5 5 2 2 4");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("20 7 4 3 5");
            //77520
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("100 50 10 6 7");
            //591911044
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    const long Hou = 998244353;

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = GetSplitArr(InputList[0]);
        long N = wkArr[0];
        long K = wkArr[1];
        long A = wkArr[2];
        long B = wkArr[3];
        long D = wkArr[4];

        // 場合の数[何個置いたか,残り腕,残り指,置ける場所のMax]
        long UB0 = K;
        long UB1 = A;
        long UB2 = B;
        long UB3 = N;

        long[, , ,] DPArr = new long[UB0 + 1, UB1 + 1, UB2 + 1, UB3 + 1];
        DPArr[0, A, B, 0] = 1;

        for (long LoopI = 1; LoopI <= N; LoopI++) {
            // 配るDP
            for (long LoopJ = UB0; 0 <= LoopJ; LoopJ--) {
                if (LoopJ == K) continue;
                for (long LoopK = UB1; 0 <= LoopK; LoopK--) {
                    for (long LoopL = UB2; 0 <= LoopL; LoopL--) {
                        for (long LoopM = UB3; 0 <= LoopM; LoopM--) {
                            if (DPArr[LoopJ, LoopK, LoopL, LoopM] == 0) continue;

                            Action<long, long, long, long> SendAct = (pNewJ, pNewK, pNewL, pNewM) =>
                            {
                                if (pNewK < 0) return;
                                if (pNewL < 0) return;
                                pNewM = Math.Min(N, pNewM);

                                DPArr[pNewJ, pNewK, pNewL, pNewM] += DPArr[LoopJ, LoopK, LoopL, LoopM];
                                DPArr[pNewJ, pNewK, pNewL, pNewM] %= Hou;
                            };

                            // 置いてる最中でない場合
                            if (LoopL == B) {
                                // 新しい腕を使う遷移
                                SendAct(LoopJ + 1, LoopK - 1, B - 1, LoopI + D);
                                continue;
                            }

                            // 指を使えるなら、使う必要あり
                            bool MustUseFinger = false;
                            if (LoopL > 0 && LoopI <= LoopM) {
                                MustUseFinger = true;
                            }

                            // 場合の数[何個置いたか,残り腕,残り指,置ける場所のMax]
                            if (MustUseFinger) {
                                // 指を使う
                                SendAct(LoopJ + 1, LoopK, LoopL - 1, LoopM);
                            }
                            else {
                                // 新しい腕を使う遷移
                                SendAct(LoopJ + 1, LoopK - 1, B - 1, LoopI + D);
                            }
                        }
                    }
                }
            }
        }

        long Answer = 0;
        for (long LoopJ = UB0; 0 <= LoopJ; LoopJ--) {
            if (LoopJ < K) continue;
            for (long LoopK = UB1; 0 <= LoopK; LoopK--) {
                for (long LoopL = UB2; 0 <= LoopL; LoopL--) {
                    for (long LoopM = UB3; 0 <= LoopM; LoopM--) {
                        Answer += DPArr[LoopJ, LoopK, LoopL, LoopM];
                        Answer %= Hou;
                    }
                }
            }
        }
        Console.WriteLine(Answer);
    }
}

解説

使う腕を増やすことなく、使う指を増やすことで対応できる場合は、
必ず指を使う遷移とすることで、
配置と、状態を1対1でマッピングできます。

これをふまえて
場合の数[何個置いたか,残り腕,残り指,置ける場所のMax]
を更新してます。

「何個置いたか」は、遷移で必ず増えるので
これを添字の0番目とし、for文でリバースループすれば
インラインDPにできます。