ABC268-F Best Concatenation

問題へのリンク

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("3");
            WillReturn.Add("1X3");
            WillReturn.Add("59");
            WillReturn.Add("XXX");
            //71
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10");
            WillReturn.Add("X63X395XX");
            WillReturn.Add("X2XX3X22X");
            WillReturn.Add("13");
            WillReturn.Add("3716XXX6");
            WillReturn.Add("45X");
            WillReturn.Add("X6XX");
            WillReturn.Add("9238");
            WillReturn.Add("281X92");
            WillReturn.Add("1XX4X4XX6");
            WillReturn.Add("54X9X711X1");
            //3010
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct ItemDef : IComparable<ItemDef>
    {
        internal long XCnt;
        internal long NumSum;

        public int CompareTo(ItemDef pOtherIns)
        {
            long Sahen = XCnt * pOtherIns.NumSum;
            long Uhen = pOtherIns.XCnt * NumSum;
            return Uhen.CompareTo(Sahen);
        }
    }

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

        long BaseScore = 0;
        var ItemList = new List<ItemDef>();
        foreach (string EachStr in InputList.Skip(1)) {
            ItemDef WillAdd;
            WillAdd.NumSum = 0;
            WillAdd.XCnt = 0;
            foreach (char EachChar in EachStr) {
                if (EachChar == 'X') {
                    WillAdd.XCnt++;
                }
                else {
                    long Num = EachChar - '0';
                    WillAdd.NumSum += Num;
                }
            }
            ItemList.Add(WillAdd);
            BaseScore += DeriveScore(EachStr);
        }

        ItemList = ItemList.OrderBy(pX => pX).ToList();

        long XSum = 0;
        long ScoreSum = 0;
        foreach (ItemDef EachItem in ItemList) {
            ScoreSum += EachItem.NumSum * XSum;
            XSum += EachItem.XCnt;
        }
        Console.WriteLine(BaseScore + ScoreSum);
    }

    // 文字列を引数として、その文字列でのスコアを返す
    static long DeriveScore(string pStr)
    {
        long WillReturn = 0;
        long XCnt = 0;
        foreach (char EachChar in pStr) {
            if (EachChar == 'X') {
                XCnt++;
            }
            else {
                long Num = EachChar - '0';
                WillReturn += Num * XCnt;
            }
        }
        return WillReturn;
    }
}

解説

足し算には、分配法則
A * (B+C) = A*B + A*C
という法則があります。

なので、文字列内でのXによるスコア加算と
別の文字列のXによるスコア加算は、分けて考えることができます。

最初に、文字列内でのXによるスコア加算を求めておきます。

後は、各文字列がランダムに並んだ状態から、バブルソートの要領で交換可能と考えます。
交換したスコアの差は
(Xの個数,数値の和) を (X1 , N1)、(X2 , N2)として
交換しなければ、スコアはX1*N2
交換したら、スコアはX2*N1
とスコア合計が変わるので
バブルソートで交換を続けた結果を
クイックソートで高速に求めれば良いです。