AT1202Contest_h Incomplete Notes

[problemUrl]: https://atcoder.jp/contests/DEGwer2023/tasks/1202Contest_h それぞれ長さが $ N $, $ M $ の 2 つの非負整数列 $ A\ =\ (A_1,\ \dots,\ A_N) $, $ B\ =\ (B_1,\ \dots,\ B_M) $ が与えられます． $ 1\ \le\ i\ \le\ N\ -\ M\ +\ 1 $ を満たす整数 $ i $ のうち，以下の条件を満たすものの個数を求めてください． ##### 条件 > $ A $ の長さ $ M $ の連続部分列 $ C $ を $ C\ =\ (A_i,\ \dots,\ A_{i\ +\ M\ -\ 1}) $ で定める．次に，数列 $ B $, $ C $ の各要素のうち値が $ 0 $ であるもの全てを任意の **正の実数** で更新する（更新後の値は各要素で異なっていてよい）．その後， **正の実数** $ t $ を任意に定め，数列 $ C $ の全ての要素に $ t $ を乗じる．このようにして得られた数列 $ B $ と $ C $ を一致させることができる．

N/A

N/A

### ストーリー あなたは $ N $ 個の音からなる歌が途切れ途切れ聞こえた．この歌に， $ M $ 個の音からなるフレーズが含まれていたかどうかを推測したい．ただし，フレーズが本来と異なる [調](https://ja.wikipedia.org/wiki/%E8%AA%BF) で含まれている場合も考慮したい． ### 制約 - $ 1\ \leq\ M\ \leq\ N\ \leq\ 5\ \times\ 10^5 $ - $ 0\ \leq\ A_i\ \leq\ 5\ \times\ 10^5 $ $ (i\ =\ 1,\ \ldots,\ N) $ - $ 0\ \leq\ B_i\ \leq\ 5\ \times\ 10^5 $ $ (i\ =\ 1,\ \ldots,\ M) $ ### Sample Explanation 1 $ i\ =\ 1 $ のとき， $ B $ を $ (6,\ 2,\ 5,\ 4) $ に，また $ C\ =\ (9,\ 3,\ 0,\ 0) $ を $ (9,\ 3,\ 7.5,\ 6) $ に更新し， $ t\ =\ 2/3 $ ととると最終的に $ B $ と $ C $ が一致します． $ i\ =\ 2,\ 3,\ 4 $ のときも，適切に操作を行うことで $ B $ と $ C $ を一致させることが可能ですが， $ i\ =\ 5,\ 6 $ のときは不可能です． 以上より， $ i\ =\ 1,\ 2,\ 3,\ 4 $ の $ 4 $ 個が条件を満たすので答えとして $ 4 $ を出力します．