Open6
競プロ問題考察
masato_is_a_ snake
方針
動的計画法を使用、常に最善手を選び続ける
masato_is_a_ snake執筆時間 180 + 180 = 360 + 22 => 380分
記事概要
- 幅優先探索(BFS)を用いた問題の方針と実装内容の解説を記載します。
対象読者
- BFSを用いた問題の知見がない方
問題概要
無向グラフが合って、以下のルールに従って色を塗っていく。
操作をk = 0...N-1回行う。
-
k = 0 -
k \neq 0
色が塗られた頂点を番号が小さい順にすべて出力する。
実装方針
こういった無向グラフを走破するやり方として幅優先探索(BFS)、深さ優先探索(DFS)で探索することが一般的。今回はBFSで解く。
なぜキューを用いた方が良いか？GhatGPTより
キューを用いた方が良い理由は、BFSの探索が「幅優先」であるためです。キューを使うと、最も探索が浅いノードから順に順番に処理され、探索の順序が自然に決まります。具体的な利点は以下の通りです：
シンプルで直感的なコード：キューを使うと、各ステップで処理するノードの順序を一貫して管理できるため、余計な処理（nodes[k]のような一時的な配列を用意する）が不要になります。
効率性の向上：キューに基づく実装では、「探索が浅いノードを先に処理する」性質が自然に維持されるため、探索範囲が増えても適切な順序で各ノードを処理できます。
幅優先探索(BFS)とは？
幅優先探索とは、現在のノードの隣接ノードをすべて訪れた後、次の層のノードに進む探索方法のこと
こちらでキャッチアップ中
提出コード
キューを使用していないコード
キューを用いたコード
補足
入力を与えると無向グラフを作成してくれるツールが非常に便利
masato_is_a_ snake
考えたこと
BFSの計算量はO(N)、よってクエリの回数分やるとなるとO(NQ)で間に合わない。
なんとなく、最後にまとめて足し算していけばいいことは分かるが具体的なやり方が見えていない。
幅優先探索1回とクエリの計算でO(N+Q)になるのが望ましい。
解説見た
DFSを用いていたので飛ばし