JOI '15 春合宿 2：1 - ビルの飾りつけ 3

問題
解法
解答

問題

https://www.ioi-jp.org/camp/2015/2015-sp-tasks/2015-sp-d2.pdf

解法

元の数列である A を構成する条件は，

1 <= A_i <= max(A_0, A_1, A_2, ... , A_(i - 1) ) + 1

であるので，B_i も同様に

1 <= B_i <= max(B_0, B_1, B_2, ... , B_(i - 1) ) + 1

となる．まず，全ての B の要素が上の条件を満たすか調べる．もし，条件を満たしていない箇所がある場合，B のその箇所より前に要素を追加することで条件を満たすようにできるかどうか判定する．具体的には，

max(B_0, B_1, B_2, ... , B_(k - 1) ) と B_k の差が 2 以上ある箇所が１つでもある場合
1 <= B_i <= max(B_0, B_1, B_2, ... , B_(i - 1) ) + 1 を満たさない箇所が複数ある場合

に答えが 0 になる．max(B_0, B_1, B_2, ... , B_(k - 1) ) と B_k の差が 2 以上ある箇所が１つの時は，その箇所の前までで (B_k) - 1 を追加できる箇所の数が答えになる．B だけで条件を満たしている場合は，全ての箇所について追加できる数の通り数を足し合わせればよい．この時，B_(i - 1) と B_i，B_i と B_(i + 1) の間に同じ要素を入れると作られる A はどちらも同じものになってしまい重複が発生するので，答えから N - 1 を引く．O(N)．