AtCoder Beginner Contest 403 F

https://atcoder.jp/contests/abc403/tasks/abc403_f

DPなのですが、足し算の結果は次に括弧をつけないと掛け算に使えないところがいやらしいので、掛け算に使えるのと使えないの両方の値を保持しておきます。あと111とかは最初に決めておきます。

// Shortest One Formula
#![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()
}


//////////////////// process ////////////////////

fn F(N: usize) -> String {
    // そのまま掛け算に使える
    let mut a: Vec<String> = vec![String::new(); N+1];
    // 括弧があれば掛け算に使える
    let mut b: Vec<String> = vec![String::new(); N+1];
    for i in 1u32.. {
        let n = 10usize.pow(i) / 9;
        if n > N {
            break
        }
        a[n] = format!("{}1", a[n/10]);
        b[n] = a[n].to_string()
    }
    
    for n in 2..N+1 {
        // 足し算
        for x in 1..n/2+1 {
            let y = n - x;
            if b[x].is_empty() || b[y].is_empty() {
                continue
            }
            let m = b[x].len() + b[y].len() + 1;
            if a[n].is_empty() || m + 2 < a[n].len() {
                a[n] = format!("({}+{})", b[x], b[y])
            }
            if b[n].is_empty() || m < b[n].len() {
                b[n] = format!("{}+{}", b[x], b[y])
            }
        }
        
        // 掛け算
        for x in 2.. {
            if x * x > n {
                break
            }
            else if n % x != 0 {
                continue
            }
            let y = n / x;
            let m = a[x].len() + a[y].len() + 1;
            if a[n].is_empty() || m < a[n].len() {
                a[n] = format!("{}*{}", a[x], a[y])
            }
            if b[n].is_empty() || m < b[n].len() {
                b[n] = format!("{}*{}", a[x], a[y])
            }
        }
    }
    b[N].to_string()
}

fn main() {
    let N: usize = read();
    println!("{}", F(N))
}