Rustで競技プログラミングを始めた人のためのデータ構造紹介とノウハウ書き留め
もともと自分のメモとして書いていたのですが、始める人の参考になればと思い公開しておきます。
データ構造の原理、基本は知っているものとみなします。
Rustのコレクション型まとめ (VecやHashMapなど) - Qiita
探索
https://qiita.com/e869120/items/25cb52ba47be0fd418d6#おねえさん問題に学ぶ探索アルゴリズム
一般に、コンピューターでは、1秒間に 10^8 ～ 10^9 回程度計算できるといわれています
DP
基本は漸化式と初期値（i=0の時）を与えればDP配列は全インデックス更新されることが前提。(そのように漸化式のコードを書く)
bool dp[][];
dp [i][j] = i番目で jが~~ だったときのT/F
などが例。
dpのvalueの型はアウトプットに合わせるべき。
dpは10^5単位はセグフォしない！
vec![0; 200000+1];
してもOk
dp[e+5][e+5]は普通にセグフォする。
二次元配列は
v = vec![vec![0;n];n];
i32で n=2 *10^4 まで受け付けられる。
答えをPで割ったものを出力せよ系はたいていdp
dpのインデックスオーバーフローをしないようにするためには？
https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_A&lang=ja
インデックスを~~円などのバリュー値にしてる場合は結構オーバーフローが起きてしまう。
(今回はdp[i]= i円の時の最小枚数 と定義してる)
for i in 0..n { dp[i+1] = dp[i] }
みたいなdpならフローを気にしなくていいが、そうではないdpの方が大半なので。
上記のリンクの問題は
for i
for c_i
dp[i+c_i] …
でループするがいつインデックスが nを超えてしまうかわからない。
→dp[i+c_i] のまえにif i + c_i ≤ n を挟んで超えてしまうときを作らければOk
→それだと二重ループでdp[n]が記入されることがない場合も出てくる！
→while dp[n] == default値 { }の中で二重ループさせる
while dp[n] == std::usize::MAX {
for i in 0..n {
for c_i in c.iter() {
if i + c_i <= n && dp[i] < std::usize::MAX { // idx overflow への対策はifでやる
dp[i+c_i] = min(dp[i+c_i], dp[i] + 1);
}
}
}
}
数列問題は大体dp.
k列目までの答えをdpするなどするといい。
二つ数列があるならdp[][] になることが多い。
bit探索
選ぶ選ばない（Yes or Noで判断できるもの）を二進数で表して配列に格納する。
ｎを二進数表記に変換してそこのｂｉｔが存在するかどうかを比較するのでinputの情報を簡単に変換できる。２＾ｎ回for で回す
構造体…
| n人目of true | n-1人目of true | ... | 2人目 true | 1人目 true |
|---|---|---|---|---|
| n人目of false | n-1人目of false | ... | 2人目 false | 1人目 false |
#![allow(non_snake_case)]
#![allow(unused_imports)]
#![allow(dead_code)]
use proconio::*;
use std::collections::HashMap;
// https://atcoder.jp/contests/abc249/tasks/abc249_c
#[fastout]
fn main() {
input! {n:usize, k:usize}
let mut v:Vec<Vec<char>> = vec![];
for _ in 0..n {
input! {S:String}
v.push(S.chars().collect::<Vec<char>>());
}
let mut ans = 0;
for bit in 0..(1<<n) { //全パターン列挙して
let mut S_all: Vec<char> = vec![];
for i in 0..n { //各TorFに対して
if bit & (1<<i) == 0 { //処理をしていく
continue;
}else {
S_all.append(&mut v[i].clone());
}
}
let mut map = HashMap::new();
for s in S_all {
*map.entry(s).or_insert(0) += 1;
}
let res = map.values().filter(|&v| *v == k).count();
ans = std::cmp::max(ans, res);
}
println!("{}", ans);
}
再帰関数を用いて全通り調べ上げる手法を深さ優先探索（DFS）ということがあります。
二分探索；よく使うのはBTreeSet
use std::collections::BTreeMap;
↑二分探索のMapバージョン。（mapとはkey , val があるやつ）。
(公式サイトによるとimpl Hash for BTreeMap してるのでHash構造でデータを格納してる？)
BTreeMap/ BTreeSetは、キーについて昇順(小→大)でデータが格納されます
https://laysakura.github.io/2019/12/25/rust-DataStructures-Algorithm-BinarySearchTree/
Vecとの大きな差はremove(key)ができること。なのでBTreeSetでkeyをvalueとみなして使うといい。Vecはremoveでもインデックスしか指定できない。
探索時間は最大log(n)だが、大きい数順に探索するので大きい数をremoveするならほとんど時間はかからない。
BTreeSetは重複を許さない。（insertしても重複は一つにまとめられる）（Hashも同様）
対策としてtupleをkeyとして放り込むというのがある。
for i in 0..n {
bts.insert((x, i));
//iで何回目にぶち込んだかを明記することで重複を避ける
}
Hashmap
Hashのすごいところは任意の値のgetがO(1)であること。ただしメモリの消費量が大きい。
おなじみのハッシュテーブルです。キーと値をペアで記録してくれるもので、他の言語では連想配列や辞書型と呼ばれたりします。
https://qiita.com/garkimasera/items/a6df4d1cd99bc5010a5e#hashmap
hm.entry().or_insert()はセット。
.entry ... 引数のkeyに対するvalueを返す。そのvalueが存在しなければ.or_insert(val)のvalをそのキーに割り当てる
なので.or_insertはそのキーの初期値割り当てとなる。
一般的な例：
use std::collections::HashMap;
let mut map = HashMap::new();
map.insert("lisp", 1958);
map.insert("c", 1972);
map.insert("rust", 2006);
map.insert("rust", 2007);
for (i,j) in map.iter() {
println!("{}",i);
println!("{}",j);
}
//こうしてもrust(キー)が2007に更新されるだけで、
//(rust,2006)と共存するわけではないことに注意
.entry().or_insert()例：
#![allow(non_snake_case)]
#![allow(unused_imports)]
#![allow(dead_code)]
use std::{collections::HashMap, vec};
// https://atcoder.jp/contests/abc235/tasks/abc235_c
use proconio::*;
#[fastout]
fn main() {
input! {n:usize, q:usize}
input! {A:[usize;n]}
input! {XK: [(usize,usize);q]}
let mut m = HashMap::new();
for i in 0..n {
let count = m.entry(A[i]).or_insert(vec![]);
//entryで挿入。or_insert ではじめて挿入するときの処理
// or_insert(default)でdefault値を&mutで返す。
//https://keens.github.io/blog/2020/05/23/rustnohashmaphaentrygabenri/
count.push(i+1);
}
for (x,k) in XK.into_iter() {
if !m.contains_key(&x){
println!("{}", -1);
}else if k > m[&x].len() {
println!("{}", -1);
}else {
println!("{}", m[&x][k-1]);
}
}
}
ハッシュマップで要素がいくつあったかをカウントをする。
ここではS_allの要素をキーにしてvalにそのキーが何回出てきたかを格納してる。
let mut map = HashMap::new();
for s in S_all { //S_all : Vec<char>
*map.entry(s).or_insert(0) += 1;
}
let res = map.values().filter(|&v| *v == k).count();
よく使うのはHashSet
Hash系は同じキーを一つしか持たない点に注意。
hashset で要素を取り除くのは .take(&elem)
deque ... 両端からpop, push できるキュー
use std::collections::VecDeque;
let mut v = VecDeque::new();
v.push_front(2);
v.push_front(3);
v.push_front(5);
assert_eq!(v.pop_back(), Some(2));
assert_eq!(v.pop_back(), Some(3));
assert_eq!(v.pop_back(), Some(5));
assert_eq!(v.pop_back(), None);
dequeは
while let Some(t) = q.pop_front() {
for i in ...
と使うことがおおい
Heap , Priority Queue, Binary Heap
どれも同義。二分木でルートが最大値なので最大値をO（１）で取り出せる。
use std::collections::BinaryHeap;
.push
.pop 最大値を取り出す&&取り除く。
.peek ...最大値を確認するだけ。ドロップしないので＆で返される
https://doc.rust-lang.org/std/collections/binary_heap/struct.BinaryHeap.html#method.pop
https://maikiichan.hatenadiary.com/entry/2019/07/19/011505
if let で取り出してる
セグメント木（ヒープ構造）
（TODO: まだ理解していません…）
構築に[$ O(N)]かかる。
区間に対する[クエリ]に[$ O(logN)]の速さで処理できるやつ。
- 構築
- 更新
- 検索
が機能。
区間の〇〇を扱いたい時は使える。モノイド辺りだと使える
[* 親]…(i-1)/2
[* 子]…i2+1とi2+2
なので配列のサイズは 2 * ( [nよりも大きい、最小の 2^k ] )
e.g. n=20→32 (2^5) スカスカな配列をイメージ。
グラフ
graphの基本の考え方：
答えに沿った答え行列[[]]を作る（dpであることも多い） → g[[]]を作る → 辺をg.pushする
→ for any_node の for any隣接ノード に対して処理を描く （または, dfsの中で graph の for any隣接ノードに対して処理を描く）
たとえば答え行列が「頂点Xへの到達回数が偶奇回における、頂点kへの到達は何通りあるか。↓
dp[i][j][l]:=i回目の推移で現在jにいて、Xをl回(mod 2)通った場合の数,でDP. dp[0][S][0]から始めてdp[K][T][0]が答え
またはVecDequeで while let するやり方もある。
https://atcoder.jp/contests/abc138/submissions/30409675
while let Some(v) = queue.pop_front(){
for next in &graph[v]{
...
used[*next] = true;
queue.push_back(*next);
}
}
Discussion