Weekly Contest 153 : 1187. Make Array Strictly Increasing

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

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

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

Java(Kotlin)で遅くなる書き方まとめ

こうすると遅い!!!

理由 10^5回の差分 遅い提出 速い提出
FastScannerでなく標準ライブラリのScannerを使う 400ms カツサンドくん β カツサンドくん β
FastScannerでなくkotlin.io.readLine()!!.split(" ") 260ms カツサンドくんβ カツサンドくん β
PrintWriterでなく標準のprintlnを使う 500ms
グラフで二次元配列でなくArrayList<T>[]を使う 900ms don't be late don't be late
Int?を使う(ボクシング/アンボクシングの発生) 300ms Virus Tree 2 Virus Tree 2

Rustの演算子優先順位表

載っているサイトがいまいち見つからなかったので、プログラミングRustから引用する。 上ほど優先順位が高い。

名前
タプル/構造体フィールドアクセス、メソッド呼び出し、関数呼び出し、インデックス point.x, point.m(), stdin(), arr[0]
エラーチェック create_dir("tmp")?
not, 単項マイナス、参照解決、借用 !ok, -num, *ptr, &val
型キャスト x as u32
掛け算、割り算、余り n*2, n/2, n%2
足し算、引き算 n-2, n+2
シフト n << 1, n >> 1
bit and n & 1
bit xor n ^ 1
bit or n | 1
不等号、等号 n < 1, n <= 1, n > 1, n >= 1, n == 1, n != 1
and x.ok && y.ok
or x.ok || backup.ok
範囲 start..stop
代入 x = val, x *= 1, x /= 1, x %= 1, x += 1, x -= 1, x <<= 1, x >>= 1, x &= 1, x ^= 1, x |= 1
クロージャ |x, y| x + y

HashMapでdpすることができなくもない

概要

  • RustのHashMapのラッパーを作ってIndex, IndexMutトレイトを実装すると配列のように使えて便利
  • でも流石に大きな定義域でループを回すとTLEする

HashMapをindexで参照と可変参照できるようにする

github.com

昔はあったらしいHashMapのIndexMut実装は↑によって消されてしまったので独自実装する。

#[allow(unused_macros)]
macro_rules! map {
    () => {
        IndexMap(std::collections::HashMap::new())
    };
    ($value:expr; $key_iter:expr) => {
            IndexMap(($key_iter).map(|k| (k, $value)).collect::<std::collections::HashMap<_,_>>())
    };
    ($value:expr; $($key:expr);*) => {
        map!($($key);* => $value)
    };
    ($head:expr; $($tail:expr);* => $init:expr) => {
        map![map!($($tail);* => $init); $head]
    };
    ($head:expr => $init:expr) => {
        map![$init; $head]
    };
}

// HashMapのラッパー
#[derive(Debug, Clone, Default)]
struct IndexMap<K: Eq + std::hash::Hash, V>(pub std::collections::HashMap<K, V>);

#[allow(dead_code)]
impl<K, V> std::ops::Deref for IndexMap<K, V>
where
    K: Eq + std::hash::Hash,
{
    type Target = std::collections::HashMap<K, V>;
    fn deref(&self) -> &Self::Target {
        &self.0
    }
}

#[allow(dead_code)]
impl<'a, K, V, Q: ?Sized> std::ops::Index<&'a Q> for IndexMap<K, V>
where
    K: std::borrow::Borrow<Q> + Eq + std::hash::Hash,
    Q: Ord + Eq + std::hash::Hash,
{
    type Output = V;

    fn index(&self, index: &Q) -> &V {
        self.0.get(index).expect("no entry found for key")
    }
}

#[allow(dead_code)]
impl<'a, K, V, Q: ?Sized> std::ops::IndexMut<&'a Q> for IndexMap<K, V>
where
    K: std::borrow::Borrow<Q> + Eq + std::hash::Hash,
    Q: Ord + Eq + std::hash::Hash,
{
    fn index_mut(&mut self, index: &Q) -> &mut V {
        self.0.get_mut(index).expect("no entry found for key")
    }
}

上で定義したIndexMapはDerefによって中身のHashMapにすることもできる。 これで let mut a = map![0; 0..20; "abc".chars()]; とかすれば a[&0][&'b'] = 20 とかして配列のようにアクセスできるのでdpだって書けてしまう。

調子にのって大きめの定義域で回すと遅い

Submission #5311611 - AtCoder Beginner Contest 122

これは上とはmapマクロの定義が少し違うが、定義域がchar5個分しかないので普通にACできている。

Submission #5400783 - AtCoder Beginner Contest 082

でもこっちは -8000..8000 でdpを回して、TLEしてしまう。 Vec だと600msくらいでAC。調子に乗ってはいけない。

ローリングハッシュ法でご丁寧にmodを取っていると時々TLEする

概要

内容

  • 2つの互いに素な数をB, MとしてBの(係数つき)べき乗の和をmod Mしてハッシュを取る
  • M=2^64 としてunsigned intで計算してオーバーフロー前提で計算すると速い
  • Rustだとリリースビルド以外は普通オーバーフローはpanicなので丁寧に %M していこうかなと思った
    • これが結構遅くて時々TLEするくらい
    • 文字が u8 であることを前提に省略できる %M を省略して、前処理できるものを関数から逃がすとなんとか通る
  • オーバーフロー許容構造体の Wrapping で包んで M=2^64 として書くのが良さそう

ご丁寧版(TLE)

yukicoder.me

pub fn search_rh(base: &[u8], key: &[u8]) -> Vec<usize> {
    const B: i64 = 9973;
    const M: i64 = 1_000_000_007;
    let key_len = key.len();
    let base_len = base.len();
    if key_len > base_len {
        return vec![];
    }
    let mut t = 1i64;
    for _ in 0..key_len {
        t *= B;
        t %= M;
    }
    let mut key_h = 0;
    let mut base_h = 0;
    for i in 0..key_len {
        key_h = (key_h * B % M + key[i] as i64) % M;
        base_h = (base_h * B % M + base[i] as i64) % M;
    }
    let mut ret = vec![];
    {
        let mut i = 0;
        while i + key_len <= base_len {
            if key_h == base_h {
                ret.push(i);
            }
            if i + key_len < base_len {
                let p = base_h * B;
                let q = base[i + key_len] as i64;
                let r = base[i] as i64 * t;
                let mut z = (p + q - r) % M;
                if z < 0 {
                    z += M;
                }
                base_h = z;
            }
            i += 1;
        }
    }
    ret
}

Wrappingに加えて少し抽象化したもの(AC)

yukicoder.me

pub fn search_rh<T: Into<u64> + std::clone::Clone>(base: &[T], key: &[T]) -> Vec<usize> {
    use std::num::Wrapping;
    const B: Wrapping<u64> = Wrapping(1_000_000_007u64);
    let key_len = key.len();
    let base_len = base.len();
    if key_len > base_len {
        return vec![];
    }
    let mut t = Wrapping(1u64);
    for _ in 0..key_len {
        t *= B;
    }
    let mut key_h = Wrapping(0u64);
    let mut base_h = Wrapping(0u64);
    for i in 0..key_len {
        key_h = key_h * B + Wrapping(key[i].clone().into());
        base_h = base_h * B + Wrapping(base[i].clone().into());
    }
    let mut ret = vec![];
    {
        let mut i = 0;
        while i + key_len <= base_len {
            if key_h == base_h {
                ret.push(i);
            }
            if i + key_len < base_len {
                base_h = base_h * B + Wrapping(base[i + key_len].clone().into())
                    - Wrapping(base[i].clone().into()) * t;
            }
            i += 1;
        }
    }
    ret
}

VSCode 拡張の SVG Editor つくった

VSCodeマーケットプレイスはここです

!https://github.com/Henoc/svgeditor/raw/master/images/out.gif

まだSVGの色々な記法に対応できてないです...
previewHtmlコマンドというのがあることを知って、これならなんでもできるじゃん!てことで作りました。VSCodeの現在適用されているテーマの色とかが取れないんですが、透過色などで色々ごまかしてボタンのデザインをしているのがコツです。previewから元の拡張のコードにデータを受けわたすのはリンク方式しかないんですが、リンクをクリックしたことにするコードをpreviewのjs上で使えば任意のタイミングでデータの受け渡しが可能です。Markdownの拡張にもこの方法が使われているらしいです。みんなには内緒だよ。

(Scala)ある型クラスを実装する任意クラスのインスタンス列が持てるやつ

適当にググってもでてこないのでうんうんうなっていたらできた。僕みたいなうなり声を上げる人が少なくなるようにブログに書いておきます。

ある型クラス F を実装するクラス A, B, C, ... があって、それらのインスタンスの列を引数にとってどこかのクラス Collector にフィールドとして保存する。 Collector ではその列の各要素について F のメソッドを使いたい。そういうときは

を保存しておく型クラス Box[F] { type Content = A }を別に用意して、それの列を引数にとるとなんとかなるみたいです。

@typeclasssimulacrumというライブラリで、 typeClassImpl.show(a)a.show とかけるようになるやつです。今回の題とは関係ないですが見やすいので。

Box の型パラメータに A を持っていくと Seq にするときに Any になって個別の型が消し飛んでしまいます。なので Box のメンバーに入れて隠します。

うーん疲れた...もっと簡単な書き方があったら教えてください。