Stairs(階段) - joi2010-day1 解説

筆者: qnighy

階段の上り方の総数を数える問題である。

O(N^2)解法

一見して、この問題はおそらく動的計画法であると想像がつくだろう。

そこで、漸化式を立てると

a[k] (0 ≤ k ≤ N) … k段目に登る上り方の総数、とおいて

• a⁰ = 1
• a[i] = Σ(iとjの間のh[k]の総和がP以下となるようなa[j])

この漸化式の各ステップにおいて、jをi-1から下げつつ嘗めれば、O(N)で実行でき、全体ではこのDPはO(N^2)で処理できることがわかる。

この方法では50点を得ることができる。

O(N)解法

上記手法のボトルネックは、明らかに総和計算である。これを削減すればよい。

基本的には尺取法(しゃくとり虫になぞらえて命名されたようだ.)と呼ばれる手法に近いことを行う。

• a[i] = (a[j]a[j1]…a[i-1])
• P ≥ (h[j]h[j1]…h[i-1])

だったとする。ここで、a[i+1]について同じことを考えると、

• a[i+1] = (a[k]a[k1]…a[i-1]+a[i])
• P ≥ (h[k]h[k1]…h[i-1]+h[i])

Pの不等式について、左端にh[i]が付加されることから、右端についてはその要素は減る(か同じ)、つまり、j≤kだとわかる。

ここで、k:=jとおいて、上記不等式が成立するまで、kを増やしていけば、目的のkが得られることがわかる。

このとき、a[k]を記憶しておけば、aの総和計算も同時に行うことができる。

これらの操作は一見1つのiにつきO(N)で抑えるしかないように見えるが、実際は合計でO(N)回しか実行されないので、ならし計算で1つのiにつきO(1)で抑えられると言える。

この方法ならばO(N)で計算でき、満点を得ることができる。