問題
N 本の木の柱が左から右へ一列に並んだアスレチックがあります。左から i 本目の柱の高さは ai センチメートルです。
高橋君は左から 1 本目の柱からスタートし、右へ柱を渡っていき N 本目の柱まで行こうとしています。
高橋君がある柱にいるとき、次には現在の柱から 1 個もしくは 2 個右にある柱のどちらかへ移動することができます。
移動するときには、現在いる柱の高さと、移動後の柱の高さの差の絶対値のぶんだけコストがかかります。
N 本目の柱まで行くとき、コストの合計の最小値はいくらになるでしょうか。
制約
2≦N≦100,000
0≦ai≦10,000
ai はすべて整数である。
入力形式
N
a1 a2 a3 ...
AtCoder Beginner Contest 040, C: 柱柱柱柱柱
#はまった
(*_*) { アルゴリズムの授業でやった再帰をちゃんとメモ化もして実装したのに！
**REというのはRuntime errorのことで、整数を0で割ったりした時のような、コンパイル（または文法チェック）のときには気づかないエラーが出ていることを指す
#元々のコード
(*_*) { 確かめに確かめたのに、、、
(0_0)!! { inputが大きいケース試してない!!
#案の定
N = 100,000のケースの入力を作って入れてみた
# a1 a2 a3 .. a100000 の乱数を生成し、txtファイルに入れる
n = gets.chomp.to_i
File.open("input_c.txt", "w") do |f|
f.puts n
(1..n).each do |e|
f.print Random.rand(10000)
unless e == n
f.print " "
end
end
f.puts "\n"
end
# 生成したtxtファイルを上のプログラムに入力として入れる
$ruby c.rb < input_c.txt
!!!!!!!!!!!!!
stack level too deep
#stack level too deepとは
一般に関数が呼ばれると、（どの親関数から呼ばれたかという情報を保持するためにも）、プロセス(プログラム単位のこと）の（使っているメモリ領域の）スタック領域に関数情報が順々に積まれていく。
スタック領域とは、
あるプログラム(プロセス)を動かすために確保されるメモリ領域のうち、local変数や呼び出した関数の情報を保持しておくために取っておく領域
のことで、
この領域の前後には、例えばコンピュータを動かすのに必要なメモリ領域だったり他の大切な情報が入っている。（プロセスのメモリ領域は連続して確保されるので、文字通り「前後」に他の領域がある。）
なので、今回のように、nが大きくて、１つの関数から呼び出す関数の数が大きい、つまりtopレベルの関数呼び出しの完了のためには、大量の関数を呼び出し、スタック領域にめいいっぱい関数情報を積んでいかなければならない！なんてことになると、
（本来ならば）このスタック領域をはみ出してしまう！
しかしながら、先述したように、本当にスタック領域を超えて、他の重要な情報が入っているメモリに関数呼び出し（なんか笑）の情報を書き込んだら、
このプログラムを動かしているコンピュータ自体に支障を招きかねない。
なので予め、はみ出さないように、スタック領域をはみ出しそうなほど関数情報が積まれていったら(stackしていったら)、
プログラムが"stack level too deep"を出して終了するようになっている、ということだったのだ！（(~ω~) {...で合ってますかね？しかも文章長かったですね、ごめんなさい！）
#やっぱり先生は正しかった
再帰を学習したときに、
- 愚直に再帰→ 2) memo化で再帰→ 3)下から計算していく(普通のfor文で再帰的に関数は呼ばない)
の順に効率化を図っていく、と習った。
# E.g. fibonacciだったら
# 1) 愚直に再帰
def fib(n)
return 0 if n == 0
return 1 if n == 1
return a[n] = a[n-1] + a[n-2]
end
# 2) memo化で再帰
memo = Array.new(n+1, -1)
def fib(n, memo)
if memo[n] >= 0 return memo[n]
あとは上と一緒
end
# 3) for文で下からmemoを埋めていく
memo = Array.new(n+1, -1)
memo[0] = 0
memo[1] = 1
(2..n).each do |e|
memo[e] = memo[e-1] + memo[e-2]
end
return memo[n]
普段大きな入力を扱うことがあまりなく、
2)で終わっていたが、
計算量以外に、stack level too deepという罠があるとは。。
勉強になりました。
#答え
total = gets.chomp.to_i
a = gets.chomp.split(' ').map(&:to_i)
memo = Array.new(total+1, -1)
memo[1] = 0
memo[2] = (a[1] - a[0]).abs
(3..total).each do |e|
memo[e] = [memo[e-1] + (a[e-1] - a[e-2]).abs, memo[e-2] + (a[e-1] - a[e-3]).abs].min
end
puts memo[total]
より良い答えがあったら教えてもらえると助かります。
後記
(**) oO (他の人の答えを見てみたけど、普通にrecursionでやってた人もいるような気がしたんだけどなあ
(**) oO (RubyとC++とかの実行速度の速さの違いってやっぱりAtCoderなどでは考慮されないですかね、、？