ARC168-A <Inversion>

問題へのリンク

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("4");
            WillReturn.Add("<><");
            //1
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2");
            WillReturn.Add("<");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10");
            WillReturn.Add(">>>>>>>>>");
            //45
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("30");
            WillReturn.Add("<<><>>><><>><><><<>><<<><><<>");
            //19
        }
        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();
        string S = InputList[1];

        var RunLenInfoArr = RunLen.DeriveRunLenInfoArr(S);

        long Answer = 0;
        foreach (var EachRunLenInfo in RunLenInfoArr) {
            if (EachRunLenInfo.AppearChar == '>') {
                long CurrRunLen = EachRunLenInfo.RunLen;
                Answer += CurrRunLen * (CurrRunLen + 1) / 2;
            }
        }
        Console.WriteLine(Answer);
    }
}

/*
    // 使用例1
    RunLen.RunLenInfo[] RunLenInfoArr1 = RunLen.DeriveRunLenInfoArr("abbccc");

    // 使用例2
    foreach (RunLen.RunLenInfo EachRunLenInfo in RunLen.DeriveRunLenInfoArr("abbccc")) {
        Console.WriteLine("AppearChar={0},RunLen={1}",
            EachRunLenInfo.AppearChar, EachRunLenInfo.RunLen);
    }
*/
#region RunLen
// ランレングス圧縮(文字列)
internal class RunLen
{
    // ランレングス圧縮情報
    internal struct RunLenInfo
    {
        internal char AppearChar;
        internal int RunLen;
    }

    // ランレングス圧縮結果を返す
    internal static RunLenInfo[] DeriveRunLenInfoArr(string pBaseStr)
    {
        var RunLenInfoList = new List<RunLenInfo>();

        int StrUB = pBaseStr.Length - 1;
        char PrevChar = pBaseStr[0];
        int StrLen = 0;
        for (int I = 0; I <= StrUB; I++) {
            if (pBaseStr[I] != PrevChar) {
                RunLenInfo WillAdd;
                WillAdd.AppearChar = PrevChar;
                WillAdd.RunLen = StrLen;
                RunLenInfoList.Add(WillAdd);
                StrLen = 0;
                PrevChar = pBaseStr[I];
            }
            StrLen++;

            if (I == StrUB) {
                RunLenInfo WillAdd;
                WillAdd.AppearChar = pBaseStr[I];
                WillAdd.RunLen = StrLen;
                RunLenInfoList.Add(WillAdd);
            }
        }
        return RunLenInfoList.ToArray();
    }
}
#endregion

解説

デカルト平面で図を書いて考えると解けます。

転倒数は、バルルソートでの交換回数なので、
これを最小化するのであれば、
増加の際には、際限なく増加させる。
減少の際には、なるべく小さい減少とする。(たとえば0.0000000000000001刻み)
これが最適と分かります。

例
+ - - - +  +   +   -   -
9 8 7 6 9 99 999 998 997

上記では整数を使用してますが、
実際のところは、実数で0.0000000000000001刻みの減少で良いです。

以上により、
RLEし、マイナスの連続数に対し
1からnまでの自然数の和の公式の
総和が解だと分かります。