急勾配の判定
Posted feedbacks - D
与えられたrangeの急勾配性を判定します．
rangeが後ろから手繰れる場合はO(n) time, O(1) space，そうでない場合はO(n) time, O(n) spaceです．
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | module doukaku248;
import std.algorithm, std.array, std.range, std.traits;
bool isSteep(Range)(Range r) if(isInputRange!(Range)) {
static if(isInfinite!(Range)) {
static assert(false, "steepness of infinite ranges cannot be determined.");
} else static if(isBidirectionalRange!(Range)) {
if(!r.empty) {
auto sum = r.back;
r.popBack;
foreach_reverse(e; r) {
if(e <= sum)
return false;
sum += e;
}
}
return true;
} else {
return isSteep(toArray(r));
}
}
ElementType!(Range)[] toArray(Range)(Range r) if(isInputRange!(Range)) {
static if(isImplicitlyConvertible!(Range, typeof(return))) {
return r;
} else static if(isInfinite!(Range)) {
static assert(false, "infinite ranges cannot be converted to arrays.");
} else {
typeof(return) a;
static if(isForwardRange!(Range)) {
a.length = walkLength(r);
size_t i = 0;
foreach(e; r) {
a[i++] = e;
}
} else {
foreach(e; r) {
a ~= e;
}
}
return a;
}
}
|
nobsun
#8891()
Rating1/1=1.00
有限の長さの数列で，各要素の値が，その要素の後ろにある残りの列に含まれるすべての要素の和よりも大きい列を「急勾配の列」ということにします（空列の和は0とします）．
任意の長さ（ただし有限の長さの）数列を与えられたとき，それが「急勾配の列」であるかどうかを判定する述語関数を定義してください．
必須ではありませんが，効率についてコメントがあれば面白いかもしれませんね．
[ reply ]