ARC-048-B AtCoderでじゃんけんを

■■■問題■■■

AtCoderじゃんけんの大会が開かれています。
AtCoderじゃんけんとは、2人で行う以下のようなゲームです。

●まず、2人がそれぞれ独立にグー、チョキ、パーのいずれかの手を出す。
●2人のAtCoderのレーティングが等しくなければ、
  レーティングが高いほうを勝者とする。
●2人のAtCoderのレーティングが等しく、2人の出した手が異なるならば、
  通常のじゃんけんの勝者を勝者とする。
●2人のAtCoderのレーティングが等しく、2人の出した手も等しいならば、
  引き分けとする。

大会にはN人の参加者がおり、大会期間中同じ参加者は同じ手を出し続け、
また大会期間中にレーティングが変化することはありません。

大会では、すべての参加者が、ほかのN-1人の参加者とちょうど1回ずつAtCoderじゃんけんをします。

それぞれの人のレーティングと出す手が与えられるので、
すべての参加者について、大会終了時の対戦成績が何勝何敗何引き分けかを答えてください。

ただし、通常のじゃんけんにおいては、
グーはチョキに、チョキはパーに、パーはグーに、それぞれ勝つものとします。

■■■入力■■■

N
R1 H1
・
・
・
RN HN

●1行目には、整数N(1 <= N <= 10万)が与えられる。
●続くN行には、i番目の参加者の情報を表す整数
  Ri,Hi(1 <= Ri <= 10万,1 <= Hi <= 3)が空白を区切りとして与えられる。
  これは、i番目の参加者のレーティングがRiで、
  出す手が Hi=1のときグー、Hi=2のときチョキ、Hi=3のときパーであることを表す。

■■■出力■■■

●出力はN行からなる。
●i行目には、i番目の参加者の勝ち数、負け数、引き分け数を表す整数3つを
  順に空白区切りで出力せよ。

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("6");
            WillReturn.Add("2 1");
            WillReturn.Add("2 2");
            WillReturn.Add("3 2");
            WillReturn.Add("5 3");
            WillReturn.Add("2 2");
            WillReturn.Add("3 3");
            //2 3 0
            //0 4 1
            //4 1 0
            //5 0 0
            //0 4 1
            //3 2 0
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2");
            WillReturn.Add("1999 3");
            WillReturn.Add("2000 1");
            //0 1 0
            //1 0 0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("8");
            WillReturn.Add("3200 2");
            WillReturn.Add("2800 3");
            WillReturn.Add("2800 2");
            WillReturn.Add("2700 1");
            WillReturn.Add("2800 2");
            WillReturn.Add("3200 1");
            WillReturn.Add("2700 1");
            WillReturn.Add("3200 3");
            //6 1 0
            //2 5 0
            //3 3 1
            //0 6 1
            //3 3 1
            //6 1 0
            //0 6 1
            //6 1 0
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct ResultInfoDef
    {
        internal int Cnt;
        internal int Win;
        internal int Draw;
        internal int Lose;
    }

    struct SplitInputDef
    {
        internal int Rate;
        internal int Te;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int N = int.Parse(InputList[0]);

        int[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(X => int.Parse(X)).ToArray();

        const int UB = 100000;
        ResultInfoDef[,] ResultInfoArr = new ResultInfoDef[UB + 1, 4];

        var SplitInputList = new List<SplitInputDef>(N);

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            SplitInputList.Add(new SplitInputDef() { Rate = wkArr[0], Te = wkArr[1] });
            ResultInfoArr[wkArr[0], wkArr[1]].Cnt++;
        }

        int PrevRateSum = 0;
        for (int I = 0; I <= UB; I++) {
            int CntG = ResultInfoArr[I, 1].Cnt;
            int CntT = ResultInfoArr[I, 2].Cnt;
            int CntP = ResultInfoArr[I, 3].Cnt;
            if (CntG == 0 && CntT == 0 && CntP == 0) continue;

            //グーの場合
            ResultInfoArr[I, 1].Win = PrevRateSum + CntT;
            ResultInfoArr[I, 1].Draw = CntG - 1;
            ResultInfoArr[I, 1].Lose = N - PrevRateSum - CntT - CntG;

            //チョキの場合
            ResultInfoArr[I, 2].Win = PrevRateSum + CntP;
            ResultInfoArr[I, 2].Draw = CntT - 1;
            ResultInfoArr[I, 2].Lose = N - PrevRateSum - CntP - CntT;

            //パーの場合
            ResultInfoArr[I, 3].Win = PrevRateSum + CntG;
            ResultInfoArr[I, 3].Draw = CntP - 1;
            ResultInfoArr[I, 3].Lose = N - PrevRateSum - CntG - CntP;

            PrevRateSum += CntG + CntT + CntP;
        }

        SplitInputList.ForEach(X =>
            Console.WriteLine("{0} {1} {2}",
                ResultInfoArr[X.Rate, X.Te].Win,
                ResultInfoArr[X.Rate, X.Te].Lose,
                ResultInfoArr[X.Rate, X.Te].Draw));
    }
}

解説

nの上限が10万ですので、
計算量のオーダーがnの2乗を超えないようにアルゴリズムを工夫してます。