TopCoder SRM 589: FlippingBitsDiv2

問題文

メモ付き探索する場合は、Nullableの配列を使うと初期化する必要がなくなるので楽

メモ配列へのアクセスに Array.SetValue/GetValue を使うようにすると、メモ化に使うパラメタに破壊的代入してもバグらなくなる。追記：ただし、非常に速度が遅いので取り扱い注意

public class FlippingBitsDiv2 {
    int?[,,] memo;

    public int solve(string S, int M, int k, bool allFlip = false, bool lastFlip = false)
    {
        if (k * M == S.Length)
        {
            if (allFlip) return 0;
            if (lastFlip) return -1;
            return 0;
        }
        var key = new long[] { k, allFlip ? 1 : 0, lastFlip ? 1 : 0 };
        var memoised = (int?)memo.GetValue(key);
        if (memoised.HasValue)
            return memoised.Value;
        int ret = int.MaxValue;
        int bitNum = S.Where((c,index) => k * M <= index && index < (k+1) * M && c == '1').Count();
        if (k == 0)
        {
            ret = Math.Min(ret, solve(S, M, k + 1, false, false) + M - bitNum);
            ret = Math.Min(ret, solve(S, M, k + 1, true, true) + bitNum + 1);
        }
        else
        {
            ret = Math.Min(ret, solve(S, M, k + 1, false, false) + M - bitNum);
            ret = Math.Min(ret, solve(S, M, k + 1, allFlip, true) + bitNum + (lastFlip ? 0 : 2));
        }
        memo.SetValue(ret, key);
        return ret;
    }

    public int getmin(string[] _S, int M)
    {
        string S = String.Concat(_S);
        memo = new int?[S.Length / M, 2, 2];
        return solve(S, M, 0) ;
    }
}