ABC216-F Max Sum Counting

問題へのリンク

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("2");
            WillReturn.Add("3 1");
            WillReturn.Add("1 2");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2");
            WillReturn.Add("1 1");
            WillReturn.Add("2 2");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("20");
            WillReturn.Add("1937 3980 2689 1208 3640 1979 581 2271 4229 3948 3708 1522 4161 4661 3797 96 3388 3395 2920 2247");
            WillReturn.Add("4485 2580 174 1156 3770 3396 3558 3500 3494 479 269 3383 1230 1711 3545 3919 134 475 3796 1017");
            //476
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    const int Hou = 998244353;

    struct ABPairInfoDef
    {
        internal int A;
        internal int B;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] AArr = InputList[1].Split(' ').Select(pX => int.Parse(pX)).ToArray();
        int[] BArr = InputList[2].Split(' ').Select(pX => int.Parse(pX)).ToArray();
        int UB = AArr.GetUpperBound(0);

        var ABPairInfoList = new List<ABPairInfoDef>();
        for (int I = 0; I <= UB; I++) {
            ABPairInfoDef WillAdd;
            WillAdd.A = AArr[I];
            WillAdd.B = BArr[I];
            ABPairInfoList.Add(WillAdd);
        }

        ABPairInfoList = ABPairInfoList.OrderBy(pX => pX.A).ToList();

        int MaxA = AArr.Max();

        // 場合の数[Bの合計]なDP表
        int[] DPArr = new int[MaxA + 1];
        DPArr[0] = 1;

        int Answer = 0;
        for (int I = 0; I <= UB; I++) {
            for (int J = MaxA; 0 <= J; J--) {
                if (DPArr[J] == 0) continue;

                int NewJ = J + ABPairInfoList[I].B;
                if (NewJ > MaxA) continue;

                DPArr[NewJ] += DPArr[J];
                DPArr[NewJ] %= Hou;

                // 解に計上
                if (NewJ <= ABPairInfoList[I].A) {
                    Answer += DPArr[J];
                    Answer %= Hou;
                }
            }
        }
        Console.WriteLine(Answer);
    }
}

解説

Aが3 1 4 1 5 9 2
Bが6 5 3 5 8 9 7
として、
AはMax
BはSum
を見るので、Aの昇順にソートします。

すると、Bを順に走査しつつ、
場合の数[Bの合計] をDPで更新すれば良いと分かります。

DPを更新したときのBの添字で、Aの値を参照して、
Aの方が大きかったら、解に計上してます。