AtCoder プログラミングコンテスト2024（AtCoder Beginner Contest 382） のB問題〜D問題をPythonで解説します。
提出コード
B問題
問題
画像の文字起こし
＠と、で構成される文字列が与えられます。
＠がクッキーが入った、・が空箱です。
1日1枚ずつ最も右のクッキーを食べる時、D日後の箱の状況を出力してください。
アプローチ
画像の文字起こし
単純にD日後までを1日ずつシミュレートしていきます。
C問題
問題
画像の文字起こし
回転寿司にN人の客とM貫の寿司があります。
寿司にはそれぞれ美味しさの数値が設定されていて、客はその美味しさ以上の寿司しか食べない美食度が設定されています。
寿司は左から流れてきます。
それぞれの寿司はどの客に食べられるかを求めなさい。
誰にも食べられない寿司もあります。
アプローチ
画像の文字起こし
どの美味しさの寿司までをどの人が食べるかの配列を最初に作り、その後、実際にどの客が食べるかを求めます。
人を順番に見ていき、その人の美食度までをその人のインデックスの値で埋めます。
配列は美味しさの最大値の2*10**5を用意します。初期値は-1で埋めておきます。
配列の右側から見ていき、その人の美食度までをその人のインデックスの値で埋めます。
1人目の客が美食度3の場合、以下のようになります
配列の右側から見る理由
美味しい寿司ほど左側の人が食べるため、配列は右から埋めていきます。
1人目が美食度3だと、2人目以降は美味しさ2以下の寿司しか食べられません
2人目の客が美食度8の場合、何も食べられません。
先客がいなければ美味しさ8以上の寿司が食べられますが、
1人目の美味しさ3以上の寿司を食べてしまうため、何も食べられません。
つまり、先客の最低値をさらに下回る美食度の場合のみに、寿司が食べられる可能性が出てきます。
3人目の客が美食度2の場合、以下のようになります。
あとは、流れてくる寿司の美味しさの値を
作成した配列のインデックスに当てはめることで、どの客が食べるかを求められます。
D問題
問題
画像の文字起こし
文字列Sがあります。この文字列に以下の操作をQ回行った際の、
K番目の文字列を求めてください。
アプローチ
画像の文字起こし
全探索の再帰で解けます。
荷形だとわかりやすいです
1-11-21の次は1-11-22というように出力するので、DFSが有効です。
DFS
・階層がNになったら値を出力して終了
・そうでなければ1階層下にいく
・その層内でループを組む
・開始値は直前の値と＋10した値、終了値はM - （N- 現在の階層を引いた数）*10
N=3の時
1階層目：Mから-20した値が終了値
2階層目：Mから-10した値が終了値
3階層目：Mが終了値
シミュレーション
画像の文字起こし
最初は1から始まります。
同じ階層に2から3を作成し、スタックします
1つ下の階層に行き、11から13を作成し、スタックします。
11を処理します。1つ下の階層に行き、21から23を作成し、スタックします。
21を処理します。階層がnに達したので、この処理を終了し、次の処理に移行します。
同様に22と23を処理します。
同様に12と13、2と3を処理します。図は省略します。