Problem 255 めも

解いた．前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++ まともに勉強したことない．

コンテンツ