https://atcoder.jp/contests/abc275/tasks/abc275_d
ABCのD問題を解いていきます。
単なるメモ化の問題ですが、Rustではグローバル変数が難しいので、みっともないですが関数にメモを渡します。
// Yet Another Recursive Function #![allow(non_snake_case)] use std::collections::HashMap; 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 f(N: usize, memo: &mut HashMap<usize, usize>) -> usize { match memo.get(&N) { Some(&y) => y, None => { let y = f(N/2, memo) + f(N/3, memo); memo.insert(N, y); y } } } fn main() { let N = read(); let mut memo: HashMap<usize, usize> = HashMap::<usize, usize>::new(); memo.insert(0, 1); println!("{}", f(N, &mut memo)) }