王女様のジェムストリング問題

結城浩さんによるCodeIQ用問題から。

http://www.hyuki.com/codeiq/

```csharp:Program.cs
using System;
using System.Diagnostics;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        var gems = new[] { 1, 4, 1, 4, 2, 1, 3 };
        var pattern = "eagcdfbe".Select(x => x - 'a').ToArray();
        var day = Day(gems, pattern);
        Console.WriteLine(day);
    }

    /// <summary>
    /// 使える宝石の一覧が与えられているときに、
    /// 指定したパターンが何日目に登場するかを返します。
    /// </summary>
    /// <param name="gems">
    /// 使える宝石の一覧を表すint配列。
    /// <c>gems[0]</c>が宝石aの数、<c>gems[1]</c>が宝石bの数、というように対応します。
    /// たとえば、使える宝石の例が "aaabcc" だった場合は、
    /// <c>{ 3, 1, 2 }</c>という配列で表現します。
    /// </param>
    /// <param name="pattern">
    /// 宝石パターンを指定するint配列。
    /// 宝石aは0、宝石bは1、というように対応します。
    /// たとえば、"aabac"というパターンは、<c>{ 0, 0, 1, 0, 2 }</c>という配列で表現します。
    /// </param>
    /// <returns>
    /// 指定したパターンの登場日。
    /// 指定したパターンを作ることができない場合は、その直前にあたる、可能なパターンの登場日。
    /// </returns>
    static long Day(int[] gems, int[] pattern)
    {
        const int gem_A = 0;
        var sum = 0L;
        var memo = Array.CreateInstance(typeof(long?),
                                        gems.Select(x => x + 1).ToArray());

        for (var i = 0; i < pattern.Length; i++)
        {
            var currentPattern = new int[i + 1];
            Array.Copy(pattern, currentPattern, i);
            var gem_i = pattern[i];
            for (var gem_j = gem_A; gem_j <= gem_i; gem_j++)
            {
                currentPattern[i] = gem_j;
                var rest = Take(gems, currentPattern);
                if (rest == null) continue;
                sum++;
                DebugWrite(currentPattern);
                if (gem_j < gem_i)
                {
                    var count = Combination(rest, memo);
                    sum += count;
                    DebugWrite(currentPattern, rest, count);
                }
            }
        }
        return sum;
    }

    /// <summary>
    /// 使える宝石の一覧から、指定したパターンを並べるために宝石を取り出した場合に、
    /// 残った宝石の一覧を返します。
    /// </summary>
    /// <param name="gems">
    /// 使える宝石の一覧を表すint配列。
    /// <c>gems[0]</c>が宝石aの数、<c>gems[1]</c>が宝石bの数、というように対応します。
    /// </param>
    /// <param name="pattern">
    /// 宝石パターンを指定するint配列。
    /// 宝石aは0、宝石bは1、というように対応します。
    /// </param>
    /// <returns>
    /// 残った宝石の一覧を表すint配列。
    /// <c>gems[0]</c>が宝石aの数、<c>gems[1]</c>が宝石bの数、というように対応します。
    /// 指定したパターンを作ることができない場合は<c>null</c>を返します。
    /// </returns>
    static int[] Take(int[] gems, int[] pattern)
    {
        var rest = (int[])gems.Clone();
        for (var i = 0; i < pattern.Length; i++)
        {
            if (rest[pattern[i]] == 0) return null;
            rest[pattern[i]]--;
        }
        return rest;
    }

    /// <summary>
    /// 使える宝石の一覧から、その一部を取り出したときに、
    /// 取り出した宝石によって作ることができる宝石パターンが何通りあるか、数え上げて返します。
    /// </summary>
    /// <param name="gems">
    /// 使える宝石の一覧から取り出した宝石を表すint配列。
    /// <c>gems[0]</c>が宝石aの数、<c>gems[1]</c>が宝石bの数、というように対応します。
    /// たとえば、使える宝石の例が "aaabcc" の時に、aを2つ、bを1つ取り出した場合は、
    /// <c>{ 2, 1, 0 }</c>という配列で表現します。
    /// </param>
    /// <param name="memo">
    /// 取り出した宝石と、それによって作ることができる宝石パターンの数の対応表をメモしたもの。
    /// <c>long?</c>型の多次元配列で、
    /// 次元数（ランク）は使える宝石の種類の数と一致している必要があります。
    /// たとえば、使える宝石の例が "aaabcc" の時に、
    /// aを2つ、bを1つ取り出した場合の宝石パターンの数は、
    /// このメソッドで計算された後、<c>memo[2, 1, 0]</c>にメモされます。
    /// </param>
    /// <returns>
    /// 取り出した宝石によって作ることができる宝石パターンの数。
    /// </returns>
    static long Combination(int[] gems, Array memo)
    {
        var count = (long?)memo.GetValue(gems);
        if (count.HasValue) return count.Value;
        count = 0L;
        for (var i = 0; i < gems.Length; i++)
        {
            if (gems[i] == 0) continue;
            var rest = (int[])gems.Clone();
            rest[i]--;
            count += 1L + Combination(rest, memo);
        }
        memo.SetValue(count, gems);
        return count.Value;
    }

    [Conditional("DEBUG")]
    static void DebugWrite(int[] pattern)
    {
        var patternString = new string(
            pattern.Select(x => Convert.ToChar('a' + x)).ToArray());
        Console.WriteLine(patternString + " -> 1通り");
    }

    [Conditional("DEBUG")]
    static void DebugWrite(int[] pattern, int[] rest, long count)
    {
        var patternString = new string(
            pattern.Select(x => Convert.ToChar('a' + x)).ToArray());
        var restString = string.Join(",", rest);
        Console.WriteLine(patternString
                          + "* -> Combination(" + restString + ") = "
                          + count + "通り");
    }
}
```