魔法少女Madokaは魔女Walpurgisnachtと戦っていた。 Walpurgisnachtは複数の使い魔を使役しているため、短時間ですべての敵にダメージを与えない限り倒せない。 そこでMadokaは範囲に対する攻撃魔法を使用し、効率的に敵を倒そうと考えた。 Walpurgisnachtとその使い魔の座標と体力、Madokaが攻撃した範囲と敵に与えるダメージが与えられるので、 倒せていない敵の残り体力の合計を答えよ。
N K X1 Y1 HP1 X2 Y2 HP2 ・ ・ ・ XN YN HPN AX1 AY1 W1 H1 D1 AX2 AY2 W2 H2 D2 ・ ・ ・ AXK AYK WK HK DK 入力はすべて整数で与えられる。 ●1 <= N <= 100000 は敵の数を表す ●1 <= K <= 100000 はMadokaの攻撃回数を表す ●-500 <= Xk,Yk <= 500 は k番目の敵の座標を表す ●1 <= HPk <= 10000 は k番目の敵の体力を表す ●-500 <= AXt,AYt <= 500 ●1 <= Wt,Ht <= 500 ●1 <= Dt <= 10000 ●t回目の攻撃では AXt <= X <= AXt+Wt かつ AYt <= Y <= AYt+Ht を満たすすべての敵にDのダメージを与える。 ●同じ座標に複数の敵が存在することはないとする ●同じ攻撃が複数回行われることもある
敵は体力以上のダメージを受けると倒れるものとし、 倒れていない敵の体力の合計を計算し出力せよ。
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("7 2");
WillReturn.Add("0 0 1");
WillReturn.Add("1 0 1");
WillReturn.Add("1 1 2");
WillReturn.Add("1 2 1");
WillReturn.Add("2 0 1");
WillReturn.Add("2 1 1");
WillReturn.Add("2 2 1");
WillReturn.Add("-1 -1 2 2 1");
WillReturn.Add("1 0 1 2 1");
//0
//すべての敵を倒したので残り体力の合計は0
}
else if (InputPattern == "Input2") {
WillReturn.Add("4 1");
WillReturn.Add("1 0 1");
WillReturn.Add("1 2 1");
WillReturn.Add("2 0 2");
WillReturn.Add("2 1 1");
WillReturn.Add("-1 -1 3 3 2");
//0
}
else if (InputPattern == "Input3") {
WillReturn.Add("4 1");
WillReturn.Add("1 0 2");
WillReturn.Add("1 2 1");
WillReturn.Add("2 0 1");
WillReturn.Add("2 1 1");
WillReturn.Add("-1 0 3 3 1");
//1
}
else if (InputPattern == "Input4") {
WillReturn.Add("10 10");
WillReturn.Add("-444 -456 6808");
WillReturn.Add("465 31 3659");
WillReturn.Add("-16 103 7545");
WillReturn.Add("199 342 7710");
WillReturn.Add("374 -206 4493");
WillReturn.Add("-15 -286 2504");
WillReturn.Add("-287 155 8841");
WillReturn.Add("-345 -444 3170");
WillReturn.Add("-7 304 9561");
WillReturn.Add("-143 -456 279");
WillReturn.Add("-349 154 13 268 3811");
WillReturn.Add("-40 256 150 80 8822");
WillReturn.Add("486 270 394 337 5486");
WillReturn.Add("310 -342 92 195 6358");
WillReturn.Add("111 -243 209 445 5669");
WillReturn.Add("-224 -120 197 31 904");
WillReturn.Add("436 -206 50 25 7802");
WillReturn.Add("-394 -493 409 229 4934");
WillReturn.Add("-388 367 136 14 3866");
WillReturn.Add("-79 -157 37 426 1670");
//35302
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
const int UB = 1000;
const int OriginTyousei = 500;
struct MonsterInfo
{
internal int X;
internal int Y;
internal int HP;
}
static void Main()
{
List<string> InputList = GetInputList();
int[] wkArr = { };
Action<string> SplitAct = pStr =>
wkArr = pStr.Split(' ').Select(X => int.Parse(X)).ToArray();
SplitAct(InputList[0]);
int N = wkArr[0];
MonsterInfo[] MonsterArr = new MonsterInfo[N];
for (int I = 1; I <= N; I++) {
SplitAct(InputList[I]);
MonsterArr[I - 1].X = wkArr[0] + OriginTyousei;
MonsterArr[I - 1].Y = wkArr[1] + OriginTyousei;
MonsterArr[I - 1].HP = wkArr[2];
}
int[,] ImosArr = new int[UB + 1, UB + 1];
for (int I = N + 1; I <= InputList.Count - 1; I++) {
SplitAct(InputList[I]);
int StaX = wkArr[0] + OriginTyousei;
int StaY = wkArr[1] + OriginTyousei;
int EndX = StaX + wkArr[2] + 1;
int EndY = StaY + wkArr[3] + 1;
int Damage = wkArr[4];
ImosArr[StaX, StaY] += Damage;
if (EndX < UB) ImosArr[EndX, StaY] -= Damage;
if (EndY < UB) ImosArr[StaX, EndY] -= Damage;
if (EndX < UB && EndY < UB) ImosArr[EndX, EndY] += Damage;
}
Console.WriteLine("累積和の取得前");
PrintBan(ImosArr);
//横方向の累積和を求める
for (int X = 1; X <= UB; X++) {
for (int Y = 0; Y <= UB; Y++) {
ImosArr[X, Y] += ImosArr[X - 1, Y];
}
}
Console.WriteLine("横方向の累積和の取得結果");
PrintBan(ImosArr);
//縦方向の累積和を求める
for (int Y = 1; Y <= UB; Y++) {
for (int X = 0; X <= UB; X++) {
ImosArr[X, Y] += ImosArr[X, Y - 1];
}
}
Console.WriteLine("縦方向の累積和の取得結果");
PrintBan(ImosArr);
int Answer = 0;
foreach (MonsterInfo EachMonster in MonsterArr) {
int CurrX = EachMonster.X;
int CurrY = EachMonster.Y;
int RestHP = EachMonster.HP - ImosArr[CurrX, CurrY];
if (RestHP > 0)
Answer += RestHP;
}
Console.WriteLine(Answer);
}
static void PrintBan(int[,] pImosArr)
{
var sb = new System.Text.StringBuilder();
for (int Y = 498; Y <= 503; Y++) {
for (int X = 498; X <= 503; X++) {
sb.AppendFormat("{0,2},", pImosArr[X, Y]);
}
sb.AppendLine();
}
Console.WriteLine(sb.ToString());
}
}
累積和の取得前 0, 0, 0, 0, 0, 0, 0, 1, 0, 0,-1, 0, 0, 0, 0, 1, 0,-1, 0, 0, 0, 0, 0, 0, 0,-1, 0, 0, 1, 0, 0, 0, 0,-1, 0, 1, 横方向の累積和の取得結果 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,-1,-1,-1, 0, 0, 0, 0, 0,-1,-1, 0, 縦方向の累積和の取得結果 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 2, 1, 0, 0, 1, 1, 2, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0
2次元いもす法で解いてます。