fix(cxx): Fix a bug of MoveSemantics

[kmyk]

154 のトップのコメント (https://github.com/kmyk/Jikka/issues/154#issue-961817489) の変換は直った。でも #153 のフィボナッチ数列のコード + mod はまだ動かない

cc @riantkb

[kmyk]

別のバグが埋まってテストが落ちてる……

[kmyk]

こんどは仕事しなさすぎて計算量が上がって TLE してる

input: examples/dp_b.py

# https://atcoder.jp/contests/dp/tasks/dp_b
from typing import *

INF = 10 ** 18

def solve(n: int, k: int, h: List[int]) -> int:
    assert 2 <= n <= 10 ** 5
    assert 1 <= k <= 100
    assert len(h) == n
    assert all(1 <= h_i <= 10 ** 4 for h_i in h)

    dp = [INF for _ in range(n)]
    dp[0] = 0
    for i in range(1, n):
        for j in range(max(0, i - k), i):
            dp[i] = min(dp[i], dp[j] + abs(h[i] - h[j]))
    return dp[n - 1]

def main() -> None:
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    assert len(h) == n
    ans = solve(n, k, h)
    print(ans)

if __name__ == '__main__':
    main()

output:

int64_t solve(int64_t n_0, int64_t k_1, std::vector<int64_t> h_2) {
    assert (- n_0 + 2 <= 0 and n_0 - 100000 <= 0);
    assert (- k_1 + 1 <= 0 and k_1 - 100 <= 0);
    assert (- n_0 + int64_t(h_2.size()) == 0);
    std::vector<bool> x3(h_2.size());
    for (int32_t i4 = 0; i4 < int32_t(h_2.size()); ++ i4) {
        x3[i4] = - h_2[i4] + 1 <= 0 and h_2[i4] - 10000 <= 0;
    }
    bool x6 = std::find(x3.begin(), x3.end(), false) == x3.end();
    assert (x6);
    std::vector<int64_t> x7(n_0, 1000000000000000000ll);
    x7[0] = 0;
    for (int32_t x10 = 0; x10 < n_0 - 1; ++ x10) {
        for (int32_t x14 = 0; x14 < x10 - std::max<int64_t>(0, x10 - k_1 + 1) + 1; ++ x14) {
            std::vector<int64_t> x17 = x7;
            x17[x10 + 1] = std::min<int64_t>(x7[x10 + 1], std::max<int64_t>(h_2[x10 + 1] - h_2[x14 + std::max<int64_t>(0, x10 - k_1 + 1)], - h_2[x10 + 1] + h_2[x14 + std::max<int64_t>(0, x10 - k_1 + 1)]) + x7[x14 + std::max<int64_t>(0, x10 - k_1 + 1)]);
            x7 = x17;
        }
    }
    return x7[n_0 - 1];
}

[kmyk]

たとえば

vector<int> func(vector<int> a) {
    for (int i = 0; i < n - 1; ++ i) {
        vector<int> b = a;
        b[i + 1] = a[i];
        a = b;
    }
    return a;
}

を

vector<int> func(vector<int> a) {
    for (int i = 0; i < n - 1; ++ i) {
        a[i + 1] = a[i];
    }
    return a;
}

に変換しないとだめなのだけど、これ無理じゃない？ core から C++ への変換のときに情報が落ちてしまってて、その状態で添字の解析をやるのはしんどすぎるし、ある程度はやれたとしても不可能ケースが残ってしまう。 UnpackTuples.hs や MoveSemantics.hs の中身をすべて ToCore.hs に埋め込んで、core から C++ への変換のときにすべてを同時に最適にやるしかなさそう