bouzuya/sitemap-xml-writer の README のバッジを追加した。
rust-lang org や rust-cli org などにあるいくつかの crate を参考にして、 license と ci (GitHub Actions) のバッジを追加した。
https://github.com/bouzuya/sitemap-xml-writer/commit/17019afbb7ca9b9dcd08811697721e6bb2567cee
docs.rs のバッジのリンク先は https://docs.rs/crate/sitemap-xml-writer よりも https://docs.rs/sitemap-xml-writer のほうが良いかもとは思っている。
Feature Flags をモジュールのドキュメントに追加したり、エラーまわりを改善したらバージョンを上げようかな。他にやるべきことがあるので優先度は低い。
Corne Chocolate をつくっている。
ホワイトデーなのでクッキーを返した。
ABC073 : AtCoder Beginner Contest 073 の A, B, C, D を解いた。
- A - September 9
https://atcoder.jp/contests/abc073/tasks/abc073_a
- 提出: https://atcoder.jp/contests/abc073/submissions/39728810
n.to_string().contains('9')
- B - Theater
https://atcoder.jp/contests/abc073/tasks/abc073_b
- 提出: https://atcoder.jp/contests/abc073/submissions/39729054
- いもす法・累積和
- 単純に l_i から r_i まで加算を N 回やると間に合わない
- N 回の走査では l_i に +1, r_i+1 に -1 だけをしておく
- 最後にまとめて先頭から累積和を取れば最終的に座っているかが分かるし、間に合う
- あとはそれらの総和を取れば答えになる
- C - Write and Erase
https://atcoder.jp/contests/abc073/tasks/abc073_c
- 提出: https://atcoder.jp/contests/abc073/submissions/39729225
HashSet
を使う- 要素が含まれていれば remove 、含まれていなければ insert する
- 最終的な len が答えになる
- B より簡単では……
- D - joisino's travel
https://atcoder.jp/contests/abc073/tasks/abc073_d
- 提出: https://atcoder.jp/contests/abc073/submissions/39729471
- 全点対最短経路・ next_permutation
- 個数が少ないので全点対最短経路を求められる、事前に求めておく
- 各頂点からダイクストラ法などを使うか、ワーシャルフロイド法を使う
- r の順番を next_permutation ですべて試す
- 各順番では事前に求めておいた経路の総和を求める
use proconio::{input, marker::Usize1}; use superslice::Ext; fn dijkstra(n: usize, inf: usize, edges: &[Vec<(usize, usize)>], s: usize) -> Vec<usize> { use std::{cmp::Reverse, collections::BinaryHeap}; let mut d = vec![inf; n]; let mut pq = BinaryHeap::new(); d[s] = 0; pq.push(Reverse((0, s))); while let Some(Reverse((w_u, u))) = pq.pop() { if w_u > d[u] { continue; } for (v, w_v) in edges[u].iter().copied() { let w = w_u + w_v; if w < d[v] { d[v] = w; pq.push(Reverse((w, v))); } } } d } fn main() { input! { capital_n: usize, capital_m: usize, capital_r: usize, mut r: [Usize1; capital_r], abc: [(Usize1, Usize1, usize); capital_m], }; let mut edges = vec![vec![]; capital_n]; for (a, b, c) in abc.iter().copied() { edges[a].push((b, c)); edges[b].push((a, c)); } let inf = 1_usize << 60; let mut dist = vec![]; for u in 0..capital_n { dist.push(dijkstra(capital_n, inf, &edges, u)); } let mut min = 1_usize << 60; r.sort(); loop { let mut sum = 0_usize; let mut prev = r[0]; for next in r.iter().copied().skip(1) { sum += dist[prev][next]; prev = next; } min = min.min(sum); if !r.next_permutation() { break; } } let ans = min; println!("{}", ans); }
今日のコミット。
- rust-sandbox 2 commits
- rust-atcoder 1 commit
- sitemap-xml-writer 1 commit