Drawer を追加しようとして expo-router に嫌気がさしたので react-navigation に移行しようとしている。
- 編集距離 (オリジナル問題)
https://atcoder.jp/contests/pastbook2022/tasks/pastbook2022_b
- https://atcoder.jp/contests/pastbook2022/submissions/42222290
- 解説 AC
- 過去にも解いたことがあるはずの問題なのに自力で解けない
- 問題の位置付けから O(NM) になるのは見えた
dp[0][0] = 0
も分かる- 遷移にいまひとつ自信が持てず
=m
や=n
の範囲もうまく出てこなさそう
use proconio::{input, marker::Chars}; macro_rules! chmin { ($min_v: expr, $v: expr) => { if $v < $min_v { $min_v = $v; true } else { false } }; } fn main() { input! { m: usize, n: usize, s: Chars, t: Chars, } let inf = n * m + 1; let mut dp = vec![vec![inf; n + 1]; m + 1]; dp[0][0] = 0_usize; for i in 0..=m { for j in 0..=n { if i > 0 && j > 0 { chmin!( dp[i][j], dp[i - 1][j - 1] + if s[i - 1] == t[j - 1] { 0 } else { 1 } ); } if i > 0 { chmin!(dp[i][j], dp[i - 1][j] + 1); } if j > 0 { chmin!(dp[i][j], dp[i][j - 1] + 1); } } } let ans = dp[m][n]; println!("{}", ans); }
今日のコミット。
- tsukota 1 commit
- rust-atcoder 1 commit