第23回PAST E 分数のソート

問題へのリンク

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("2 3");
            WillReturn.Add("1 2");
            WillReturn.Add("3 5");
            //1 2
            //3 5
            //2 3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5");
            WillReturn.Add("1 5");
            WillReturn.Add("1 7");
            WillReturn.Add("6 5");
            WillReturn.Add("9 8");
            WillReturn.Add("9 4");
            //1 7
            //1 5
            //9 8
            //6 5
            //9 4
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10");
            WillReturn.Add("39 83");
            WillReturn.Add("93 70");
            WillReturn.Add("5 92");
            WillReturn.Add("81 67");
            WillReturn.Add("30 53");
            WillReturn.Add("57 5");
            WillReturn.Add("91 58");
            WillReturn.Add("21 85");
            WillReturn.Add("81 34");
            WillReturn.Add("37 38");
            //5 92
            //21 85
            //39 83
            //30 53
            //37 38
            //81 67
            //93 70
            //91 58
            //81 34
            //57 5
        }
        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();
    }

    struct SortableStruct : IComparable<SortableStruct>
    {
        internal long A;
        internal long B;

        public int CompareTo(SortableStruct pOtherIns)
        {
            long[] Sahen1 = GetNumArr(A);
            long[] Sahen2 = GetNumArr(pOtherIns.B);

            long[] Uhen1 = GetNumArr(pOtherIns.A);
            long[] Uhen2 = GetNumArr(B);

            long[] SahenResult = GetProd(Sahen1, Sahen2);
            long[] UhenResult = GetProd(Uhen1, Uhen2);

            for (long I = 0; I <= SahenResult.GetUpperBound(0); I++) {
                if (SahenResult[I] != UhenResult[I]) {
                    int Result = SahenResult[I].CompareTo(UhenResult[I]);
                    return Result;
                }
            }
            return 0;
        }

        // 配列に値を設定して返す
        private static long[] GetNumArr(long pVal)
        {
            long[] NumArr = new long[50];
            long CurrInd = NumArr.GetUpperBound(0);
            while (pVal > 0) {
                NumArr[CurrInd] += pVal % 10;
                pVal /= 10;
                CurrInd--;
            }
            return NumArr;
        }

        // 配列2つの掛け算の結果を返す
        private static long[] GetProd(long[] pNumArr1, long[] pNumArr2)
        {
            long[] ResultArr = new long[50];

            for (long I = pNumArr1.GetUpperBound(0); 0 <= I; I--) {
                if (pNumArr1[I] == 0) continue;
                for (long J = pNumArr2.GetUpperBound(0); 0 <= J; J--) {
                    if (pNumArr2[J] == 0) continue;
                    long Diff = pNumArr2.GetUpperBound(0) - J;
                    long TargetInd = I - Diff;
                    ResultArr[TargetInd] += pNumArr1[I] * pNumArr2[J];
                    if (ResultArr[TargetInd] > 9) {
                        ResultArr[TargetInd - 1] += ResultArr[TargetInd] / 10;
                        ResultArr[TargetInd] %= 10;
                    }
                }
            }

            for (long I = ResultArr.GetUpperBound(0); 0 <= I; I--) {
                if (ResultArr[I] > 9) {
                    ResultArr[I - 1] += ResultArr[I] / 10;
                    ResultArr[I] %= 10;
                }
            }
            return ResultArr;
        }
    }
    static List<SortableStruct> mSortableStructList = new List<SortableStruct>();

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

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

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            SortableStruct WillAdd;
            WillAdd.A = wkArr[0];
            WillAdd.B = wkArr[1];
            mSortableStructList.Add(WillAdd);
        }
        mSortableStructList.Sort();
        mSortableStructList.ForEach(pX => Console.WriteLine("{0} {1}", pX.A, pX.B));
    }
}

解説

10の18乗 * 10の18乗 はdecimal型でもオーバーフローするので
long型の配列を使用してます。