AtCoder Beginner Contest 376（Promotion of AtCoder Career Design DAY） のB問題〜D問題をPythonで解説します。
提出コード
B問題
問題
画像の文字起こし
円形にN個のパーツが繋がったリングあります。
最初はL（左手）に1番目、R（右手）に2番目のパーツを持っています。
Rは右回りに、Lは右回りに1つずつ移動します。
ただし、同じパーツを両手で持つことはできません。
移動先にもう一方の手がある場合は、逆回りで移動します。
与えられた指示に従うために必要な操作回数の合計の最小値を求めてください。
アプローチ
画像の文字起こし
移動元をfrom、移動先をto、もう一方の手をngとおきます。
右回り、左回りの場合分けは無視できます。ngを通らない回り方が常に選択経路になります。
from,to は入れ替えてしまっても問題ないです。操作回数に影響しないため。
常にfrom≤toを満たすようにすることができます。
from＜ng<toの場合、N+from-to
それ以外の場合、to-fromで計算できます
計算量はO（N）です。
C問題
問題
画像の文字起こし
N個のおもちゃとN-1個の箱があります。それぞれ大きさが決まっています。 箱を1つ購入して全てのおもちゃが入りきるか判定してください。 新しく購入するは可能な限り小さくしてください。大きさ3の箱を購入することで
全てのおもちゃを箱に入れられます。
どんな大きさの箱を購入しても
箱に入りきらないおもちゃが出てきます。
アプローチ
画像の文字起こし
まず、ソートします。
次に全てのおもちゃが入りきるかを判定します。
おもちゃと箱を昇順に比較して、おもちゃの方が大きいケースが存在したら、
入りきらないと判定できます。
おもちゃと箱の差ができるだけ出ないように
昇順ソート順で比較します。
最大おもちゃは購入する箱で
調整可能なので、最も効率的に
箱に入れた時、最大おもちゃ以外が
入り切るかをチェックします
おもちゃがは入りきることがわかったので、次は購入する最小の箱を見つけます。
おもちゃと箱を降順に見ていき、おもちゃと1つ小さい箱を比較します。
おもちゃの方が小さければ、そのおもちゃの箱は既存の箱で十分ということです。
逆に、おもちゃの方が大きければ、そのおもちゃの大きさが購入する箱に
なります。
7のおもちゃは8の箱
5のおもちゃは6の箱
3のおもちゃは2の箱に入らないので、
購入する箱は3です。
最後までおもちゃの方が小さいままだったら、
一番小さいおもちゃの大きさの箱を購入します。
大きさ1のおもちゃが入ればいいので、
購入する箱は1です
計算量はO（NIogN））です。
D問題
問題
画像の文字起こし
単純有向グラフに頂点1を含む閉路が存在するか判定してください。
存在する場合、当てはまる閉路のうち、最短の平路の長さを求めてください。
アプローチ
画像の文字起こし
BFS（幅優先探索）で解くことができます。
特に最短経路の発見や、特定の条件を満たすノードの探索に
向いているグラフ探索アルゴリズムの一種です。
BFSを用いて各頂点への距離を距離の昇順に計算します。
頂点1へ帰る辺の時、距離に1を加えたものが解になります。
計算量はO（N+M）です。