ARC224-B Adjacent Tiles

問題へのリンク

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("1");
            WillReturn.Add("2");
            WillReturn.Add("3");
            WillReturn.Add("4");
            WillReturn.Add("100000000000000000");
            WillReturn.Add("1000000000000000000");
            //0
            //1
            //2
            //4
            //199999999367544467
            //1999999998000000000
        }
        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();
        for (int I = 1; I <= InputList.Count - 1; I++) {
            long N = long.Parse(InputList[I]);
            long Answer = Solve(N);
            Console.WriteLine(Answer);
        }
    }

    static long Solve(long pN)
    {
        if (pN == 1) return 0;
        if (pN == 2) return 1;
        if (pN == 3) return 2;
        if (pN == 4) return 4;

        long L = 0;
        long R = pN;
        long AnswerSum = 0;
        while (L + 1 < R) {
            long Mid = (L + R) / 2;

            long Sum;
            if (CanAchieve(pN, Mid, out Sum)) {
                AnswerSum = Sum;
                L = Mid;
            }
            else {
                R = Mid;
            }
        }
        return AnswerSum;
    }

    // 2をX個以上作成可能か？
    // 作成可能なら解候補をpSumに設定
    static bool CanAchieve(long pN, long pX, out long pSum)
    {
        pSum = 0;
        long Rest = pN - pX;
        if (Rest <= 3) return false;

        // 0の分を引く
        Rest--;

        long Yoko;
        long Tate;

        if (Rest % 2 == 0) {
            Yoko = Rest / 2;
            Tate = Rest / 2;
        }
        else {
            Yoko = Rest / 2;
            Tate = Rest - Yoko;
        }

        if (WillOverProd(Yoko, Tate, long.MaxValue) || Yoko * Tate >= pX) {
            // 1の数
            long CntOne = Yoko + Tate;
            
            // 2の数
            long CntTwo = pX;

            pSum = CntOne + CntTwo * 2;
            return true;
        }
        return false;
    }

    // long型の2正数の掛け算が、Limitを超えるかを返す
    static bool WillOverProd(long pA, long pB, long pLimit)
    {
        return pA > pLimit / pB;
    }
}

解説

対称性より、
左か下のみに伸ばせるとしても、解は変わらないです。

なので
0111
1222
1222
1222
のような寄与度の図で、2をたくさん作るのが最適です。

そして、作る2の数を決めたら、
残った中で0と1を作ることになり、
横の長さと、縦の長さの和が決まった状態で、
作成可能な最大面積の長方形を考える問題となり、
これは、横の長さと縦の長さの差を最小化するのが最適です。

以上により、作る2の数を二分探索して解くことができます。