Weekly Contest 153 : 1187. Make Array Strictly Increasing

leetcode

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
}

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。調子に乗ってはいけない。

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 }を別に用意して、それの列を引数にとるとなんとかなるみたいです。

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

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

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

とあるゲームの最大連勝数の期待値

勝率p = 0.6のゲームがあったとして, x回やったときの最大連勝数の期待値E(x)はいくつか? という話. (元ネタは人狼オンライン...)
式を考えるのが面倒だったのでPythonの練習がてらモンテカルロる(誰か式教えて...). 

最大連勝数の期待値

結果

|   x |     E(x) |
|----:|---------:|
|   10|    3.5264|
|   20|     4.812|
|   30|    5.5511|
|   40|    6.0917|
|   50|     6.558|
|   60|    6.8769|
|   70|    7.2235|
|   80|    7.4595|
|   90|    7.6671|
|  100|    7.8445|
|  110|    8.0861|
|  120|    8.2694|
|  130|    8.3864|
|  140|    8.5268|
|  150|    8.6831|
|  160|    8.8097|
|  170|    8.8772|
|  180|    9.0426|
|  190|    9.1298|
|  200|    9.2271|
|  210|    9.2799|
|  220|    9.4045|
|  230|    9.4813|
|  240|    9.5403|
|  250|    9.6695|
|  260|    9.7226|
|  270|    9.7855|
|  280|    9.9046|
|  290|    9.9533|