AtCoder Beginner Contest 402 E

https://atcoder.jp/contests/abc402/tasks/abc402_d

残りの持ち金とどれをすでにクリアしたかでメモ化すればよいです。

// Payment Required
#![allow(non_snake_case)]


//////////////////// 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 ////////////////////

type Problem = (f64, f64, f64);

fn read_problem() -> Problem {
    let v: Vec<f64> = read_vec();
    (v[0], v[1], v[2] / 100.0)
}

fn read_input() -> (f64, Vec<Problem>) {
    let v: Vec<usize> = read_vec();
    let (N, X) = (v[0], v[1] as f64);
    let problems: Vec<Problem> = (0..N).map(|_| read_problem()).collect();
    (X, problems)
}

use std::collections::HashMap;

fn F_core(x: f64, problems: &Vec<Problem>, solved: i32,
                                memo: &mut HashMap<(i32, i32), f64>) -> f64 {
    if let Some(&y) = memo.get(&(x as i32, solved)) {
        return y
    }
    
    let mut exp_value: f64 = 0.0;
    for (i, &(S, C, p)) in problems.iter().enumerate() {
        if ((solved >> i) & 1) == 1 || x < C {
            continue
        }
        // 勝った場合
        let exp_value_win = S + F_core(x - C, problems, solved | (1 << i), memo);
        // 負けた場合
        let exp_value_lose = F_core(x - C, problems, solved, memo);
        let e = exp_value_win * p + exp_value_lose * (1.0 - p);
        if e > exp_value {
            exp_value = e
        }
    }
    memo.insert((x as i32, solved), exp_value);
    exp_value
}

fn F(X: f64, problems: Vec<Problem>) -> f64 {
    let mut memo: HashMap<(i32, i32), f64> = HashMap::new();
    F_core(X, &problems, 0, &mut memo)
}

fn main() {
    let (X, problems) = read_input();
    println!("{}", F(X, problems))
}