2023-02-08 ABC088 の A, B, C, D を解いた
ABC088 : AtCoder Beginner Contest 088 の A, B, C, D を解いた。
- A - Infinite Coins
https://atcoder.jp/contests/abc088/tasks/abc088_a
- 提出: https://atcoder.jp/contests/abc088/submissions/38715960
n % 500 <= a
- B - Card Game for Two
https://atcoder.jp/contests/abc088/tasks/abc088_b
- 提出: https://atcoder.jp/contests/abc088/submissions/38716266
- a を降順にソートして偶数番目を alice 側、奇数番目を bob 側に加算しておく
- 最後に alice - bob をとれば良い
- C - Takahashi's Information
https://atcoder.jp/contests/abc088/tasks/abc088_c
- 提出: https://atcoder.jp/contests/abc088/submissions/38716788
- a_1, a_2, a_3, b_1, b_2, b_3 を全探索すると間に合わない
- a_1 を決めると b_1, b_2, b_3 も c 経由で一意に定まる
- それらの組み合わせのうち c と突き合わせて矛盾しないものがあれば Yes
- D - Grid Repainting
https://atcoder.jp/contests/abc088/tasks/abc088_d
- 提出: https://atcoder.jp/contests/abc088/submissions/38717068
- 幅優先探索で最短距離を求める
- (H,W) に到達できない場合は -1
- 到達できる場合は最短距離が最低限必要な
'.'
の数になる - 盤面全体の
'.'
の数から最短距離を除いた数が'.'
から'#'
に変換可能な個数になる
use std::collections::VecDeque;
use proconio::{input, marker::Chars};
fn main() {
input! {
h: usize,
w: usize,
s: [Chars; h],
};
let inf = h * w + 1;
let mut dist = vec![vec![inf; w]; h];
let mut deque = VecDeque::new();
dist[0][0] = 0;
deque.push_back((0, 0));
while let Some((i, j)) = deque.pop_front() {
let dir = vec![(-1, 0), (0, -1), (0, 1), (1, 0)];
for (dr, dc) in dir {
let (nr, nc) = (i as i64 + dr, j as i64 + dc);
if !(0..h as i64).contains(&nr) || !(0..w as i64).contains(&nc) {
continue;
}
let (nr, nc) = (nr as usize, nc as usize);
if s[nr][nc] != '.' {
continue;
}
if dist[nr][nc] != inf {
continue;
}
dist[nr][nc] = dist[i][j] + 1;
deque.push_back((nr, nc));
}
}
let d = dist[h - 1][w - 1];
if d == inf {
println!("-1");
return;
}
let d = d + 1;
let mut count = 0_usize;
for i in 0..h {
for j in 0..w {
if s[i][j] == '.' {
count += 1;
}
}
}
let ans = count - d;
println!("{}", ans);
}
bouzuya/rust-sandbox の bbn コマンドで https://blog.bouzuya.net/sitemap.xml
と意味的に同じものが出力できるようになった。
今日のコミット。
- rust-sandbox 1 commit
- rust-atcoder 1 commit