Plush Toys~AtCoder~

https://atcoder.jp/contests/joi2017yo/tasks/joi2017yo_d

NOTE
This problem is in Japanese.

Solution

use proconio::input;
pub fn main() {
    input!(
        n: usize,
        m: usize,
        data: [usize; n],
    );
    let data = data.iter().map(|e| e - 1).collect::<Vec<usize>>();
    let mut cnt = vec![0; m];
    let mut cnt_sum = vec![vec![0]; m];
    for &d in data.iter() {
        cnt[d] += 1;
        for i in 0..m {
            let last_val = cnt_sum[i][cnt_sum[i].len() - 1] + if d == i { 1 } else { 0 };
            cnt_sum[i].push(last_val);
        }
    }
    const INF: usize = 1 << 60;
    let mut dp = vec![INF; 1 << m];
    dp[0] = 0;
    for s in 0..1 << m {
        let mut sum = 0;
        for i in 0..m {
            if s >> i & 1 == 1 {
                sum += cnt[i];
            }
        }

        for i in 0..m {
            if (s >> i) & 1 == 0 {
                dp[s | (1 << i)] = dp[s | (1 << i)]
                    .min(dp[s] + cnt[i] - (cnt_sum[i][sum + cnt[i]] - cnt_sum[i][sum]));
            }
        }
    }
    println!("{}", dp[(1 << m) - 1]);
}

Explanation

• cnt[i] := Number of i type toys
• cnt_sum[i][j] := Number of i type toys when examining the j toys from left to right on the shelf.
• dp[S] := Minimum number of operations for a new subset containing S types of toys.

for s in 0..1 << m {
    let mut sum = 0;
    for i in 0..m {
        if s >> i & 1 == 1 {
            sum += cnt[i];
        }
    }

    for i in 0..m {
        if (s >> i) & 1 == 0 {
            dp[s + (1 << i)] = std::cmp::min(
                dp[s + (1 << i)],                               dp[s] + cnt[i] - (cnt_sum[i][sum + cnt[i]] - cnt_sum[i][sum]),
            )
        }
    }
}

• sum := Total number of types already selected.

For the types of toys not yet included in the subset(S)

• (cnt_sum[i][sum + cnt[i]] - cnt_sum[i][sum]) := Number of toys that do not need to move.