DouKaku?beta

challenge 急勾配の判定

有限の長さの数列で，各要素の値が，その要素の後ろにある残りの列に含まれるすべての要素の和よりも大きい列を「急勾配の列」ということにします（空列の和は0とします）．

任意の長さ（ただし有限の長さの）数列を与えられたとき，それが「急勾配の列」であるかどうかを判定する述語関数を定義してください．

必須ではありませんが，効率についてコメントがあれば面白いかもしれませんね．

post comment

Posted feedbacks - Nested

Flatten Hidden

数列の長さに対して線形時間です。

1
2
3
4
(defun rapidly-decreasing-p (numbers)
  (loop for sum = (reduce #'+ (cdr numbers)) then (- sum x)
     for x in numbers
     always (< sum x)))

超増加列の反転かどうかを判定すればいいので、線形時間で出来ました。

1
2
3
4
5
6
7
(define (super-decreasing? lis)
  (let1 l (reverse lis)
        (let loop ((l l) (s 0))
          (cond ((null? l) #t)
                ((> (car l) s)
                 (loop (cdr l) (+ s (car l))))
                (else #f)))))

OCaml学習中。

1
2
3
4
5
let rec super_inc n lst = match lst with
    []     -> true
  | a::rst -> if n < a then (super_inc (n+a) rst) else false

let super_dec lst = f 0 (List.rev lst)

訂正。super_dec関数内で呼び出す関数名が間違ってました。 あと、計算量は O(n)です。

1
2
3
4
5
let rec super_inc n lst = match lst with
    []     -> true
  | a::rst -> if n < a then (super_inc (n+a) rst) else false;;

let super_dec lst = super_inc 0 (List.rev lst);;

$ が多くてうっとうしいけど。

1
2
3
import List

steep xs = and $ zipWith (>) xs $ map sum $ tail $ tails xs

1
isSteelyList xs = and $ zipWith (>) xs $ tail $ scanl (-) (sum xs) xs

Squeak Smalltalk で。

 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
"ナイーブに"
| 急勾配か？ |

急勾配か？ := [:配列 |
    (1 to: 配列 size - 1) allSatisfy: [:順 | (配列 at: 順) > (配列 allButFirst: 順) sum]].

急勾配か？ value: #().    "=> true "
急勾配か？ value: #(1).   "=> true "
急勾配か？ value: #(0).   "=> true "
急勾配か？ value: #(32 16 8 4 2 1).   "=> true "
急勾配か？ value: #(32 15 8 4 2 1).   "=> false "


"効率に配慮して"
| 急勾配か？ |

急勾配か？ := [:配列 |
    [:exit |
        (配列 size to: 1 by: -1) inject: 0 into: [:和 :順 |
            | 要素 |
            要素 := 配列 at: 順.
            要素 > 和 ifFalse: [exit value]. 和 + 要素]
    ] valueWithExit notNil].

急勾配か？ value: #().    "=> true "
急勾配か？ value: #(1).   "=> true "
急勾配か？ value: #(0).   "=> false "
急勾配か？ value: #(32 16 8 4 2 1).   "=> true "
急勾配か？ value: #(32 15 8 4 2 1).   "=> false "

コードは素直に書いてみました。たぶんO(n)のはず。OO的述語関数の表現としてbooleanの読み取り専用プロパティにしてみました。

動作確認は以下のようにしています。

>|groovy|

assert [].is急勾配()

assert [0].is急勾配()

assert [1,0].is急勾配()

assert ! [0,1].is急勾配()

assert [4,2,1].is急勾配()

assert ! [3,2,1].is急勾配()

||< 

1
2
3
4
5
List.metaClass.is急勾配 = {->
    delegate.size() <= 1?
        true:
        delegate[1..-1].is急勾配() && delegate[1..-1].sum() < delegate[0]
}

違った。毎回sum()してるから自乗オーダーでした。 もうちょっと手を入れなきゃ。

とりあえず急勾配な場合でもO(n)。かっこわるいです。 一般的にはもっと良いはず。ランダムな数列において後ろから見たときに急勾配の条件に合わない値が出てくる確率ってどのくらいなんでしょう。（考えるのめんどくさい）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
List.metaClass.is急勾配 {->
    def sum
    for (val in delegate.reverse()) {
        if (sum != null && val <= sum) {
            return false
        }
        sum = (sum?:0) + val
    }
    return true
}
効率は悪くないと思うけど、工夫はしてません。

仕様面ではっきりしないのは、
１．空リストは急勾配？ not 急勾配？
２．問題文の「空列の和は0とします」をどう読むか。
　　[0] は 0 + 空列  なので、not 急勾配になる？
　　（sum の初期値を 0 とするか -∞ にするかというだけの話だけど） 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
Array.prototype.isHeavySlope = function() {
  var sum = 0;
  for (var i = this.length-1; i >= 0; i--) {
    if (this[i] <= sum) return false;
    sum += this[i];
  }
  return true;
}

>>> [].isHeavySlope()
true
>>> [0].isHeavySlope()
false
>>> [1,0].isHeavySlope()
false
>>> [0,1].isHeavySlope()
false
>>> [4,2,1].isHeavySlope()
true
>>> [3,2,1].isHeavySlope()
false
sumの初期値を -∞ にしたらだめじゃん。勘違いです。忘れてください。
てことは [0] は急勾配じゃないということでFA?
リストを前から見ていくこともできます。
後ろから見るほうがシンプルだけど、リストの長さが未確定の場合はこちらが有利。
ちなみに [1,0].isHeavySlope() は true になりますが何か？ 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
Array.prototype.isHeavySlope = function() {
    if (this.length == 0) return true;
    var pre, sub;
    for each (var n in this) {
        if (pre == undefined) {
            sub = pre = n;
        } else {
            sub -= n;
            if (pre <= n || sub <= 0) return false;
            pre = n;
        }
    }
    return true;
}

O(n)ですね。速くなりませんかね？ でも、どうせ全部チェックしなきゃいけないんだから、O(n)が最速でしょうね。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
using System;
static class P
{
    static void Main(string[] args)
    {
        int[] array = { 1, 2, 7, 11, 25 };
        Console.WriteLine("急勾配で{0}", IsAggressive(array) ? "す" : "はありません");
    }
    static bool IsAggressive(int[] array)
    {
        int sum = 0;
        for (int i = 0; i < array.Length; i++)
        {
            if (sum >= array[i])
                return false;
            else
                sum += array[i];
        }
        return true;
    }
}

　効率優先で。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
object SteepAngle {
    def isSteep(l:List[Int]):Boolean = l match {
            case List() => true
            case _ => {
                def loop(s:Int, r:List[Int]):Boolean = r match {
                        case List() => true
                        case x::xs if x > s => loop(s + x, xs)
                        case _ => false
                    }
                loop(l.last, l.reverse.tail)
            }
        }
    def main(args:Array[String]):Unit =
        try {
            isSteep(args.toList.map(_.toInt)) match {
                case true => println("steep")
                case _ => println("not steep")
            }
        } catch {
            case e => println("usage: SteepAngle NUMBERS")
        }
}

　素直に書いてみました。

1
2
3
4
5
6
7
class SteepAngle
    def self.steep?(l)
        (l.size < 2) || (0...l.size - 1).all? { |i| l[i] > l[i + 1...l.size].inject(0) { |r,e| r + e } }
    end
end

puts SteepAngle.steep?(ARGV.map { |p| p.to_i }) ? "steep" : "not steep"

mapAccumの遅延評価が良くわかりませんが...

1
2
3
import Data.List (mapAccumR)

isSteep = and . snd . mapAccumR (\acc x -> (acc+x, x > acc)) 0

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
import Maybe

isKyukoubai xs = isJust $ foldr f (Just 0) xs  where
  f x b = do
    s <- b
    if (x > s) then Just (s+x) else Nothing
{-
> isKyukoubai [4,2,1]
True
> isKyukoubai [2,2,1]
False
> isKyukoubai [undefined,2,2,1]
False
-}
#8894を参考にさせて頂きました。 数列を反転後、合計値を先頭に書き込みながら大小比較をしています。 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def super_decreasing?(a)
  r = a.reverse
  while r[1] && (w = r[0] < r[1])
    r[1] += r[0]
    r.shift
  end
  w ? "yes. super_decreasing." : "not super_decreasing."
 end

p super_decreasing?([8, 4, 2, 1]) # => yes..
p super_decreasing?([8, 3, 2, 1]) # => not..
p super_decreasing?([1]) # => not..
p super_decreasing?([]) # => not..
p super_decreasing?([1, -4, -5]) # => yes..

Cで普通に。
O(n)です。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>

static int is_kyuukoubai(int* a, int num)
{
    int i;
    int sum=0;
    for(i=num-1; i>=0; i--)
    {
        if (a[i]<=sum) return 0;
        sum+=a[i];
    }
    return 1;
}

int main()
{
    int test[5] = { 20, 10, 5, 3, 1 };
    if (is_kyuukoubai(test, 5)) printf("kyuukoubai.\n");
    else printf("not kyuukoubai.\n");
    return 0;
}

foreachの方が分かりやすかったかも。 計算量はΘ(n)のはずです。

1
2
3
4
5
use List::MoreUtils qw/all/;
sub is_super_dec(@) {
  my $total = 0;
  all { ($_ > $total) and do { $total += $_; 1 } } reverse @_;
}

ありゃしまった、急勾配でなければもっと早く返るからO(n)ではあってもΘ(n)じゃないですね。

末尾再帰になってる？ 
1
2
3
4
5
6
7
isKyukoubai xs = f [] xs  where
  f ys (x:xs) = f (x:ys) xs
  f ys [] = g 0 ys
  g s (y:ys)
    | y > s     = g (s+y) ys
    | otherwise = False
  g _ [] = True

思いっきりナイーブに。

強いて特徴を言うなら，エラーチェックやオーバーフロー対策がしてあるくらい？

1
2
3
4
5
6
7
8
9
public static boolean isSteep(int[] nums) {
    if (nums == null || nums.length == 0) return false;
    long sum = 0L;
    for (int i = nums.length - 1; i >= 0; i--) {
        if (nums[i] <= sum) return false;
        sum += nums[i];
    }
    return true;
}

効率や末尾再帰や遅延評価や見易さやら考えてたら
#8896 の reverse版になりました。

1
2
isKyukoubai xs = and $ zipWith (>) ys $ scanl (+) 0 ys  where
  ys = reverse xs
計算量はO(n)ですが、リストを尻から舐めてくと多少は無駄な計算が抑えられるかなー、と。 
 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
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

template <typename T>
struct not_steep_slope {
  T sum_;
  not_steep_slope() : sum_(0) {}
  bool operator()(T v) {
    if (v <= sum_) return true;
    sum_+=v;
    return false;
  }
};

template <typename T>
bool is_steep_slope(const std::vector<T>& v) {
  return std::find_if(v.rbegin(), v.rend(), not_steep_slope<T>()) == v.rend();
}

template <typename T>
void check(const std::vector<T>& v) {
  std::cout << "(";
  std::copy(v.begin(), v.end(), std::ostream_iterator<T>(std::cout, ","));
  std::cout << ") => " << is_steep_slope(v) << "\n";
}

int main() {
  std::cout.setf( std::ios::boolalpha );

  std::vector<int> v;
  check(v);

  v.push_back(1);
  check(v);

  v.front() = 0;
  check(v);

  v.clear();
  v.push_back(32);
  v.push_back(16);
  v.push_back(8);
  v.push_back(4);
  v.push_back(2);
  v.push_back(1);
  check(v);

  v[1] = 15;
  check(v);

  return 0;
}

組み込み関数reversedのオーダは分かりませんが、少なくともそれ以外の部分は要素数について、線形時間です。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
#!/usr/bin/python

def checkSteep(target):
    li = reversed(target)
    sum = 0
    for x in li:
        if x <= sum: return False
        sum += x
    return True

if __name__ == '__main__':
    print 'Steep' if checkSteep([32, 16, 8, 4, 2, 1]) else 'not Steep' # => Steep
    print 'Steep' if checkSteep([32, 15, 8, 4, 2, 1]) else 'not Steep' # => not Steep

1
2
def super_decreasing(l):
    return all(l[i] > sum(l[i+1:]) for i in xrange(0, len(l)-1))

cumsum の結果をキャッシュしておけば線形になります。

1
is.superdecreasing <- function(l) all(l > rev(cumsum(rev(l)))-l)

1
2
3
sd([],_) :- !.
sd([X|Xs],S) :- X > S, S1 is S + X, sd(Xs,S1).
super_decreasing(Xs) :- reverse(Xs,Ys), sd(Ys,0).

累積値のリストをつくって元のリストと比較しているので
効率は良くないと思います。
   ]data1=: 2^i._15
16384 8192 4096 2048 1024 512 256 128 64 32 16 8 4 2 1
   ]data2=: 100(0)}2^i._15
100 8192 4096 2048 1024 512 256 128 64 32 16 8 4 2 1
   f data1
1
   f data2
0
1
f=:*/@(>(-~+/\.))

LINQを使って無難に判定。コレは 3n だから O(n)になるのかな。

Aggregateとかを使おうと思ったんですが、結局はsumを外出しにするのと、Selectで十分だと気づきました。

1
2
3
4
5
6
7
8
9
        static bool IsAggressive(int[] list)
        {
            int sum = list.Sum();
            return list.Reverse().Select(num =>
            {
                sum -= num;
                return sum - num;
            }).Any(num => num < 0);
        }
ほとんどOCaml互換。計算量はO(n)です。 
1
2
3
4
let isSteep ls =
    List.fold_right (fun x (result, sum) ->
        if result && x > sum then (true, sum + x) else (false, sum)
    ) ls (true, 0) |> fst

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
#! /usr/bin/ruby

class Array
    def steep?
        reverse.inject(0) do |sum, previous|
            return false unless previous > sum
            sum += previous
        end
        true
    end
end

p [5, 3, 2].steep?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
#!/usr/bin/perl
use strict;
use warnings;

sub is_steep_array{
    my @arr = reverse @_;
    my $sum = 0;
    $sum < $_ ? $sum += $_ : return () for @arr;
    1;
}
print 'true' if is_steep_array(9,4,2,1);

後ろから見ていくことで、効率的になっていますね。 pop使えば、reverseする手間も省けていいんじゃないかなーと思います。

1
2
3
4
sub isSteep2{
    my($x,$q) = 0;
    $x < ($q = pop||return 1) ? $x += $q : return 0 while 1;
}

#8973のボトルネックはreverseした値を配列にコピーしているところですね。

for(each)に直接渡すと最適化されるのでpopよりずっと速いです。以下ベンチマーク。 

 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
46
47
48
49
50
use Benchmark qw/cmpthese/;

my @steep = map { 2 ** $_ } reverse 0 .. 49;

cmpthese(100_000,
         { pop    => sub { is_steep0(@steep) },
           rev_cp => sub { is_steep1(@steep) },
           rev    => sub { is_steep2(@steep) },
           nk_pop => sub { is_steep3(@steep) },
           sk_rev => sub { is_steep4(@steep) } });

sub is_steep0 {
  my $total = 0;
  while (my $i = pop) {
    return unless $total < $i;
    $total += $i;
  }
  return 1;
}

sub is_steep1 {
  my $total = 0;
  my @rev = reverse @_;
  for my $i (@rev) {
    return unless $i > $total;
    $total += $i;
  }
  return 1;
}

sub is_steep2 {
  my $total = 0;
  for my $i (reverse @_) {
    return unless $i > $total;
    $total += $i;
  }
  return 1;
}

# http://ja.doukaku.org/comment/9251/
sub is_steep3 {
  my ($x,$q) = 0;
  $x < ($q = pop||return 1) ? $x += $q : return 0 while 1;
}

sub is_steep4 {
  my $total = 0;
  $total < $_ ? $total += $_ : return 0 for reverse @_;
  return 1;
}

SQL Server 2008 で確認しました。 SQL で関数というと、ストアドファンクションとかになると思うんですけど、入力に対して出力がありさえすれば関数と言うことで、SELECT オンリーで書いてみました。

肝心のロジック部分は、もっといいやり方はあると思います。 3段階SELECTがネストしてるんで、効率は・・・

 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
WITH
  Input(i, n) AS (
    SELECT 1, 100
    UNION ALL
    SELECT 2, 50
    UNION ALL
    SELECT 3, 10
  )
, HeavySlopes(col) AS (
    SELECT
        1
    FROM
        Input P
    WHERE
        EXISTS(
          SELECT * FROM Input C
          WHERE P.i < C.i AND P.n > (SELECT SUM(GC.n) FROM Input GC WHERE P.i < GC.i)
        )
  )
, IsHeavySlope(result) AS (
    SELECT
        CASE (SELECT COUNT(*) FROM Input)
        WHEN COUNT(*) + 1 THEN 1
                          ELSE 0
        END
    FROM
        HeavySlopes
  )
SELECT * FROM IsHeavySlope

畳み込みを使ったほうが綺麗ですが、Rubyの畳み込み(inject)は左から(foldl相当)なので、reverseする分重くなりそうですね。

というわけで、普通に実装してみました。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Array
  def steep?
    sum = 0
    (self.size - 2).downto(0) do |index|
      if self[index] <= (sum += self[index + 1])
        return false
      end
    end
    true
  end
end

p [100, 50, 25, 12, 6, 3, 1].steep?

与えられた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;
    }
}
再帰的に書いてみました。
計算量(という表現でいいかは別として、)は一律に要素数と一致するはず。たぶん。

Tabが一律4半角スペースなのでインデントがおかしいですけどそこはスルーでお願いします。 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
#!/usr/local/bin/perl
use strict;

sub isSteep{
    my $x = shift||return 1,0;
    my @y = isSteep(@_);
    return $y[0]&&$x>$y[1]?1:0,$y[1]+$x;
}

my @a1    = (\@{[100, 30, 10, 4, 1]},
      \@{[10, 30, 100]},
      \@{[10, 4, 2, 1]},
      \@{[10, 5, 4, 2]});

print join(', ',@{$_}),' is',((isSteep(@{$_}))[0]?'':'n\'t'),' a steep array.',$/ for@a1;

後ろから反復してみました。

 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
#module

#define true  1
#define false 0

#defcfunc IsSteepSlope array arr,  \
    local size, local nowSum, local bResult
    
    size    = length(arr)
    nowSum  = 0
    bResult = true
    
    repeat size, 1
        if ( cnt == 1 || nowSum < arr(size - cnt) ) {
            nowSum += arr(size - cnt)
            
        } else {
            bResult = false
            break
        }
    loop
    
    return bResult
    
#global

    list = 128, 64, 32, 16, 8, 4
    mes IsSteepSlope(list)
    stop

Perlの方々の回答を参考にしました

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function is_super_dec( [array] $super_array )
{
    $total = 0    
    foreach( $x in reverse $super_array )
    {        
        if( $x -le $total ){ return 0 }
        $total += $x
    }
    return 1
}

is_super_dec @( 512,256,128,64,32,16,8,4,2,1 )

Index

Feed

Other

Link

Pathtraq

loading...
Creative Commons License このサイトの内容は、 クリエイティブ・コモンズ・ライセンスの下でライセンスされています。 [詳細]