Problem 255 めも

Problem 255 – Project Euler

解いた.前2問に比べると簡単だと思う(もう内容忘れかけているが).

はじめにHaskellで解いたら,実行時間は3分ぐらいだった.

再帰を使おうとしたら,stack space overflow.

seq入れてみたり,!入れてみたりして,stack space overflowを解消したら,30秒位で走った.

しかし,30秒は遅い.しかも,少し前まで,stack space overflowになっていた.

自分としては,stack space overflowになるような覚えはないし,実は,なんで解消されたかも良く分からない.

ということで,C++で同じアルゴリズムを実装してみたら,約10倍速くなった.

うーん,Haskellでも速く書けないのかなぁ.

あと,C++で (ちなみに, typedef long long ll; してあります).

inline void count(ll s, ll t, ll x, ll& c) {
// 中略
if (x != y) count(s, u, y, c);
count(u + 1, t, x, c);
c += u - s + 1;
}

としたら,segmentation faultで

inline void count(ll s, ll t, ll x, ll& c) {
// 中略
c += u - s + 1;
if (x != y) count(s, u, y, c);
count(u + 1, t, x, c);
}

としたら,segmentation faultはでなかった.たしかに,若干危険な感じはするが.

何が原因なんでしょう?

# 実は C++ まともに勉強したことない.