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 のメンバーに入れて隠します。

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

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

勝率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|

院試の昔話

昔々あるところにおじいさんとおじいさんとおじいさんとおじいさんと...

同期が院試(東京大学大学院 情報理工学研究科 創造情報学専攻)について書いてたから何となく書いとこうかなってなった
でももうあんまり覚えてないや…受け方は京都も東京も以下の同期の人と同じなので,詳しい対策とか以下参照

tonton-buhi.hatenablog.com

しかし自分の場合,自大は東京と日程が被っていたので自大は受けずにNAISTを代わりに受けた
日程は
NAIST試験NAIST発表京都試験東京試験京都発表東京発表
だったから,NAIST落ちたら安全のために東京を諦めて自大にしようと思っていた

TOEFL

他のブログとか色々見て,配点が少なそうなのと,それほど差がつかないだろうと思ったので,普通のTOEFLを1回受けて半分くらいとれたからそれで終わった.多分 63/120.

京都の話

システム科学専攻を受けた

だれててあまり勉強できていなかったので,全然解けなくて焦った.線形代数は直交補空間,部分空間とかかなりやった部分なのに忘れていたのでショックだったし,論理回路は毎回計算がややこしいので当日もヒーヒーしていたし,工業数学(複素解析)は実積分への応用が出たけど大切な部分を忘れて計算できず青ざめていた.ここを受けてから尻に火がついたと思う.第二志望に受かった

東京の話

数学と電子情報学の専門を受けた

専門を創造情報学でなく電子情報学にしたのは,学部でやったことが多かった(電気電子回路を除く)のと,創造情報学と比べて範囲が安定している印象があったから

数学の解析の範囲,結局最後までベクトル解析が入るのかどうなのか自信がなくて,院試前夜に「やっぱ入ってるんじゃね?」ってなって高速で読書していた.前日にそういうのするのは意味ないしやめた方がいいよ(アドバイス)
でも未だに範囲内なのかよくわからない

数学は自分の年は難化していて,5割くらいしか書けなかったけど,多分難化してたから助かった.例年通りの難易度だと俺は解くのが遅いから差がついてやばかったと思う

専門科目はやっぱりどこが難化するか予想できないから全部勉強した方がいいと思う.過去問見て得点源だと思っていたコンピュータアーキテクチャが当日手も足も出なかったし…(泣く泣く情報理論に切り替えた)

というか一番力入れて勉強してたフーリエラプラスz変換あたりが全く出なかったの,どういうことなの…こういうのが試験って本当怖い
信号処理論でおすすめなのは以下

www.ic.is.tohoku.ac.jp

第一志望に受かった

後何か思い出したら書きます