結果

問題 No.107 モンスター
ユーザー 明智重蔵明智重蔵
提出日時 2016-01-28 06:26:17
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 84 ms / 5,000 ms
コード長 3,755 bytes
コンパイル時間 3,543 ms
コンパイル使用メモリ 105,548 KB
実行使用メモリ 30,812 KB
最終ジャッジ日時 2023-08-22 23:16:42
合計ジャッジ時間 6,250 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 60 ms
21,828 KB
testcase_01 AC 59 ms
19,732 KB
testcase_02 AC 59 ms
21,976 KB
testcase_03 AC 60 ms
21,764 KB
testcase_04 AC 59 ms
21,744 KB
testcase_05 AC 57 ms
21,736 KB
testcase_06 AC 59 ms
21,736 KB
testcase_07 AC 59 ms
23,816 KB
testcase_08 AC 60 ms
21,924 KB
testcase_09 AC 59 ms
21,936 KB
testcase_10 AC 59 ms
21,864 KB
testcase_11 AC 60 ms
21,784 KB
testcase_12 AC 58 ms
21,712 KB
testcase_13 AC 66 ms
23,304 KB
testcase_14 AC 77 ms
23,428 KB
testcase_15 AC 81 ms
23,600 KB
testcase_16 AC 60 ms
21,816 KB
testcase_17 AC 61 ms
20,316 KB
testcase_18 AC 70 ms
30,644 KB
testcase_19 AC 73 ms
30,592 KB
testcase_20 AC 72 ms
23,344 KB
testcase_21 AC 68 ms
23,328 KB
testcase_22 AC 77 ms
25,680 KB
testcase_23 AC 84 ms
30,812 KB
testcase_24 AC 78 ms
30,680 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4");
            WillReturn.Add("-90 230 -120 120");
            //240
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("4");
            WillReturn.Add("-10 -300 100 100");
            //0
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("4");
            WillReturn.Add("-40 -60 210 -110");
            //50
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    //No.107 モンスター
    //http://yukicoder.me/problems/102
    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 ((I & DeriveOmomi(J, DArrUB)) == 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 (int I = 0; I <= pDP.GetUpperBound(0); I++) {
            Console.WriteLine("{0,4}での最大HPは{1}", Convert.ToString(I, 2), pDP[I]);
        }
    }
}
0