きままにものづくり

日々の気付いたことなんかを書いてます。

ARC023 C問題

問題


C: タコヤ木 - AtCoder Regular Contest 023 | AtCoder

解法

−1の連続する区間を取り出す。例として2 -1 -1 9を取り上げる。この時の組み合わせは、3回の足し算で2を9にするための組み合わせとなる。つまり、A B Cの3変数があり2+A+B+C=9となる時のA B Cの組み合わせの数である。これは重複組み合わせに帰着できる。-1の個数をm、両端の差分をnとした時
 {}_{n+m}C_m
と表せる。
これらを掛け合わせることで答えが求まる。

計算量

 O(N R)
N:要素数
R:-1の連続数

コード

広告を非表示にする