yukicoder 3624 Product

問題へのリンク

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");
            WillReturn.Add("1 4");
            WillReturn.Add("8 15");
            WillReturn.Add("45 123");
            WillReturn.Add("0 1000000000");
            //12
            //-1
            //4032
            //288230375614840832
        }
        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();
    }

    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);
            long L = wkArr[0];
            long R = wkArr[1];
            long Answer = Solve(L, R);
            Console.WriteLine(Answer);
        }
    }

    static long Solve(long pL, long pR)
    {
        if (pL == 0 && pR == 0) return 0;

        string BinStrL = Convert.ToString(pL, 2);
        string BinStrR = Convert.ToString(pR, 2);

        int Length = Math.Max(BinStrL.Length, BinStrR.Length);

        BinStrL = BinStrL.PadLeft(Length, '0');
        BinStrR = BinStrL.PadLeft(Length, '0');

        if (BinStrL[0] == '1' && BinStrR[0] == '1') return -1;

        string NewBinStrL = "0";
        string NewBinStrR = "1";

        for (long I = 1; I <= Length - 1; I++) {
            NewBinStrL += 1;
            NewBinStrR += 0;
        }

        long LongValL = Convert.ToInt64(NewBinStrL, 2);
        long LongValR = Convert.ToInt64(NewBinStrR, 2);

        return LongValL * LongValR;
    }
}

解説

まず、LとRが0の場合、解は0になります。

LとRが、両方0より大きい場合を考えます。
2進数で考えると、場合分けができます。
最大長に合わせて、0を左パディングします。

場合1
下限が 1XXX
上限が 1XXX
これは、必ずBitAndが1以上になるので、解は-1です。

場合2
下限が 0XXX
上限が 1XXX
0XXXが範囲下限の場合、最大上界である
0111は必ず使用できます。

下限が 0XXX
上限が 1XXX
1XXXが範囲上限の場合、最小下界である
1000は必ず使用できます。

そして、BitAndを0、かつ、積は最大化したいので
0111と1000のペアが最適解となります。