結果

問題 No.107 モンスター
コンテスト
ユーザー 明智重蔵
提出日時 2016-01-28 06:26:17
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 59 ms / 5,000 ms
コード長 3,755 bytes
コンパイル時間 974 ms
コンパイル使用メモリ 112,108 KB
実行使用メモリ 34,348 KB
最終ジャッジ日時 2024-12-18 02:00:54
合計ジャッジ時間 2,769 ms
ジャッジサーバーID
（参考情報） 		judge2 / 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
        }
        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