トヨタ自動車プログラミングコンテスト2024#12（AtCoder Beginner Contest 384） のB問題〜D問題をPythonで解説します。
提出コード
B問題
問題
画像の文字起こし
Div.1とDiv.2があります。
それぞれのコンテストにはレートの更新範囲があります。
Div.1の更新範囲は1600～2799です。
Div.2の更新範囲は1200～2399です。
参加したコンテストと、増レート数が与えられます。
現在のレートがコンテストの更新範囲ならレートを更新して、最終的なレートを出力してください。
アプローチ
画像の文字起こし
forとifで実装できます。
Dで条件分岐して、レートの更新範囲なら、レートに足します。
C問題
問題
画像の文字起こし
AからEまでの問題があり、各問題の得点が入力されます。
コンテスト参加者の得点状況は文字列で管理されます。
BCD ならBとCとD問題が解けて、それ以外は解けなかったことを表します。
ありうる得点の取り方の組み合わせを全て列挙してください。
並び方はスコアの降順、名前の昇順で並べてください。
アプローチ
画像の文字起こし
Bit全探索で2^5までを全探索します。
bitが立っている箇所をその得点が取れたこととして、記録します。
同時にABCDEの名前もそのbitが立っている文字をとって名前を生成します。
最後に名前の昇順にソートしてから、得点の降順にソートします。
先に名前の昇順をすることで、得点のソートをした際に、得点、名前のソートがされるようになります。
D問題
問題
画像の文字起こし
数値SとリストAが与えられます。リストAの中身は軽数です。
リストAの部分集合の和から、Sを生成できるかを求めてください。
例1
S = 42
A = [3, 8, 4]
[8,4,3,8,4,3,8,4］の部分集合で生成できます。
例2
S = 1
A = [3, 8, 4]
どの部分集合でも生成できません。
アプローチ
画像の文字起こし
最初にSをAの和で割った余りを求めます。
こうすることで、計算範囲をSまでにできます。これをaとします。
S = sum(A) * x + aと置けます。
したがって、このaが部分和にあるなら、Sを生成できます。
a = 42 % (3 + 8 + 4) ＝ 12
a + 累積和が累積和の1つなら、それは生成できるということになります。
a+3=15の15は累積和に含まれます。よって生成できます。
累積和の特徴
画像の文字起こし
累積和a - 累積和b ＝ 部分和k が成り立ちます。