2022-03-12 ABC243 に参加した
ABC243 : AtCoder Beginner Contest 243 に参加した。レーティング +20 だった。 D までの早解きになってしまった……。 E はワーシャルフロイドっぽい判定で……とは思ったのだけど解けなかった。前にもワーシャルフロイドの動きをすこし触るような問題を解けなかった記憶がある。
https://atcoder.jp/users/bouzuya/history/share/abc243
アルゴリズムと数学 演習問題集 081 - Bill Changing Problem を解いた。
問題: https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bm
10000, 5000, 1000 の順に貪欲に使えるだけ使っていく。余りを次の紙幣の入力に使う。
貪欲法で良いかどうかの判断はよく知らない。
提出: https://atcoder.jp/contests/math-and-algorithm/submissions/30015371
アルゴリズムと数学 演習問題集 082 - Interval Scheduling Problem を解いた。
問題: https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bn
区間スケジューリング問題。典型。区間の後ろでソートして貪欲法で良い。区間の後ろをできるだけ前にしておけばそれ以降で選択可能なものが増えるので最適になる……という理解でいる。
提出: https://atcoder.jp/contests/math-and-algorithm/submissions/30015436
アルゴリズムと数学 演習問題集 083 - We Used to Sing a Song Together（★3） を解いた。
問題: https://atcoder.jp/contests/math-and-algorithm/tasks/typical90_n
競プロ典型 90 問の 14 問目 (https://atcoder.jp/contests/typical90/tasks/typical90_n) と同じ問題だ。
小学校・小学生をそれぞれ位置の昇順に並べて考える。小学校・小学生を交差して対応づけている場合は交差しないようにするほうがそれ以下にできる……はず。つまり昇順に並べて前から順に対応付ければ良い。
提出: https://atcoder.jp/contests/math-and-algorithm/submissions/30015458 解説: https://twitter.com/e869120/status/1382478816627478530
子どもと買い物に行った。ぽかぽかと暖かい日だった。
今日のコミット。