AtCoder Beginner Contest 271 D

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")
    }
}