kuretchi's blog

kuretchi's blog

競技プログラミングなどなど...

競技プログラミング

Rust で自動メモ化マクロ

作ってしまいました.かなり雑.Rust 1.15.1 で動きます. macro_rules! __memoize_internal { (@vec $FRetT:ty) => { Option<$FRetT> }; (@vec $FRetT:ty, $memo_param_head:ident $(, $memo_param:ident)*) => { Vec<__memoize_internal!(@vec $FRetT $(, $memo_param)*)> }; (@indices [$($t:tt)*]) => { [$($t</__memoize_internal!(@vec>…

Rust の多次元 Vec を初期化するマクロ

小ネタ. Rust で多次元 Vec (dp[0][1][2] のように使えるもの) を作りたい.例えば None で初期化された $2 \times 3 \times 4$ の Vec<Vec<Vec<Option<T>>>> を作るときはこう書く. vec![vec![vec![None; 4]; 3]; 2] うーん.という訳でこんなマクロ. macro_rules! nested_</vec<vec<option<t>…

桁 DP の一般化 (オートマトン DP)

桁を文字,数を文字列と考え,桁 DP の状態と遷移をオートマトン上で扱うことで,様々な桁 DP の問題に一般的なアルゴリズムを与えるオートマトン DP を紹介します.

"遅延伝播" の一般化

よく混乱するので,自分用のメモとして分かりやすくまとめておく. 遅延伝播*1についての説明は省略. 要件 半群 $(S, \bullet)$,モノイド $(O, \circ, e)$ と,(外部) 二項演算 $\triangleleft : S \rightarrow O \rightarrow S$ について, $\forall s \i…

yukicoder - No.585 工夫のないパズル

https://yukicoder.me/problems/no/585 コンテスト中、A 問題を通した後ずっとこれを実装していて、結局間に合わず 1 完になった。でも ★4 AC は嬉しい。 概要 4 × 4 のスライドパズルを解く問題。いわゆる 15 パズル と似ているが、空きマスがない代わりに…

ソートと要素のインデックス

ここらへんでハマってとてもつらかったので書いておきます。 ソート後のインデックスから、ソート前のインデックスを知りたい 方法1 インデックスとのペアのコレクションを作り、要素をキーとしてソートする。 char arr[5] = { 'D', 'A', 'C', 'E', 'B' }; p…