https://atcoder.jp/contests/abc271/tasks/abc271_d
カードの組と和でDPすればいいです。この時、1歩前の和を記録しておくとDPが終わった後にtrace backできて文字列を作ることができます。
後ろから追加していくので、あとから逆順の文字列にします。
// Flip and Adjust #![allow(non_snake_case)] use std::cmp::max; //////////////////// 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() } //////////////////// process //////////////////// fn read_input() -> (i32, Vec<(i32, i32)>) { let v = read_vec(); let N = v[0]; let S = v[1]; let ab = (0..N).map(|_| { let w = read_vec(); (w[0], w[1]) }). collect::<Vec<(i32, i32)>>(); (S, ab) } fn f(S: i32, ab: Vec<(i32, i32)>) -> (bool, String) { let N = ab.len(); let max_sum = ab.iter().map(|(a, b)| max(*a, *b)).sum::<i32>(); if S > max_sum { return (false, "".to_string()) } let mut dp = (0..(N+1)).map(|_| (0..(max_sum+1)). map(|_| -1).collect::<Vec<i32>>()). collect::<Vec<Vec<i32>>>(); dp[0][0] = 0; for (i, (a, b)) in ab.iter().enumerate() { for s in 0..(max_sum as usize + 1) { let s_prev = dp[i][s]; if (i == 0 && s != 0) || (i > 0 && s_prev == -1) { continue } dp[i+1][s+(*a as usize)] = s as i32; dp[i+1][s+(*b as usize)] = s as i32 } } if dp[N][S as usize] == -1 { return (false, "".to_string()) } let mut ht_rev = String::from(""); let mut s = S; for i in (0..N).rev() { let (a, _b) = ab[i]; let d = s - dp[i+1][s as usize]; ht_rev += if d == a { "H" } else { "T" }; s = dp[i+1][s as usize] } let ht: String = ht_rev.chars().rev().collect(); (true, ht) } fn main() { let (S, ab) = read_input(); match f(S, ab) { (true, ht) => println!("Yes\n{}", ht), (false, _) => println!("No") } }