ARC172-A Chocolate

問題へのリンク

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 4 4");
            WillReturn.Add("1 0 0 1");
            //Yes
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5 7 6");
            WillReturn.Add("0 1 0 2 0 1");
            //Yes
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("3 2 7");
            WillReturn.Add("0 0 0 0 0 0 0");
            //No
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("11 11 2");
            WillReturn.Add("2 3");
            //No
        }
        else if (InputPattern == "Input5") {
            WillReturn.Add("777 777 6");
            WillReturn.Add("8 6 9 1 2 0");
            //Yes
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct RectDef
    {
        internal long Width;
        internal long Height;
    }

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

        long[] AArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        for (long I = 0; I <= AArr.GetUpperBound(0); I++) {
            AArr[I] = (long)(1 << (int)AArr[I]);
        }
        AArr = AArr.OrderByDescending(pX => pX).ToArray();

        var RectList = new List<RectDef>();
        RectDef WillAdd;
        WillAdd.Width = W;
        WillAdd.Height = H;
        RectList.Add(WillAdd);

        foreach (long EachA in AArr) {
            bool IsOK = false;
            for (int I = 0; I <= RectList.Count - 1; I++) {
                RectDef CurrRect = RectList[I];
                if (CurrRect.Width < EachA) continue;
                if (CurrRect.Height < EachA) continue;

                var AddRectList = new List<RectDef>();
                Action AddAct = () =>
                {
                    long RestWidth = CurrRect.Width - EachA;
                    long RestHeight = CurrRect.Height - EachA;

                    if (RestWidth == 0 && RestHeight == 0) return;

                    if (RestWidth > 0 && RestHeight == 0) {
                        WillAdd.Width = RestWidth;
                        WillAdd.Height = EachA;
                        RectList.Add(WillAdd);
                        return;
                    }

                    if (RestWidth == 0 && RestHeight > 0) {
                        WillAdd.Width = EachA;
                        WillAdd.Height = RestHeight;
                        RectList.Add(WillAdd);
                        return;
                    }

                    if (RestWidth >= RestHeight) {
                        // 右の分を追加
                        WillAdd.Width = RestWidth;
                        WillAdd.Height = CurrRect.Height;
                        RectList.Add(WillAdd);

                        // 下の分を追加
                        WillAdd.Width = EachA;
                        WillAdd.Height = RestHeight;
                        RectList.Add(WillAdd);
                    }
                    else {
                        // 下の分を追加
                        WillAdd.Width = CurrRect.Width;
                        WillAdd.Height = RestHeight;
                        RectList.Add(WillAdd);

                        // 右の分を追加
                        WillAdd.Width = RestWidth;
                        WillAdd.Height = EachA;
                        RectList.Add(WillAdd);
                    }
                };
                AddAct();

                IsOK = true;
                RectList.RemoveAt(I);
                RectList.AddRange(AddRectList);
                break;
            }
            if (IsOK == false) {
                Console.WriteLine("No");
                return;
            }
        }
        Console.WriteLine("Yes");
    }
}

解説

正方形の大きさの降順に敷き詰めます。
敷き詰める場合は、必ず長方形の左上から敷き詰めます。
正方形を敷き詰めるので、
残ったピースは、長方形のListで管理します。

下記のように
3*3の正方形を敷き詰めたら、
長さが3でないほうの辺の長いほう(この場合はＢの長方形)が
Ｃの長方形を持つようにします。
こうしないと、2*2の正方形の敷き詰め可能数が減ってしまうので

■■■Ａ
■■■Ａ
■■■Ａ
ＢＢＢＣ
ＢＢＢＣ