こんにちは、ゆーてぃーです。今回は「ゆーてぃーのAtCoder精進【14日目】」ということで、2024年12月14日に行われたABC384のD問題を解きたいと思います。

問題

D - Repeated Sequence

問題ページ

問題文

周期 $N$ をもつ無限数列 $A=(A_1,A_2,A_3,…)$ の先頭 $N$ 項 $A_1,A_2,…,A_N$ が与えられます。

この数列の空でない連続する部分列のうち、和が $S$ となるものが存在するか判定してください。

ただし、無限数列 $A$ が周期 $N$ をもつとは、 $i > N$ を満たすすべての整数 $i$ に対して $A_i=A_{i−N}$ が成り立つことをいいます。

制約

$1 \leqq N \leqq 2 \times 10 ^ 5$
$1 \leqq A_i \leqq 10 ^ 9$
$1 \leqq S \leqq 10 ^ {18}$
入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

$N\ S$

$A_1\ A_2\ ...\ A_N$

出力

$A$ の連続する部分列 $(A_l,A_{l+1},…,A_r)$ であって、 $A_l+A_{l+1}+⋯+A_r=S$ となるものが存在するならば Yes を、そうでないならば No を出力せよ。

ゆーてぃーの解法

先頭 $N$ 項のまとまりで考えると、 $S=$ 先頭 $N$ 項の総和 $\times n +$ 先頭 $N$ 項の一部の総和となることがわかります。そしてその一部は必ず先頭 $N$ 項のうち連続している部分の和となるので、 $S \%$ 先頭 $N$ 項の総和の値が連続している部分の和かどうか判断すれば求められます。先頭 $N$ 項の累積和をとることで先頭 $N$ 項の部分和を計算することができます。ただし、数列 $1\ 2\ 3\ 4\ 1\ 2\ 3\ 4\ 1\ 2\ 3\ 4$ のうちの $4\ 1\ 2\ 3\ 4\ 1\ 2$ の部分が答えになっているとまとまり以外の連続している部分は $4\ 1\ 2$ となります。これは先頭 $4$ 項の一番右の $4$ から連続した3つを取らないといけません。なので先頭 $N$ 項を2つ並べて累積和とることで実現できます。右(2つ目の先頭 $N$ 項)にずれていくごとに探索範囲外となった $A_i$ を引いていけば先頭 $N$ 項の $N-1$ から $2$ 番目の総和も求められます。