Cマガ電脳クラブ(第085回) 省メモリものさし

問題

Fig.1のような、変な目盛の入ったものさしがある(数値は左端からの長さを表す) 。
実はこのものさし、目盛が4か所(両端を含む) にしかないのに、1〜6センチのすべての長さを測ることができる。
 1=1-0､2=6-4､3=4-1､4=4-0､5=6-1､6=6-0

このように、「1センチから全体の長さまで1センチ単位ですべての長さを測ることができるものさし」は、
目盛が4か所の場合この6センチが最長である。同様にして目盛が5か所の場合には、9センチが最長となる(Fig.2) 。
このとき、3センチに2通りの測り方があるが、
それぞれの長さが少なくとも1通りで測ることができればよいので、OKとする。

さて、ここで問題。目盛を9か所に入れるとしたとき、上記条件を満たすものさしは最長何センチだろうか

Fig.1 目盛が4か所のものさし


Fig.2 目盛が5か所のものさし

ソース

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var sw = System.Diagnostics.Stopwatch.StartNew();

        DeriveMaxCenti(4);
        DeriveMaxCenti(5);
        DeriveMaxCenti(9);

        Console.WriteLine("経過時間={0}", sw.Elapsed);
    }

    //目盛数を引数として、何センチまで測れるかを調べる
    static void DeriveMaxCenti(int pMemoriCnt)
    {
        Console.WriteLine(new string('■', 30));
        Console.WriteLine("目盛数={0}で何センチまで測れるかを調べます", pMemoriCnt);

        //pMemoriCnt C 2 が可能な組み合わせなので、最大でもその長さまでしか測れない
        int LimitI = pMemoriCnt * (pMemoriCnt - 1) / 2;

        //右端の目盛でループ
        for (int I = pMemoriCnt - 1; I <= LimitI; I++) {
            IEnumerable<int[]> KouhoArrEnum = DeriveKouhoArrList(pMemoriCnt, I);
            Console.WriteLine("右端の目盛={0}で解を調査中", I);

            foreach (int[] EachKouhoArr in KouhoArrEnum) {
                if (IsValidKouhoArr(EachKouhoArr, I)) {
                    Console.Write("目盛");
                    Array.ForEach(EachKouhoArr, X => Console.Write("{0},", X));
                    Console.WriteLine("で1から{0}まで測れます。", I);
                    break;
                }
            }
        }
    }

    struct JyoutaiDef
    {
        internal int MemoriCnt;
        internal int CurrMemori;
        internal List<int> KouhoList;
    }

    //目盛数と、右端の目盛を引数とし、他の目盛の候補のListを返す
    static IEnumerable<int[]> DeriveKouhoArrList(int pMemoriCnt, int pMigihajiMemori)
    {
        var WillReturn = new List<int[]>();

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.MemoriCnt = 1;
        WillPush.CurrMemori = 0;
        WillPush.KouhoList = new List<int>() { 0 };
        stk.Push(WillPush);

        while (stk.Count > 0) {
            JyoutaiDef Popped = stk.Pop();

            //クリア判定
            if (Popped.MemoriCnt + 1 == pMemoriCnt) {
                Popped.KouhoList.Add(pMigihajiMemori);
                yield return Popped.KouhoList.ToArray();
                continue;
            }

            for (int I = Popped.CurrMemori + 1; I <= pMigihajiMemori - 1; I++) {
                WillPush.MemoriCnt = Popped.MemoriCnt + 1;
                WillPush.CurrMemori = I;
                WillPush.KouhoList = new List<int>(Popped.KouhoList) { I };
                stk.Push(WillPush);
            }
        }
    }

    //1センチから全体の長さまで測れるかを判定
    static bool IsValidKouhoArr(int[] pKouhoArr, int pMigihajiMemori)
    {
        bool[] CanKeisokuArr = new bool[pMigihajiMemori + 1];
        for (int I = 0; I <= pKouhoArr.GetUpperBound(0) - 1; I++) {
            for (int J = I + 1; J <= pKouhoArr.GetUpperBound(0); J++) {
                int wkInd = pKouhoArr[J] - pKouhoArr[I];
                CanKeisokuArr[wkInd] = true;
            }
        }
        return Array.FindIndex(CanKeisokuArr, 1, X => X == false) < 0;
    }
}

実行結果

省略
右端の目盛=28で解を調査中
目盛0,2,4,6,7,18,19,27,28,で1から28まで測れます。
右端の目盛=29で解を調査中
目盛0,2,5,8,11,15,27,28,29,で1から29まで測れます。
右端の目盛=30で解を調査中
右端の目盛=31で解を調査中
右端の目盛=32で解を調査中
右端の目盛=33で解を調査中
右端の目盛=34で解を調査中
右端の目盛=35で解を調査中
右端の目盛=36で解を調査中
経過時間=00:01:32.6602386

解説

目盛が9箇所なので、1から最大でも9C2までの長さを測ることができます。
よって、9*8/2=36をループの上限としてます。