E問題をC++とPythonで解いてみました。ABC305は、2023年6月10日21:00に実施されました。紹介はこちらに、プログラミングの方針はこちらに記事があります。1158)問題はリンク先をご覧ください。Graphダイクストラ法の考え方を適用して解くことができます。解答案この問題は、各頂点から警備員がいる頂点までの距離を求めて、条件を満たすか判定する解法は、明らかに計算時間が間に合いません。なるため間に合いません。以下で紹介するダイクストラ法と同じ考え方が使えます。ダイクストラ(Dijkstra)法とはダイクストラ法は、グラフのある頂点からすべての2頂点間の最短経路を求めるアルゴリズムです。アルゴリズムのポイントは、「登録された距離が最小である頂点から処理していく」ことにあります。この処理のために優先度付きキューを使う場合が多いようです。この問題は、「警備員の体力が多い頂点から処理していく」と読み替えてアルゴリズムを適用します。ダイクストラ法については、書籍でもネット上でも説明を見つけることができるため、本記事の記述は以上とします。通常のダイクストラ法では、距離が最小の値から取り出すため、テンプレートの第3引数を指定しますが、この問題は最大の値から取り出すため、テンプレートの第1引数だけ指定します(21行目)。以下のように処理をしていきます。グラフを定義する(12-19行目)。(警備員の体力、頂点)を登録する(21ー27行目)。キューにデータが残っている場合、以下を行う(29-42行目)。キューから値を取り出す(警備員の体力が一番大きな頂点を取り出す)。その頂点の警備員の体力が(更新されて)大きい場合は、次のキューの処理を行う。その頂点と連結している頂点に対して、更新した警備員の体力が大きくなる場合その頂点の警備員の体力を更新する。以下が、C++プログラムとなります。0;}AC(Accepted=正しいプログラム)と判定されました。掛けて値を取り出しています。これにより結果的に最大値を取り出しています(16、22、27行目)。関係する行の背景色を変更しました。result.append(i)print(len(result))print(*result)こちらも「AC」と判定されました。使って該当する頂点を求めました。なるため、時間的に間に合いませんでした。ダイクストラ法については、知っていましたが応用ができませんでした。公式解説を参照しながらではありますが、この問題を解くことにより、ダイクストラ法の理解が深まりました。問題を紹介していきます。コメントをキャンセルメールアドレスが公開されることはありません。付いている欄は必須項目です上に表示された文字を入力してください。Contest)記事一覧ソフトウェア技術者アナダパンチ組込み製品の開発に従事しているソフトウェア技術者です。仕事でソフトウェア開発に従事しながら、趣味でもプログラミングを楽しんでいます。