結果

問題 No.107 モンスター
ユーザー aketijyuuzou
提出日時 2024-10-10 22:44:57
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 51 ms / 5,000 ms
コード長 5,299 bytes
コンパイル時間 930 ms
コンパイル使用メモリ 116,316 KB
実行使用メモリ 28,032 KB
最終ジャッジ日時 2024-10-10 22:44:59
合計ジャッジ時間 2,818 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

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("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]);
        }
    }
}
0