ABC077 : AtCoder Beginner Contest 077 の A, B, C, D を解いた。
- A - Rotation
https://atcoder.jp/contests/abc077/tasks/abc077_a
- 提出: https://atcoder.jp/contests/abc077/submissions/39820679
- 走査順序を工夫してなんとかする
- B - Around Square
https://atcoder.jp/contests/abc077/tasks/abc077_b
- 提出: https://atcoder.jp/contests/abc077/submissions/39820716
x * x > n
になるまで試して、そこまでの最大値が答えになるN >= 10^9
だけどx * x
なので問題ない
- C - Snuke Festival
https://atcoder.jp/contests/abc077/tasks/arc084_a
- 提出: https://atcoder.jp/contests/abc077/submissions/39820911
- 真ん中を固定
- A, B, C をソートして、 B を走査して、 A から B - 1 以下の個数、 C から B + 1 以上の個数を二分探索で数えて、かけ合わせれば良い
- こういう真ん中を固定するのよくある
- D - Small Multiple
https://atcoder.jp/contests/abc077/tasks/arc084_b
- 提出: https://atcoder.jp/contests/abc077/submissions/39822644
- 解説 AC
- 01BFS をバグらせて 5WA
use std::collections::VecDeque; use proconio::input; fn main() { input! { k: usize, }; let mut edges = vec![vec![]; k]; for i in 0..k { edges[i].push(((i + 1) % k, 1)); edges[i].push(((i * 10) % k, 0)); } let inf = 1_usize << 60; let mut dist = vec![inf; k]; let mut deque = VecDeque::new(); deque.push_back((1, 0)); dist[1] = 0; while let Some((u, d_u)) = deque.pop_front() { if u == 0 { break; } for (v, w_v) in edges[u].iter().copied() { let d_v = d_u + w_v; if d_v >= dist[v] { continue; } dist[v] = d_v; match w_v { 0 => deque.push_front((v, d_v)), 1 => deque.push_back((v, d_v)), _ => unreachable!(), } } } let ans = dist[0] + 1; println!("{}", ans); }
今日のコミット。