Module d
Expand description
§ABC 384 D - Repeated Sequence
refs: https://atcoder.jp/contests/abc384/tasks/abc384_d
解となる文字列が $N$ 項を部分文字列に含むたびに, その部分列の和は最初の $N$ 項の総和分増加する. これはどの部分列を取る場合に置いても同様になる.
もし長さ $N$ 未満の部分列で, その部分列の和が $S$ を最初の $N$ 項の総和で割った余りとなるものが存在する場合, その部分列の間に繰り返される $N$ 項を挟むことで, 総和を $S$ にすることができるため, この部分列が存在するかどうかのみ確認すれば良い. 長さ $N$ 未満の部分列の探索については, 最初の $N$ 項の後に繰り返される領域を考慮する必要がある.
部分列の和は累積和を求めておくことで, 高速に探索できる.
use proconio::input;
fn main() {
input! {
n: usize, s: usize,
a: [usize; n],
}
let sum = a.iter().sum::<usize>();
let t = s % sum;
let b = a.repeat(2).iter().fold(vec![], |mut acc, &x| {
match acc.last() {
Some(&last) => acc.push(x + last),
None => acc.push(x),
}
acc
});
for i in 0..b.len() {
if b.binary_search(&(b[i] + t)).is_ok() {
println!("Yes");
return;
}
}
println!("No");
}