AtCoderのABC    前のABCの問題へ

ABC462-E Alternating Costs


問題へのリンク


C#のソース

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("5");
            WillReturn.Add("1 2 -1 2");
            WillReturn.Add("8 5 0 0");
            WillReturn.Add("7 13 9 4");
            WillReturn.Add("1 1 0 100");
            WillReturn.Add("31 9 -74 -60");
            //4
            //0
            //103
            //100
            //1332
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        long[] wkArr = { };
        Action<string> SplitAct = (pStr) => wkArr = GetSplitArr(pStr);

        foreach (string EacgStr in InputList.Skip(1)) {
            SplitAct(EacgStr);
            long A = wkArr[0];
            long B = wkArr[1];
            long X = wkArr[2];
            long Y = wkArr[3];
            long Answer = Solve(A, B, X, Y);
            Console.WriteLine(Answer);
        }
    }

    static long Solve(long A, long B, long X, long Y)
    {
        X = Math.Abs(X);
        Y = Math.Abs(Y);

        // コスト1を計算
        var AnswerList = new List<long>();
        long MinDiff = Math.Min(X, Y);

        AnswerList.Add((MinDiff + MinDiff) * A);
        AnswerList.Add((MinDiff + MinDiff) * B);

        long FirstCost = AnswerList.Min();

        long RestX = X - MinDiff;
        long RestY = Y - MinDiff;

        long MoveACnt = 0;
        long MoveBCnt = 0;

        if (RestX > 0) {
            MoveACnt = RestX / 2;
            MoveBCnt = RestX / 2;
            long Mod = RestX % 2;
            if (Mod == 1) {
                MoveACnt++;
            }
        }
        if (RestY > 0) {
            MoveACnt = RestY / 2;
            MoveBCnt = RestY / 2;
            long Mod = RestY % 2;
            if (Mod == 1) {
                MoveBCnt++;
            }
        }

        long CostA = Math.Min(A, B * 3);
        long CostB = Math.Min(B, A * 3);

        long LastCost = MoveACnt * CostA + MoveBCnt * CostB;

        return FirstCost + LastCost;
    }
}


解説

オセロセットで、以下の図で考えます。

□□□□□□□G
□□□□□□□□
□□□□□□□□
S□□□□□□□

45度移動は、AだけかBだけで移動できるので
安いほうで移動し、以下の状態になります。

□□□C□□□G
□□□□□□□□
□□□□□□□□
S□□□□□□□

CからGまでの移動は、AとBの交互移動で移動可能ですが
Aは3回のBで代替可能
Bは3回のAで代替可能
ですので、これをふまえて最小コストを求めれば解くことができます。