https://atcoder.jp/contests/abc265/tasks/abc265_d
各解はしゃくとり法で求められるので、その解をたどっていきます。
// Iroha and Haiku (New ABC Edition) #![allow(non_snake_case)] use std::collections::HashMap; //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read_line(&mut line).ok(); line.trim().parse().ok().unwrap() } fn read_vec<T: std::str::FromStr>() -> Vec<T> { read::<String>().split_whitespace() .map(|e| e.parse().ok().unwrap()).collect() } fn YesNo(b: bool) -> String { return if b { "Yes".to_string() } else { "No".to_string() } } //////////////////// process //////////////////// fn read_input() -> (Vec<i64>, Vec<i64>) { let v = read_vec(); let P: i64 = v[1]; let Q: i64 = v[2]; let R: i64 = v[3]; let A: Vec<i64> = read_vec(); (vec![P, Q, R], A) } fn accumulate(A: Vec<i64>) -> Vec<i64> { let mut B: Vec<i64> = Vec::new(); B.push(0); let mut acc = 0; for a in A.into_iter() { acc += a; B.push(acc) } B } fn solve_each(S: i64, B: &Vec<i64>) -> Vec<(usize, usize)> { let mut kls: Vec<(usize, usize)> = Vec::new(); let N = B.len(); let mut k: usize = 0; let mut l: usize = 1; while l < N { if S == B[l] - B[k] { kls.push((k, l)); k += 1; l += 1 } else if S > B[l] - B[k] { l += 1 } else { k += 1 } } kls } fn walk(vs0: Vec<usize>, i: usize, v: Vec<i64>, B: Vec<i64>) -> bool { if i == v.len() { return !vs0.is_empty() } let mut vs : Vec<usize> = Vec::new(); let range = solve_each(v[i], &B); let dic: HashMap<usize, usize> = range.iter().map(|&v| v).collect(); for v0 in vs0.iter() { match dic.get(v0) { Some(v1) => vs.push(*v1), None => () } } walk(vs, i + 1, v, B) } fn f(v: Vec<i64>, A: Vec<i64>) -> bool { let B = accumulate(A); let vs0: Vec<usize> = (0..B.len()).collect(); walk(vs0, 0, v, B) } fn main() { let (v, A) = read_input(); println!("{}", YesNo(f(v, A))) }