ARC004-C 平均値太郎の憂鬱

問題へのリンク

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/3");
            //3 2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4/6");
            //Impossible
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("49995/10");
            //10000 10000
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("1/400");
            //Impossible
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    class BunsuClass
    {
        internal decimal Bunsi;
        internal decimal Bunbo;
    }

    static int BunsuCompareTo(BunsuClass p1, BunsuClass p2)
    {
        decimal Sahen = p1.Bunsi / p1.Bunbo;
        decimal Uhen = p2.Bunsi / p2.Bunbo;

        return Sahen.CompareTo(Uhen);
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        InputList[0] = InputList[0];
        string[] SplitArr = InputList[0].Split('/');
        decimal Bunsi = decimal.Parse(SplitArr[0]);
        decimal Bunbo = decimal.Parse(SplitArr[1]);

        if (Bunsi > 0) {
            decimal GCD = DeriveGCD2(Bunsi, Bunbo);
            Bunsi /= GCD;
            Bunbo /= GCD;
        }
        var AnswerBunsu = new BunsuClass();
        AnswerBunsu.Bunsi = Bunsi;
        AnswerBunsu.Bunbo = Bunbo;

        // Nの下限を二分探索
        BunsuClass MinAVG;
        BunsuClass MaxAVG;
        SetWrongAVG(1, out MinAVG, out  MaxAVG);

        decimal L = 1;
        decimal R = 999999999999;
        while (L + 1 < R) {
            decimal Mid = Math.Truncate((L + R) / 2);

            SetWrongAVG(Mid, out MinAVG, out  MaxAVG);

            if (BunsuCompareTo(MaxAVG, AnswerBunsu) < 0) {
                L = Mid;
            }
            else {
                R = Mid;
            }
        }
        decimal NMin = L;

        // Nの上限を二分探索
        L = 1;
        R = 999999999999;
        while (L + 1 < R) {
            decimal Mid = Math.Truncate((L + R) / 2);

            SetWrongAVG(Mid, out MinAVG, out  MaxAVG);

            if (BunsuCompareTo(MinAVG, AnswerBunsu) > 0) {
                R = Mid;
            }
            else {
                L = Mid;
            }
        }
        decimal NMax = R;

        bool HasAnswer = false;
        for (decimal LoopN = NMin - 100; LoopN <= NMax + 100; LoopN++) {
            if (LoopN < 1) continue;
            SetWrongAVG(LoopN, out MinAVG, out  MaxAVG);
            int Compare1 = BunsuCompareTo(MinAVG, AnswerBunsu);
            if (Compare1 > 0) continue;

            int Compare2 = BunsuCompareTo(AnswerBunsu, MaxAVG);
            if (Compare2 > 0) continue;

            decimal Sahen = LoopN * (LoopN + 1) / 2;
            decimal Uehn = AnswerBunsu.Bunsi;
            if (LoopN % AnswerBunsu.Bunbo > 0) continue;
            Uehn *= LoopN / AnswerBunsu.Bunbo;

            // 移項する
            Sahen -= Uehn;

            if (1 <= Sahen && Sahen <= LoopN) {
                Console.WriteLine("{0} {1}", LoopN, Sahen);
                HasAnswer = true;
            }
        }
        if (HasAnswer == false) {
            Console.WriteLine("Impossible");
        }
    }

    // Nを引数とし、間違った平均値の最小と最大を設定
    static void SetWrongAVG(decimal pN, out BunsuClass pMinAVG, out BunsuClass pMaxAVG)
    {
        decimal Sum = pN * (pN + 1) / 2;

        pMinAVG = new BunsuClass();
        pMinAVG.Bunsi = Sum - pN;
        pMinAVG.Bunbo = pN;
        if (pMinAVG.Bunsi > 0) {
            decimal GCD1 = DeriveGCD2(pMinAVG.Bunsi, pMinAVG.Bunbo);
            pMinAVG.Bunsi /= GCD1;
            pMinAVG.Bunbo /= GCD1;
        }

        pMaxAVG = new BunsuClass();
        pMaxAVG.Bunsi = Sum - 1;
        pMaxAVG.Bunbo = pN;
        if (pMaxAVG.Bunsi > 0) {
            decimal GCD2 = DeriveGCD2(pMaxAVG.Bunsi, pMaxAVG.Bunbo);
            pMaxAVG.Bunsi /= GCD2;
            pMaxAVG.Bunbo /= GCD2;
        }
    }

    // ユークリッドの互除法で2数の最大公約数を求める
    static decimal DeriveGCD2(decimal pVal1, decimal pVal2)
    {
        decimal WarareruKazu = pVal2;
        decimal WaruKazu = pVal1;

        while (true) {
            decimal Amari = WarareruKazu % WaruKazu;
            if (Amari == 0) return WaruKazu;
            WarareruKazu = WaruKazu;
            WaruKazu = Amari;
        }
    }
}

解説

N=1の場合、間違った平均は0です。
N=2の場合、間違った平均は、1/2 か 2/2です。
N=3の場合、間違った平均は、3/3 から 5/3です。
N=4の場合、間違った平均は、6/4 から 9/4です。
下限も上限も、nに対して、単調増加なので

解候補のNの下限は二分探索できます。
解候補のNの上限も二分探索できます。

後は、Nの範囲を全探索し、
方程式
(N*(N+1)/2-A)/N = 入力の分数
を満たすAの十分性をチェックすれば良いです。

decimal型を使い、オーバフローに気をつけて実装してます。