Weekly Contest 153 : 1187. Make Array Strictly Increasing
arr1のある位置までで構成できる単調増加列について、最後尾の値をkey, その場合の置換処理の最小回数をvalueとしたdpを考える。それをHashMapでdp
とする。
初期値として dp[-1] = 0
を入れておく。
あるarr1上の位置iに対して
arr1[i]
があるkeyより真に大きい場合、遷移は2通り:- arr2を使用せずそのまま単調増加列に追加する
- arr2からkeyを超える最小の要素を使い、単調増加列に追加する
- そうでない場合、遷移は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で参照と可変参照できるようにする
昔はあったらしい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 つくった
まだ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|