No.107 モンスター

■■■問題■■■

N匹のモンスターがいる。モンスターには2種類ある。
悪いモンスターと良いモンスターの2種類である。

悪いモンスターとは1匹に対し1回戦わないといけない。
戦うと体力が減りレベルが1上がる。
レベルが1上がると最大体力が100上がる。
もし体力が減って0以下になればそこで終了する。

良いモンスターは1匹につき1回だけ体力を回復してくれる。
ただし、回復する体力は最大体力を超えることはない。
自分の最初の体力は100で最大体力も100である。

悪いモンスターをすべて倒したい。
また、最後に残った体力をできるだけ多くしたい。
モンスターには自由な順番で出会える。

最後までどれだけの体力を残せるだろうか？
どのようにしても途中で体力が0以下になる場合は0を答えとする。

ただし、良いモンスターを倒すことは出来ない。

■■■入力■■■

N
D1 D2  ・・・  DN

Nはモンスターの総数。1 <= N <= 16 (Nは正の整数)
Diはi番目のモンスターの情報。
Diが正の数であれば良いモンスターで|Di|だけ回復してくれる。
Diが負の数であれば悪いモンスターで倒すのに|Di|だけ体力を使う。
-1600 <= Di < 0、0 < Di <= 1600。(Diは0以外の整数)

■■■出力■■■

最後の時点での体力の最大値を1行で出力せよ。
どうがんばっても途中で体力が0以下になる場合には0を1行で出力せよ。
最後に改行を忘れずに。

C#のソース

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

class Program
{
    static string InputPattern = "Input1";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("3");
            WillReturn.Add("-90 50 50");
            //110
            //最初に1番目の悪いモンスターと戦う。
            //体力が10になり、最大体力が200になる。
            //2,3番目の2匹の良いモンスターに体力を50ずつ回復してもらう。
            //最終的な体力は110になる。
            //もし、先に回復を行っても体力は最大体力の100より増えない。
            //この場合、最後に戦うと最終的な体力は10になる。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4");
            WillReturn.Add("-90 230 -120 120");
            //240
            //1番目の悪いモンスターと戦う。
            //体力は10、最大体力は200になる。
            //4番目の良いモンスターに回復してもらう。
            //体力は130になる。
            //3番目の悪いモンスターと戦う。
            //体力は10、最大体力は300になる。
            //2番目の良いモンスターに回復してもらう。
            //体力は240になる。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("4");
            WillReturn.Add("-10 -300 100 100");
            //0
            //1番目の悪いモンスターと戦うと体力が90に減り最大体力は200になる。
            //3,4番目の良いモンスターに体力200まで回復してもらうことはできる。
            //しかし、どうがんばっても2番目の悪いモンスターと戦うと体力は0以下になる。
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("4");
            WillReturn.Add("-40 -60 210 -110");
            //50
            //2番目の悪いモンスターと戦う。
            //体力は40、最大体力は200になる。
            //3番目の良いモンスターに回復してもらう。
            //最大体力を超えられないので体力は200になる。
            //1,4番目の悪いモンスターと戦う。
            //体力は50になる。
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] DArr = InputList[1].Split(' ').Select(X => long.Parse(X)).ToArray();
        long DArrUB = DArr.GetUpperBound(0);

        long AllBitOn = 0;
        for (long I = 0; I <= DArrUB; I++) {
            AllBitOn |= DeriveOmomi(I, DArrUB);
        }

        //最大の体力[ビット位置に対応したモンスターの存在有無]なDP表
        long[] PrevDP = new long[AllBitOn + 1];
        PrevDP[AllBitOn] = 100;

        //悪いモンスターのビット位置の論理和を求める
        long BadMonsterBit = 0;
        for (long I = 0; I <= DArrUB; I++) {
            if (DArr[I] < 0) {
                BadMonsterBit |= DeriveOmomi(I, DArrUB);
            }
        }

        long Answer = 0;
        while (Array.Exists(PrevDP, X => X > 0)) {
            long[] CurrDP = new long[AllBitOn + 1];
            for (long I = 0; I <= AllBitOn; I++) {
                if (PrevDP[I] == 0) continue;

                //最大HPを求める
                long MaxHP = 100;
                for (long J = 0; J <= DArrUB; J++) {
                    long CurrBit = DeriveOmomi(J, DArrUB);
                    if ((I & CurrBit) > 0) continue;
                    if ((BadMonsterBit & CurrBit) > 0) MaxHP += 100;
                }

                //ビット列を走査する
                for (long J = 0; J <= DArrUB; J++) {
                    long wkBitProd = I & DeriveOmomi(J, DArrUB);
                    if (wkBitProd == 0) continue;

                    long NewI = I - wkBitProd;
                    long NewVal = PrevDP[I] + DArr[J];
                    if (NewVal > MaxHP) NewVal = MaxHP;
                    if (NewVal <= 0) continue;

                    if (CurrDP[NewI] < NewVal) CurrDP[NewI] = NewVal;
                }
            }
            if (Answer < CurrDP[0]) Answer = CurrDP[0];
            Console.WriteLine("DPの結果");
            PrintDP(CurrDP);
            PrevDP = CurrDP;
        }
        Console.WriteLine(Answer);
    }

    //添え字に対応した2進数での桁の重みを返す
    static long DeriveOmomi(long pInd, long pUB)
    {
        return DeriveBekijyou2(pUB - pInd);
    }

    //2のべき乗を返す
    static long DeriveBekijyou2(long pJyousuu)
    {
        long WillReturn = 1;
        for (long I = 1; I <= pJyousuu; I++) {
            WillReturn *= 2;
        }
        return WillReturn;
    }

    static void PrintDP(long[] pDP)
    {
        for (long I = 0; I <= pDP.GetUpperBound(0); I++) {
            Console.WriteLine("{0,4}での最大HPは{1}", Convert.ToString(I, 2), pDP[I]);
        }
    }
}

デバッグ情報付の実行結果

DPの結果
   0での最大HPは0
   1での最大HPは0
  10での最大HPは0
  11での最大HPは10
 100での最大HPは0
 101での最大HPは100
 110での最大HPは100
 111での最大HPは0
DPの結果
   0での最大HPは0
   1での最大HPは60
  10での最大HPは60
  11での最大HPは0
 100での最大HPは100
 101での最大HPは0
 110での最大HPは0
 111での最大HPは0
DPの結果
   0での最大HPは110
   1での最大HPは0
  10での最大HPは0
  11での最大HPは0
 100での最大HPは0
 101での最大HPは0
 110での最大HPは0
 111での最大HPは0
DPの結果
   0での最大HPは0
   1での最大HPは0
  10での最大HPは0
  11での最大HPは0
 100での最大HPは0
 101での最大HPは0
 110での最大HPは0
 111での最大HPは0
110

解説

BitDPで解いてます。