2023-12-20 bouzuya/firestore-path を改善 / ABC330 E

bouzuya/firestore-path に↓の変更を追加した。

DocumentName::collection_id を追加
DocumentPath::collection_id を追加
DocumentName::collection を TryInto<CollectionId> から TryInto<CollectionPath> に変更
DocumentPath::collection を TryInto<CollectionId> から TryInto<CollectionPath> に変更

DocumentPath::collection_id (DocumentName も同様) はそのドキュメントの親となるコレクションの ID だと直感的に分かるので追加することにした。これは createDocumentRequest を組み立てる際に collection_id を組み立てるのが面倒なことで気づいた。

https://firebase.google.com/docs/firestore/reference/rpc/google.firestore.v1?hl=ja#google.firestore.v1.CreateDocumentRequest

あと DocumentPath::collection (DocumentName も同様) で TryInto<CollectionId> を取っていたがこれだと一階層ずつ作ることになり面倒なので TryInto<CollectionPath> にして複数階層をまとめて作れるようにした。↓のような指定ができる。

DocumentPath::from_str("chatrooms/chatroom1")?.collection("messages/message1/col")?

dependabot の対応で bouzuya/serde-firestore-value を 0.2.2 にした。

ABC330 トヨタシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 330)

E - Mex and Update https://atcoder.jp/contests/abc330/tasks/abc330_e
- 提出: https://atcoder.jp/contests/abc330/submissions/48679058
- 毎回 mex を調べると間に合わない
- N,Q <= 2*10^5 なので 0 から順に設定されたとしても mex は 2*10^5 にしかならない (それを超える A_i は無視しても良い)
- 0..=2*100_000 で未使用の数字を BTreeSet で保持しておき、使用するごとに消す
- 使用済みの数字が未使用になったかを判断するために使用済みの数字の個数を HashMap で保持する
- BTreeSet の先頭要素 (mex) は O(logN) で見つけられるので間に合う

use std::collections::{BTreeSet, HashMap};

use proconio::{input, marker::Usize1};

fn main() {
    input! {
        n: usize,
        q: usize,
        mut a: [usize; n],
        ix: [(Usize1, usize); q]
    };

    let mut used = HashMap::new();
    let mut unused = (0..=2 * 100_000).collect::<BTreeSet<usize>>();
    for a_i in a.iter().copied() {
        *used.entry(a_i).or_insert(0) += 1;
        unused.remove(&a_i);
    }

    for (i, x) in ix {
        let count = used.get_mut(&a[i]).unwrap();
        *count -= 1;
        if *count == 0 {
            used.remove(&a[i]);
            unused.insert(a[i]);
        }

        a[i] = x;
        *used.entry(x).or_insert(0) += 1;
        unused.remove(&x);

        let mex = unused.iter().next().unwrap();
        println!("{}", mex);
    }
}

今日のコミット。