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