ABC037 : AtCoder Beginner Contest 037 の A, B, C, D を解いた。
- A - 饅頭
https://atcoder.jp/contests/abc037/tasks/abc037_a
- 提出: https://atcoder.jp/contests/abc037/submissions/37982166
c / a.min(b)
- B - 編集
https://atcoder.jp/contests/abc037/tasks/abc037_b
- 提出: https://atcoder.jp/contests/abc037/submissions/37982235
N, Q <= 100
なので問題文通りにシミュレーションすれば良い
- C - 総和
https://atcoder.jp/contests/abc037/tasks/abc037_c
- 提出: https://atcoder.jp/contests/abc037/submissions/37982274
- 連続する部分列を都度計算すると
O(N^2)
になるので部分点しか取れない - 連続する部分列なので右端に追加して左端を削除すれば
O(1)
で次の連続する部分列が求められるので全体でO(N)
(O(N+K)
?)
- D - 経路
https://atcoder.jp/contests/abc037/tasks/abc037_d
- 提出: https://atcoder.jp/contests/abc037/submissions/37982532
- 各マスにはそこから開始する 1 経路がある
- 最も大きな整数の書かれたマスはそこから開始する経路以外は存在しない (1 確定)
- そのマスに隣接するそのマスの整数よりも小さいマスから遷移できる
- 遷移元になりえる隣接マスからの経路には、遷移先の経路数が加えられる
- 同様に大きい整数から順に遷移元になりえる隣接マスへ経路数を配る形で加算していけば良い
- 計算する順序を書かれている整数の降順にする DP
use std::collections::BinaryHeap; use proconio::{input, marker::Usize1}; fn main() { input! { h: usize, w: usize, a: [[usize; w]; h], }; let mut pq = BinaryHeap::new(); for i in 0..h { for j in 0..w { pq.push((a[i][j], i, j)); } } let mut dp = vec![vec![1_usize; w]; h]; while let Some((_, i, j)) = pq.pop() { 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 a[nr][nc] >= a[i][j] { continue; } dp[nr][nc] += dp[i][j]; dp[nr][nc] %= 1_000_000_007; } } let mut ans = 0_usize; for i in 0..h { for j in 0..w { ans += dp[i][j]; ans %= 1_000_000_007; } } println!("{}", ans); }
今日のコミット。
- rust-sandbox 8 commits
- rust-atcoder 1 commit