2024-02-01 bouzuya/firestore-structured-query 0.4.0 / 休憩と洗い物 / ABC218 F
bouzuya/firestore-structured-query 0.4.0 をつくった。
StructuredQuery の構築をできるようにした。おおむねインタフェースはできた。あとはエラーまわりやドキュメントを詰めて、 field_path に .
を含むケースとかに対応すれば終わりかな……。
start_at と start_after, end_at と end_before の挙動に自信がないので実際に emulator などで動かしても良さそう。 Firebase JS SDK に合わせているはずだけど。
休憩を多めに取っている。きっかけが洗い物が片付いていないことに気づいたこと。普段だと休憩のタイミングで食洗機を動かしているのに、それが欠けていることに気づいた。なんか疲れるなとかいまひとつ効率が上がらないなと思っていたのだけど、休憩をうまく取れていなかったように思う。
ABC218 : AtCoder Beginner Contest 218
- F - Blocked Roads
https://atcoder.jp/contests/abc218/tasks/abc218_f
- 提出: https://atcoder.jp/contests/abc218/submissions/49867565
N <= 400
と小さいのでN^3
近くなっても間に合う- 最短経路を求めて経路上の辺を set で保持して含まれているかを見る
- すべて含まれていたとしても N 回程度なので間に合う
- 初期状態で到達できない場合に -1 を 1 回しか出力していなくて 2WA
use std::{
cmp::Reverse,
collections::{BinaryHeap, HashSet},
};
use proconio::{input, marker::Usize1};
fn main() {
input! {
n: usize,
m: usize,
st: [(Usize1, Usize1); m]
};
let mut edges = vec![vec![]; n];
for (i, (s, t)) in st.into_iter().enumerate() {
edges[s].push((t, i));
}
let inf = 1_usize << 60;
let mut dist = vec![(inf, n, n); n];
dist[0] = (0_usize, 0_usize, m);
let mut pq = BinaryHeap::new();
pq.push((Reverse(0), 0));
while let Some((Reverse(d), u)) = pq.pop() {
if d > dist[u].0 {
continue;
}
for (v, i) in edges[u].iter().copied() {
let next = (dist[u].0 + 1, u, i);
if next.0 < dist[v].0 {
dist[v] = next;
pq.push((Reverse(next.0), v));
}
}
}
if dist[n - 1].0 == inf {
for _ in 0..m {
println!("-1");
}
return;
}
let mut set = HashSet::new();
let mut cur = n - 1;
while dist[cur].1 != cur {
set.insert(dist[cur].2);
cur = dist[cur].1;
}
for i in 0..m {
if set.contains(&i) {
let mut dist2 = vec![inf; n];
dist2[0] = 0_usize;
let mut pq = BinaryHeap::new();
pq.push((Reverse(0), 0));
while let Some((Reverse(d), u)) = pq.pop() {
if d > dist2[u] {
continue;
}
for (v, j) in edges[u].iter().copied() {
if i == j {
continue;
}
let next = (d + 1, v);
if next.0 < dist2[v] {
dist2[v] = next.0;
pq.push((Reverse(next.0), next.1));
}
}
}
if dist2[n - 1] == inf {
println!("-1");
} else {
println!("{}", dist2[n - 1]);
}
} else {
println!("{}", dist[n - 1].0);
}
}
}
今日のコミット。
- rust-atcoder 1 commit
- firestore-structured-query 17 commits
- 0.4.0
- Fix description
- Add ::to_value
- Fix tests
- Add Query::limit
- Add Query::offset
- Add Query::end_at
- Add Query::end_before
- Add Query::start_after
- Add Query::start_at
- Improve README example
- Add Query::select
- Add impl From
for FieldReference - Add Query::order_by
- Add Query::r#where
- Add Query::collection
- Add Query::collection_group
- blog.bouzuya.net 1 commit