Weekly Contest 153 : 1187. Make Array Strictly Increasing

Pythonで書いてあった解法を見て書きました

arr1のある位置までで構成できる単調増加列について、最後尾の値をkey, その場合の置換処理の最小回数をvalueとしたdpを考える。それをHashMapでdpとする。 初期値として dp[-1] = 0 を入れておく。 あるarr1上の位置iに対して

1. arr1[i]があるkeyより真に大きい場合、遷移は２通り：
   1. arr2を使用せずそのまま単調増加列に追加する
   2. arr2からkeyを超える最小の要素を使い、単調増加列に追加する
2. そうでない場合、遷移は１通り：
   1. arr2からkeyを超える最小の要素を使い、単調増加列に追加する

use std::cmp::min;

impl Solution {
    pub fn make_array_increasing(arr1: Vec<i32>, mut arr2: Vec<i32>) -> i32 {
        let mut dp = Counter::new();
        arr2.sort();
        dp[-1] = 0;
        for p in arr1 {
            let mut tmp: Counter<i32> = Counter {cnt: HashMap::new(), d: std::usize::MAX};
            for (&key, &value) in dp.cnt.iter() {
                if p > key {
                    tmp[p] = min(tmp[p], value);
                }
                let loc = upper_bound(&arr2, &key);
                if loc < arr2.len() {
                    tmp[arr2[loc]] = min(tmp[arr2[loc]], value + 1);
                }
            }
            dp = tmp;
        }
        if dp.cnt.len() >= 1 {
            *dp.cnt.values().min().unwrap() as i32
        } else {-1}
    }
}

use std::collections::HashMap;
use std::iter::FromIterator;

#[derive(Clone, Debug)]
struct Counter<K: Eq + std::hash::Hash> {
    cnt: HashMap<K, usize>,
    d: usize,
}

#[allow(dead_code)]
impl <K: Eq + std::hash::Hash> Counter<K> {
    fn new() -> Counter<K> {
        Counter {cnt: HashMap::new(), d: 0}
    }
}

#[allow(dead_code)]
impl<K: Eq + std::hash::Hash> std::ops::Index<K> for Counter<K> {
    type Output = usize;

    fn index(&self, index: K) -> &Self::Output {
        self.cnt.get(&index).unwrap_or(&self.d)
    }
}

#[allow(dead_code)]
impl<K: Eq + std::hash::Hash + Clone> std::ops::IndexMut<K> for Counter<K> {
    fn index_mut(&mut self, index: K) -> &mut usize {
        if !self.cnt.contains_key(&index) {
            self.cnt.insert(index.clone(), self.d);
        }
        self.cnt.get_mut(&index).unwrap()
    }
}

#[allow(dead_code)]
impl<K: Eq + std::hash::Hash> FromIterator<K> for Counter<K> {
    fn from_iter<T: IntoIterator<Item=K>>(iter: T) -> Self {
        let mut cnt = HashMap::new();
        for i in iter {
            *cnt.entry(i).or_insert(0) += 1;
        }
        Counter {cnt: cnt, d: 0}
    }
}

#[allow(dead_code)]
fn upper_bound<T: Ord>(arr: &[T], x: &T) -> usize {
    let mut ok = arr.len() as i64;
    let mut ng = -1i64;
    while (ok - ng).abs() > 1 {
        let mid = (ok + ng) / 2;
        if &arr[mid as usize] > x {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    ok as usize
}