🦀

Rustで競技プログラミングを始めた人のためのデータ構造紹介とノウハウ書き留め

2022/03/27に公開

もともと自分のメモとして書いていたのですが、始める人の参考になればと思い公開しておきます。

データ構造の原理、基本は知っているものとみなします。

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で判断できるもの)を二進数で表して配列に格納する。

nを二進数表記に変換してそこのbitが存在するかどうかを比較するのでinputの情報を簡単に変換できる。2^n回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構造でデータを格納してる?)

BTreeMapBTreeSetは、キーについて昇順(小→大)でデータが格納されます”

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(1)で取り出せる。

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