トヨタ自動車プログラミングコンテスト2024#11(AtCoder Beginner Contest 379) のB問題〜D問題をPythonで解説します。
提出コード
B問題
問題
画像の文字起こし
食べるとX 本の歯が虫歯になるイチゴがあります。
イチゴは正常な歯でしか食べられません。
現在の虫歯の状況を示すので、イチゴを最大で何度食べられるか求めなさい。
アプローチ
画像の文字起こし
歯を左から順番に見ていきます。
イチゴを食べるのに必要な歯までをスライスして、虫歯がないことを確認します。
虫歯がなければ、食べられるイチゴの個数を＋1します。
次に確認する歯は、必要本数分の後ろから見ていきます。
C問題
問題
画像の文字起こし
石が置かれたマスがあります。
石は1つ右へ1つずつ移動させることができます。
1つのマスに1つずつ石が置かれるようにするには、
石を最低何回移動させればいいか求めなさい。
ただし、不可能な場合もあります。
アプローチ
画像の文字起こし
移動回数を求める前に前処理をします。
まずinputをマス目順にソートします。
次に不可能な場合の検証をします。
不可能な場合とは「そのマスまでの石の数が足りない時」
と「石の合計数がマス数に合わない時」の2つです。
移動回数は石の配置の重み付けの総和の現在と理想の差で求められます。
重み付けの総和とはマス番号と石の数の積です。
理想の石の配置の重み付けの総和は 1 * 1 + 2 * 1 ＋ … * N + 1 = N *（N + 1）// 2です。
Nまでの総和の式の導き方
100までの総和の時、1+100、2＋99…のような101のセットが50（100/2）個のため、
N*（N+1）//2になります。
石を1つ移動すると重み付けも＋1されます。
つまり、石を移動することで、理想の石の配置との総和の差が1ずつ減少します。
移動回数＝理想の石の配置との総和の差となります。
D問題
問題
画像の文字起こし
植える・待つ・収穫するという3種類の植物に関する指示が与えられます。
収穫は一定期間が経過した植物が対象です。
収穫の指示があった時に収穫できた植物の数を求めなさい。
アプローチ
画像の文字起こし
配列とキューで植物の高さを管理します。
配列に植えた時の累積日数を、キューにその配列のインデックスを記録します。
収穫の際には現在までの累積日数と各植物を植えたタイミングでの累積日数の差を
チェックします。
それがボーダー以上なら収穫、キューからもポップします。