デンソークリエイトプログラミングコンテスト2023（AtCoder Beginner Contest 309）をPythonで解く-Shinoryo's Weblog

こんにちは, Shinoryoです.

A - Nine

愚直に実行しても良いのですが, Yesとなる条件は「$B - A = 1$」かつ「$A$が$3$で割り切れない」になることを利用することができます.

$A$と同じ形の配列$B$を用意して, 外側なら1つずらす形で$A$の値を$B$にコピーすればよいです.

薬を飲む最終日から初日までさかのぼっていくと, 飲む薬の錠数は増えていきます. その数が$K$を超えたところで, その日の翌日を出力します. もし最後まで$K$を超えることがなければ, それは1日目から$K$錠以下だったのですから, 1日目を出力します.

入力例1に似た状況を考えます.

頂点$1$と頂点$N_1 + N_1$を結ぶ経路の長さ(辺の本数)の最小値が$d$で, $d$としてあり得る最大値を求める問題です. したがって, 直感的な言葉で言えば, 「頂点$1$から一番遠い頂点」と「頂点$N_1 + N_2$から一番遠い頂点」を結んだ場合がそれにあたります.

ある頂点から一番遠い頂点は, 幅優先探索(breadth first search; BFS)を用いて求めることができます. ある根ノードで始まり隣接した全てのノードを探索し, そのそれぞれに対して同様のことを繰り返すことによって探索対象ノードを網羅する方法です.

幅優先探索は, 以下でも取り上げています.

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