2022-04-19 ABC116 A, B, C, D を解いた
ABC116 A, B, C, D を解いた。
- A - Right Triangle
- 問題: https://atcoder.jp/contests/abc116/tasks/abc116_a
- 提出: https://atcoder.jp/contests/abc116/submissions/31101924
|AB| * |BC| / 2で良い- 面積 (答え) が整数になるという制約があるので
/ 2の切り捨てもたぶん問題にならない
- B - Collatz Problem
- 問題: https://atcoder.jp/contests/abc116/tasks/abc116_b
- 提出: https://atcoder.jp/contests/abc116/submissions/31102065
- 指示通りにシミュレートする
m <= 10^6という制約があるので set で重複を見れば良い
- C - Grand Garden
- 問題: https://atcoder.jp/contests/abc116/tasks/abc116_c
- 提出: https://atcoder.jp/contests/abc116/submissions/31102203
- 1 回でできるだけ広く取りたい→行で考える
- 第一印象では
Nが小さいので一番下の段から順に走査しても間に合いそう……愚直すぎるのでやめた - 凸の部分は追加で回数が必要なので山を登るときに登った分だけ回数を追加し、凹の部分では増やさず基準値だけを下げる、これを繰り返すと最小回数になる (未証明)
- D - Various Sushi
- 問題: https://atcoder.jp/contests/abc116/tasks/abc116_d
- 提出: https://atcoder.jp/contests/abc116/submissions/31102717
- 解説 AC
- 解けそうで解けないライン
- おいしさの降順で並べて先頭から K 取る
- そのときのネタの種類数を x とすると x 種類での最大値になっている
- 種類数ごとの最大値を考えたとき種類を減らしてもこれより良くなることはない
- 種類を減らさずおいしさの小さいものを削除して、種類を増やせるおいしさの大きいものを追加する
- これを繰り返したときの満足ポイントの最大値が答えになる
- 各種類につき 2 個目以降を BinaryHeap に入れておいしさの昇順で取り出せば、種類を減らさずおいしさの小さいものを取り出せる
- 各種類の Set を持っておき、おいしさの降順に走査して種類が増えたときに満足ポイントを計算する
sqlx 0.5.11 で修正されたこの Issue の問題をおそらく踏んだ。 Any で None を bind すると bind されずにスキップされる。
https://github.com/launchbadge/sqlx/pull/1661
検証のために bouzuya/rust-examples で試していたのだけどそちらは 0.5.11 になっていたので再現しなくて混乱した。検証はバージョンをきちんと合わせような。
今日のコミット。
- rust-examples 2 commits
- rust-atcoder 1 commit
- rust-sandbox 1 commit