SRM 395 Div1 Medium Skyscrapers

問題

1からNまでの高さを持つ、N棟の建物が一直線上に並んでいる。これらを左端から眺めた時に、i番目の建物が見えるというのは、0〜i-1番目の建物がi番目の建物より低い時である。右端から眺めた時に見える場合はi+1〜N-1番目の建物がi番目の建物より低い時である。左端から眺めた時にleftside個の建物が見え、右端から眺めた時にrightside個の建物が見えるような建物の並べ方の順列数を求めて、1000000007で割ったあまりを返せ。

やりかた

Editorialを参考にしました。

左端か右端から一番小さい建物を並べていくことを考える。
（残り、左から見て見える数の残り、右から見て見える数の残り）=（N,L,R）という状態から始まるわけだが、まず一番小さい建物を①左端に置く、②右端に置く、③それ以外に置くことが考えられる。
①一番左端に置いた場合を考えると、これは必ず見えるのでL-1となる。するとこの建物は以後の処理に全く関係なくなる（一番小さいので他の建物を見えなくさせることがない）のでなくなったものとして(N-1,L-1,R)という状態にして考えてもよいことになる。これは②の右端に置いた場合も(N-1,L,R-1)で同じことになる。③の場合は、そもそも絶対に見えなくなる位置に置いてしまうため、なくなったことにしてしまってよいので(N-1,L,R)として次状態を考えればいい。ただし置き場所にN-2ヶ所の選択肢がある。これはメモ化再帰で簡単に解ける。