2022-04-27 EDPC F, G, H を解いた
EDPC : Educational DP Contest F, G, H を解いた。
- F - LCS
https://atcoder.jp/contests/dp/tasks/dp_f
- 提出: https://atcoder.jp/contests/dp/submissions/31304505
- LCS: Longest Common Subsequence (最長共通部分列)
- ド典型だけど急に難しい
dp[i][j] := s の i 番目の文字までと t の j 番目の文字まででできる LCS の長さ- 遷移は
s[i] == t[j]ならdp[i - 1][j - 1] + 1でs[i] != t[j]ならMAX(dp[i - 1][j], dp[i][j - 1]) - 長さを求めたあと最長共通部分列を復元する
- 2020-06-24
- G - Longest Path
https://atcoder.jp/contests/dp/tasks/dp_g
- 提出: https://atcoder.jp/contests/dp/submissions/31304712
- 出次数 0 の頂点 (終端) から逆向きにたどって終端からの距離を記録して最大の距離が答えになる
- キューを用意して出次数 0 の頂点をエンキューする
- デキューしてその頂点へ入ってくる辺をたどる
- たどった辺は除去 (たどった先の頂点の出次数を減ら) して出次数 0 ならその頂点をエンキューして距離 (現在の頂点までの距離 +1) を記録する
- これを最後まで繰り返したあとすべての頂点の終端からの距離の最大値を求める
- 2020-07-04
- H - Grid 1
https://atcoder.jp/contests/dp/tasks/dp_h
- 提出: https://atcoder.jp/contests/dp/submissions/31304900
- 各マスの場合の数を求める
0で初期化したあと(1,1)を1として各行・各列について右と下に加算する(h,w)に答えが求められる- 2020-07-04
下の子の熱で休み。子どもの熱は 39 ℃とか平気で出るのがすごい。
今日のコミット。
- rust-atcoder 1 commit
- rust-sandbox 2 commits