AtCoder Beginner Contest 419 E

https://atcoder.jp/contests/abc419/tasks/abc419_e

入力例1なら、長さLの幅にして、

4 2 1
3

各列の要素がMの剰余で同じにして、一番上の行を足したらMの剰余で0になるようにします。
DPを使うことを考えて左から右に更新していきます。状態を一番上の行のそこまでの和のMの剰余、値を操作回数の最小値とします。頑張れば1回のDPの更新の計算量はになるので、全体の計算量はとなってなんとか間に合います。実際には0.2sec程度でした。

// Substr Swap
#![allow(non_snake_case)]

use std::cmp::min;


//////////////////// 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() -> (usize, usize, Vec<usize>) {
    let v: Vec<usize> = read_vec();
    let (M, L) = (v[1], v[2]);
    let A: Vec<usize> = read_vec();
    (M, L, A)
}

fn divide(A: Vec<usize>, M: usize, L: usize) -> Vec<Vec<usize>> {
    let mut table: Vec<Vec<usize>> = vec![vec![]; L];
    for i in 0..A.len() {
        table[i%L].push(A[i] % M)
    }
    table
}

fn initialize_dp(M: usize) -> Vec<usize> {
    let mut dp = vec![100000000; M];
    dp[0] = 0;
    dp
}

fn update_dp(v: Vec<usize>, dp: Vec<usize>) -> Vec<usize> {
    let M = dp.len();
    let mut a: Vec<usize> = vec![0; M];
    for &e in v.iter() {
        a[e] += 1
    }
    
    let mut new_dp: Vec<usize> = vec![100000000; M];
    let mut s: usize = v.iter().map(|&e| M - 1 - e).sum::<usize>();
    for i in 0..M {
        if a[i] == 0 {
            s += v.len()
        }
        else {
            s = s + v.len() - M * a[i]
        }
        for j in 0..M {
            let r = (i + j) % M;
            new_dp[r] = min(new_dp[r], dp[j] + s)
        }
    }
    new_dp
}

fn F(M: usize, L: usize, A: Vec<usize>) -> usize {
    let table = divide(A, M, L);
    let mut dp = initialize_dp(M);
    for v in table {
        dp = update_dp(v, dp)
    }
    dp[0]
}

fn main() {
    let (M, L, A) = read_input();
    println!("{}", F(M, L, A))
}