ABC 129 C - Typical Stairs

リハビリっていうほど元々すごいわけでもないけどレポート提出が落ち着いたのでリハビリがてら解きました

diff 795

Total Accepted 122

回答時の方針

最近関数型言語に触れていたこともあり再帰脳で全探索しにいってしまった,当然間に合わず.

i番目の階段に辿り着く移動方法を以下のように定義した.

v[i]= v[i-1] + v[i-2]  (2 <= i)
v[0] = 0
v[1] = 1
v[2] = 2

途中でv[1]とv[2]について自身と前の階段が壊れていることを考慮していないことに気づき以下のように修正した.

if(b[1]) v[1] = 0;
else v[1] = 1;

if(b[2]) v[2] = 0;
else 
  if(b[1]) v[2] = 1;
  else v[2] = 2;

dpで計算するのが正答で上の解答も同じ方針なので特に問題はなかったが洗練されてない. 条件分岐が増えるとそれだけバグが混入する可能性が上がるのでなるべく条件分岐を考えずに済むコーディングを意識したい. 今回の場合だと

- v[0]=1とおくこと
- v[i+1] = v[i+1] + v[i]としてループを回す
- v[i+2] = v[i+2] + v[i]としてループを回す

これにより不要なif文は回避できた,結局はシンプルさに行き着くんだと改めて感じたのだった.