2022-03-28 ABC245 E - Wrapping Chocolate を解いた

ABC245: AtCoder Beginner Contest 245 E - Wrapping Chocolate を解いた。

本番では解けなかった。解けそうで解けなかった。解けると思って D を飛ばしたらひどくハマって解けなかった。 D を解かなかったせいで緑になった。

さて。本番で考えたことを書く。

縦と横のふたつの軸がある。こういうときはどちらか一方でソートして扱うとそちらを考慮しなくて良くなる。チョコレート・箱を共に縦で昇順に並べることを考えた。この順序でチョコレートを走査する。あるチョコレートの縦よりも大きいもののうち最小の横幅を選べば良さそうだ。どうやって……？

解説によるとチョコレート・箱を合わせて縦の降順・箱→チョコレートの順で並べる。箱のとき順序集合に横幅を入れてチョコレートのとき順序集合から最小のものを取り出す。取り出せなければ No 。すべての要素を操作できれば Yes 。

注意すべきは BTreeSet にしてしまうと同じ横幅の箱が 2 つあったときに困るので BTreeMap にして個数を保持した。

見落としていた点は「横をキーとした順序集合を用意する (縦の降順にソートしてあるのでそれで十分で両方は要らない)」「対象外のものを選択肢 (順序集合) に含めないこと」だろう。

体調が悪くノルマなどはこなしたもののほとんど一日寝ていた。

今日のコミット。