freee プログラミングコンテスト2023（AtCoder Beginner Contest 310）をPythonで解く

こんにちは, Shinoryoです.

今回はfreee プログラミングコンテスト2023（AtCoder Beginner Contest 310）を, Pythonで解いてみた結果を書き連ねていこうと思います.

freee Programming Contest 2023（AtCoder Beginner Contest 310） - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

A - Order Something Else

AtCoderドリンクの値段は, 次の2パターンです.

• 割引券を使わなかった場合：$P$円
• 割引券を使った場合：$Q + \min_{i = 1, \ldots, N} D_i$円

したがって, それらのうち安い方を出力すればよいです.

B - Strictly Superior

全ての$i$, $j$の組み合わせに対して, 一方が一方の上位互換になっているかを確かめればよいです. 下記の例のようにset()を使うと高速ですが, list()を使っても十分ACできると思います.

C - Reversible

棒を順番に見ていき, 今までに見たどの棒とも同じでない棒を見るたびにカウンタの値を$1$増やすことで, そのカウンタが答えになります.

「今までに見たどの棒とも同じでない棒」であるかを判断するには, 今までに見た棒を記録しておけば良いです. list()で格納してしまうと全体の計算量が$O(N^2)$となりTLEですが, set()で格納すれば全体の計算量が$O(N)$となりACです.

D - Peaceful Teams

順番に選手をチームに加えていく, またはその選手だけで新たなチームを作るということを順に行っていくことで, 全探索すればよいです. うまくset()を使うことで高速化できます.

E以降

E以降は私の能力不足故に省略いたします.

参考にしたサイト等

• 「解説 - freee プログラミングコンテスト2023（AtCoder Beginner Contest 310）」
  Editorial - freee Programming Contest 2023（AtCoder Beginner Contest 310）

  AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

• nkmk様による「Python, set型で集合演算（和集合, 積集合や部分集合の判定など）」
  Python, set型で集合演算（和集合, 積集合や部分集合の判定など） | note.nkmk.me

  Pythonでは, 集合を表すset型が組み込みのデータ型として提供されている. 集合setは重複しない要素（同じ 値ではない要素, ユニークな要素）のコレクションで, 和集合・差集合・積集合などの集合演算を行うことができる. 組み込み型 - set（集 合）型 — Python 3.11.4 ドキュメント setオブジェクトを生成: {}, 集合内包表記...