ABC349-D Divide Interval

問題へのリンク

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 19");
            //5
            //3 4
            //4 8
            //8 16
            //16 18
            //18 19
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("0 1024");
            //1
            //0 1024
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("3940649673945088 11549545024454656");
            //8
            //3940649673945088 3940649673949184
            //3940649673949184 4503599627370496
            //4503599627370496 9007199254740992
            //9007199254740992 11258999068426240
            //11258999068426240 11540474045136896
            //11540474045136896 11549270138159104
            //11549270138159104 11549545016066048
            //11549545016066048 11549545024454656
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        long L = wkArr[0];
        long R = wkArr[1];

        // 2べきのList
        var Beki2List = new List<long>();
        long Beki2Val = 1;
        while (Beki2Val <= R) {
            Beki2List.Add(Beki2Val);
            Beki2Val *= 2;
        }
        Beki2List.Reverse(); // 降順にしておく

        var AnswerList = new List<string>();
        long CurrL = L;
        while (CurrL < R) {
            foreach (long EachBeki2 in Beki2List) {
                if (CurrL % EachBeki2 > 0) continue;
                long CurrR = CurrL + EachBeki2;
                if (CurrR > R) continue;

                AnswerList.Add(string.Format("{0} {1}", CurrL, CurrR));
                CurrL = CurrR;
                break;
            }
        }

        Console.WriteLine(AnswerList.Count);
        AnswerList.ForEach(pX => Console.WriteLine(pX));
    }
}

解説

最初に2べきな数のListを求めます。
次に、なるべく長い区間を貪欲に設定してます。