2022-01-15 第八回アルゴリズム実技検定 (PAST) E - カラフルなTシャツを解いた

第八回アルゴリズム実技検定 (PAST) E - カラフルなTシャツを解いた。

色ごとに最も安いもの以外は買う必要がない。価格の安い色を K 種類買えば良い。 K 種類に満たないときは -1 になる。

ぼくは色と価格を Tuple にして価格で昇順にソートして走査し、一度選んだ色は Set に追加して既に選んでいないか、 K 個を超えていないかを確認することで解いた。

ソートと Set への挿入を伴う走査はどちらも O(NlogN) なので全体としては O(NlogN) で間に合う。

先に色ごとの最小値を求める方法でも解いてみた。色ごとの最低価格を保持する Map を用意する。価格の昇順で先頭から K 個の合計を求めると良い。 K 種類の色がないときに -1 を返すことを忘れないように注意する。

ABC235 に参加した。 D は冷静にやれば解けそうだった。

今日のコミット。