FindSeedByBlink_ver_3

FindSeedByBlink_ver_3.cs

// 一部を修正. 一部と言いつつかなりクリティカルな部分.
public static IEnumerable<uint> FindCurrentSeedByBlink_Old2(uint seed, uint minIndex, uint maxIndex, int[] blinkInput, int allowanceLimitOfError = 20, int coolTime = 4)
{
    var res = new List<uint>();

    seed.Advance(minIndex);
    blinkInput = blinkInput.Select(_ => _ - (5 + coolTime)).ToArray(); // 瞬き後のクールタイム分を引く.

    var n = maxIndex - minIndex + 1;

    // i = maxまで計算できるように, 全て最大間隔で瞬きが行われた場合でも足りるだけ余分に計算しておく.
    var len = (int)n + 85 * (blinkInput.Length + 2);

    // 「到達したときに瞬きをするような内部カウンタの値」の最小値に変換する.
    // FindIndexは計算量O(N)かかるが, UpperBoundならO(logN)で済む.
    // 今回はN=86なのでlog(86)≈6.4. かなり差が出るはず. (単純に86/6.4ではないけれど)
    var countList = seed.EnumerateRand().Take(len + 1).Select(_ => BlinkConst.blinkThresholds_even.UpperBound(_)).ToArray();

    // 「その位置で瞬きをした場合の, 次の瞬きまでの間隔」.
    // ここが定数倍大きいのでちょっと辛い.
    var blankList = Enumerable.Repeat(86, len).ToArray(); // 86 = INF
    for (int i = len - 1; i >= 0; i--) // 後ろから埋めていく. 確率的にcountListは大きい値が多く, 特に85になる確率が高い.
        for (int k = countList[i]; k <= Math.Min(i, 85); k++) // kは『到達したときに瞬きするような内部カウンタの最小値』から85まで(境界を超えないように).
            blankList[i - k] = Math.Min(blankList[i - k], k); // kの定義より, i-kで瞬きをしたら, 次は少なくともiで瞬きが発生する.

    // 『iフレーム目に1回目の瞬きが行われた』と仮定してシミュレート.
    for (int i = 0; i < n; i++)
    {
        int idx = i;
        int k;
        for (k = 0; k < blinkInput.Length; k++)
        {
            // 許容誤差を超えているなら次のフレームへ.
            if ((blinkInput[k] + allowanceLimitOfError) < blankList[idx] || blankList[idx] < (blinkInput[k] - allowanceLimitOfError)) break;

            // 間隔ぶんをindexに加算する.
            idx += blankList[idx] + 1;
        }

        // 入力と全て一致すればresに入れる.
        if (k == blinkInput.Length) res.Add((uint)idx);
    }

    return res.Distinct().Select(_ => seed.NextSeed(_));
}