Rust에서 시합 프로그래밍을 시작하는 사람을 위해 데이터 구조를 소개하다

Rust의 컬렉션(Vec 및 HashMap 등) - Qita
먼저 위의 사이트를 보십시오.

수색하다

https://qiita.com/e869120/items/25cb52ba47be0fd418d6#언니 문제 탐색 알고리즘 배우기
탐색 알고리즘의 깊이
간단한 for 순환만 돌려서 쓸 수 없습니다.어떻게 전체 검색을 실현할 것인가, 더욱 효율적인 검색 알고리즘이 존재하는가
일반적으로 컴퓨터는 1초에 10^8~10^9번 정도 계산할 수 있다

DP

기본적으로 점화식과 초기값(i=0시)을 주면 DP 배열은 모든 인덱스 업데이트를 전제로 한다.(이렇게 점차적인 코드를 쓴다)
“””
bool dp[][];
i번 j는 ~시의 T/F입니다.
“””
잠깐만요. 예예요.
dp의value 형식은 출력에 맞춰야 합니다.

bit 탐색

선택하지 않은(Yes 또는 No로 판단된) 바이너리 표현을 배열에 저장합니다.
n을 2진법으로 변환하면 그곳의bit가 존재하는지 비교하기 때문에 input의 정보를 간단하게 변환할 수 있습니다.for에서 2^n회 회전
구조체...
n번째 비밀
n-1 첫 번째 사람 of 진짜
...
두 번째 사람 진짜.
첫 번째 사람이 진짜.
n인의 가짜
n-1 1인 of 가짜
...
두 번째 거짓
첫 번째 거짓
주제 밖의 말:bit라고 해도 이차원 배열에 대해 아무것도 할 수 없는 것은 아니다.일차원적이면 좋겠다.

using namespace std;

int N, X, A[22];
bool flag = false;

int main() {
    cin >> N >> X;
    for (int i = 1; i <= N; i++) cin >> A[i];
    for (int i = 0; i < (1 << N); i++) {
        int bit[30], sum = 0;
        for (int j = 0; j < N; j++) {
            int Div = (1 << j);
            bit[j] = (i / Div) % 2;
        }
        for (int j = 0; j < N; j++) sum += A[j] * bit[j];
        if (sum == X) flag = true;
    }
    if (flag == true) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

<<는 두 배를 나타냅니다.(왼쪽으로 이동)

2분 탐색;BTreeSet을 많이 사용해요.

use std::collections::BTreeMap;↑ 2분 탐색의 맵 버전.(키, val 있는 녀석)BTreeMap/BTreeSet에서 키를 눌러 오름차순으로 데이터를 저장하는 정보
https://laysakura.github.io/2019/12/25/rust-DataStructures-Algorithm-BinarySearchTree/
Vec와 큰 차이가 있는데 리모브가 된다는 거예요.따라서 BTreset에서 키를value로 사용하는 것이 좋습니다.Vec는 remove에서도 색인만 지정할 수 있습니다.
검색 시간은 최대log(n)이지만 큰 순서로 검색하기 때문에remove가 큰 숫자는 시간이 거의 필요 없습니다.
BTreeSet에서는 중복을 허용하지 않습니다.(insert도 중복을 하나로 정리할 수 있음) (Hash도 마찬가지)
대책으로 투플을 키로 넣었습니다.

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 ... 매개 변수 키의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]);
        }
    }
}

자주 쓰는 건 HashSet입니다.

해시계 열쇠가 하나밖에 없으니까 조심해.
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);

Heap , Priority Queue, Binary Heap

어느 것이든 동의어이다.이분수이기 때문에 가장 큰 노선은 O(1)이기 때문에 최대치를 꺼낼 수 있다.use std::collections::BinaryHeap;.push
최대 팝 값을 추출하고 제거합니다.
.peek ...최대치만 확인하면 됩니다.드래그하지 않기 때문에 & 되돌아오기
https://doc.rust-lang.org/std/collections/binary_heap/struct.BinaryHeap.html#method.pop
https://maikiichan.hatenadiary.com/entry/2019/07/19/011505 비공식iflet으로 제거
희망이 가장 큰 것이 아니라 가장 작은 것이다.Reverse 함수 사용

use std::{cmp::Reverse, collections::BinaryHeap};

fn main() {
    let mut a: BinaryHeap<_> = vec![1, 2, 3].into_iter().collect();
    if let Some(v) = a.pop() {
        println!("Next is {}", v);
    }

    let mut b: BinaryHeap<_> = vec![1, 2, 3].into_iter().map(Reverse).collect();
    if let Some(Reverse(v)) = b.pop() {
        println!("Next is {}", v);
    }
}

つまりは、以下のように
//値を `Reverse`でラップします
heap.push(Reverse(1));
heap.push(Reverse(5));
heap.push(Reverse(2));

//これらのスコアを今ポップすると、逆の順序で戻ってくるはずです。
assert_eq!(heap.pop(), Some(Reverse(1)));
assert_eq!(heap.pop(), Some(Reverse(2)));
assert_eq!(heap.pop(), Some(Reverse(5)));

다이어그램

graph의 줄기:
정답에 따라 답변 매트릭스[]-제작 g[]→변 g.push
→ for any_노드의 for와 y가 인접한 노드에 대한 처리를 묘사합니다 (OR, dfs에서graph의 for와 y가 인접한 노드에 대한 처리를 묘사합니다)
예를 들어 응답 대기열에 있는'X는 짝짓기에서 정점에 도달하는 k는 몇 개?↓
i차 추이에서 현재 j에서 X회(mod2)를 통과할 때의 수량을 계산하고 DP를 계산합니다.처음으로 dp[K][T][0]가 나왔습니다.

use proconio::input;
use proconio::marker::*;
use std::collections::*;
use std::cmp::*;

// https://atcoder.jp/contests/abc244/tasks/abc244_e
// 以下の条件を満たす数列 A=(A0, .., Ak) は何通りありますか？

/* 
アライグマ「E問題は要するに「頂点SからTへ、ちょうどK回で移動する方法のうち、頂点Xを偶数回通るものは何通り？」なのだ！
dp[n][v][f]=Sからn回移動して頂点vにいて、Xを通った回数の偶奇がfの移動方法の数
とすればO(K(N+M))で解けるのだ！」
dp[i][j][l]:=i回目の推移で現在jにいてXをl回(mod 2)通った場合の数,でDP. dp[0][S][0]から初めてdp[K][T][0]が答え

graphの根幹:
答えに沿った答え行列[[]]を作る（dpであることも多い） → g[[]]を作る → 辺をg.pushする 
→ for any_node の for any隣接ノード に対して処理を描く || dfsの中で graph の for any隣接ノードに対して処理を描く
今回の答え行列は「Xが偶奇回における。頂点kへの到達は何通りあるか。」
*/

const MOD:usize = 998244353;
fn main() {
  input! {
    n:usize,
    m:usize,
    k:usize,
    s:Usize1,
    t:Usize1,
    x:Usize1,
    edges:[(Usize1,Usize1);m]
  }
 
  let mut g = vec![vec![];n]; //グラフは 2 dim
  for (a, b) in edges {
    g[a].push(b);
    g[b].push(a); // 無向グラフ
  }
 
  let mut memo = vec![vec![0;n+1];2]; //all 0, Xが偶奇回における。頂点kへの到達は何通りあるか。
  memo[0][s] = 1usize;
 
  for _ in 0..k {
    let mut new_memo = vec![vec![0;n+1];2];
    for ci in 0..n {//any 全頂点に対して
      for &ni in &g[ci] { //any その頂点に接続している頂点
        if ni == x { //問題文：xが偶数個という制約より, aはXを通った回数の偶奇
          for a in 0..2 {
            let nni = (a+1) % 2;//0→１、1→0
            new_memo[nni][ni] += memo[a][ci]; //ci→ni。niがXだったのでXは偶数になる。
            new_memo[nni][ni] %= MOD;
          }
        } else {
          for a in 0..2 {
            new_memo[a][ni] += memo[a][ci];//Xが奇数回を更新。niはXじゃなかったから。
            new_memo[a][ni] %= MOD;
          }
        }
      }
    }
    memo = new_memo;
  }
 
  println!("{}", memo[0][t]);  //Xが偶数回 && T
}

Usize 1에는 0의 usize가 없습니다.