ABC443-D Pawn Line

問題へのリンク

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("5");
            WillReturn.Add("5 2 1 3 4");
            WillReturn.Add("2");
            WillReturn.Add("1 1");
            WillReturn.Add("3");
            WillReturn.Add("1 3 1");
            WillReturn.Add("9");
            WillReturn.Add("9 9 8 2 4 4 3 5 3");
            WillReturn.Add("20");
            WillReturn.Add("7 4 6 2 15 5 17 15 1 8 18 1 5 1 12 11 2 7 8 14");
            //4
            //0
            //1
            //16
            //105
        }
        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);

        for (int I = 2; I <= InputList.Count - 1; I += 2) {
            SplitAct(InputList[I]);
            long Result = Solve(wkArr);
            Console.WriteLine(Result);
        }
    }

    static long Solve(long[] pPornArr)
    {
        long UB = pPornArr.GetUpperBound(0);

        long CostSum = 0;
        Action<long, long> ExecAdjust = (pInd1, pInd2) =>
        {
            if (pInd1 < 0 || UB < pInd1) return;
            if (pInd2 < 0 || UB < pInd2) return;

            long Y1 = pPornArr[pInd1];
            long Y2 = pPornArr[pInd2];

            if (Math.Abs(Y1 - Y2) > 1) {
                if (Y1 < Y2) {
                    long Goal = Y1 + 1;
                    CostSum += Math.Abs(Goal - Y2);
                    pPornArr[pInd2] = Goal;
                }
                else {
                    long Goal = Y2 + 1;
                    CostSum += Math.Abs(Goal - Y1);
                    pPornArr[pInd1] = Goal;
                }
            }
        };
        for (long I = 0; I <= UB; I++) {
            ExecAdjust(I, I + 1);
        }
        for (long I = UB; 0 <= I; I--) {
            ExecAdjust(I, I - 1);
        }

        return CostSum;
    }
}

解説

ハナヤマのキングチェスで考察します。

□□□□□□□●
●□□□□□□□
□□□□□□□□
□□□□□●□□
□□●□□□□□
□□□□●□●□
□●□●□□□□
□□□□□□□□

左から右に隣接ペアを見て、上に移動しないといけないポーンなら上に移動。
それから
右から左に隣接ペアを見て、上に移動しないといけないポーンなら上に移動。
として解くことができます。

考察すると
最初の、配列の左から右の走査により、各ポーンは、右のポーンと隣接することができます。
次の  、配列の右から左の走査により、各ポーンは、左のポーンと隣接することができます。
以上により正順と逆順の2回の配列走査で解くことができます。