セグ木とか必要なくて、本当に単純な実装で解けるの面白い
問題
制約
考えたこと
まずは、生成可能であるための分かりやすい特徴付けを考えようと思った。数列の生成手順が、いかにも入れ子構造をしているので、カッコ列を連想した。
カッコ列の連想から、次の判定手順が自然に得られた。
スタックを用意する。
数列を後ろから見ていくことにする。今見ている要素が であるとき
ならば、スタックに
を挿入する
ならば、階段になっている限りスタックを pop していく (たとえば、スタックが top から順に 2, 3, 4, 6, ... だとしたら、
最終状態において、スタックが空であることが、生成可能であるための必要十分条件である。
これで判定は解けた。
数え上げ
一般に、区間 が生成可能ならば、
に対して区間
も生成可能である。
よって、上に述べたようなスタックの処理をしながら、
であるような
に対して
- スタック操作後のスタックの先頭要素の添字を
として (空なら
として)、
を答えに合算していく
とすることで問題が解ける。計算量は となる。
