srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

bfs

yukicoder No.360 増加門松No.307 最近色塗る問題多くない?

問題 問題概要 省略 解法 bfsで書いた。やることはシンプルで、色を変えた場所から隣接している同じ色だった部分の色も同時に変わるので、そのようなマスをbfsで探索して色を変えていけばいい。これを実装すると、O(HWQ)となり、TLEしてしまう。ここをどう…

SRM 699 div2 hard FromToDivisibleDiv2

問題 問題概要 a[i]の倍数の頂点番号からb[i]の頂点番号へ有向グラフを張ることができる。SからTに行く最小コストを求める問題。 解法 愚直に、(a[i]の倍数) -> (b[i]の倍数) の有向グラフをすべてはり、bfsで、到達した点までの距離を更新しながら、最短距…

yukicoder No.424 立体迷路

問題 問題概要 省略 解法 bfsで解いた。よくある、2次元座標上での迷路問題などで、ゴールまで行けるかの問題と同じようにやる。ただし、4方向への移動が高さの条件で制限されるので、それを確認すればよい。また、dyとdxを2倍して、2倍の距離の移動も同様に…

yukicoder No.124 門松列(3)

問題 問題概要 省略 解法 bfsで解いた。進める方向は、進もうとするマスと、現在のマスと過去のマスの3つが門松列をなしているとき。注意しなければならないのは、基本的な最短経路問題で使うbfsのように、座標のみを状態として最短距離をメモしていくと、解…

ABC 021 C - 正直者の高橋くん

問題 問題概要 省略 解法 bfsで解いた。よくある最短距離を求めるときにやる、bfsは一度、到達したところは2回目以降むしをするが、今回は、初めて到達したあとも、その位置に最短距離として、ほかの経路から到達して来る可能性があるので、bfsで初めに到達…

abc 020 C - 壁抜け

問題 問題概要 省略 解法 2分探索and最短経路問題。 xを小さくしていけば、かならず、ゴールにたどり着け、無限に大きくしていけば、どこかで、たどり着けなくなる。このような場合、求めるxを2分探索で効率よく絞り込んでいける。あとは、そのxに対して、ダ…

yukicoder No.277 根掘り葉掘り

問題 問題概要 木の上での最短経路(根からの距離、葉からの距離)を求める問題。 解法 根から葉、葉から根へ向けて、bfsをすればいい。その時に注意することはbfsで次に進む方向を決めるときに、来た方向に戻ってしまうと、正確な値が求まらないので、queueの…

yukicoder No.34 砂漠の行商人

問題 問題概要 省略 解法 2次元座標のなかで、スタートからゴールまで最短距離で行けるかを判定する問題。最短経路を求めるのだから、bfsで解けばいい。ただし、よくある迷路のような問題で最短距離を求める問題は、状態が座標のみでよいが、今回は残りの体…

ARC 005 C - 器物損壊!高橋君

問題 問題概要 省略。 解法 よくあるのは、used[y][x]で(x, y)へ行くことができたことをメモしてbfsをやったりしていたが、今回は、何回壁を壊して、(x, y)へ到達できたかの情報も必要なので、used[y][x][k]として、k=0なら壁を壊さず、(x, y)へ到達できてお…

ARC 003 C - 暗闇帰り道

問題 問題概要 省略。 解法 sからgまでの経路が存在するとき、答えを小さくすれば、条件を満たし、答えを大きくしていくと、条件を満たさなくなる。そのため、答えを2分探索していけばよいことになる。また、ある地点まで、最短でいったときが、そのますの明…

yukicoder No.13 囲みたい!

問題 問題概要 閉路検出 解法 考え方が悪かった。閉路検出のためにある始点から初めて、1周してその点に戻るかを判別すればいいなと思い、dfsもどきのbfsみたいなのを書き出したが完全に悪かった。閉路検出は「ある始点からスタートして、探索方向はfrom以外…

yukicoder No.157 2つの空洞

問題 問題概要 省略 解法 まず、穴が2つあることがわかっているので、bfsでana1とana2にそれぞれ穴の座標を入れる。ana1とana2の全ての穴に対して、それぞれの穴をつなげる時に退ける壁の数を求め、それらの最小値が 答えとなる。 ミス なし。 コード #inclu…

yukicoder No.240 ナイト散歩

問題 問題概要 省略。 解法 幅優先探索。qに座標を入れて、numに何回目の動きなのかを入れてやった。 ミス 特になし。 コード #include <iostream> #include <vector> #include <queue> #include <cstdio> #include <algorithm> using namespace std; #define rep(i,n) for(int i=0;i<(n);i++) int dx[8] </algorithm></cstdio></queue></vector></iostream>…

aoj 0596 - Taxis

問題 問題概要 与えられたグラフに対して、幅優先探索を使い、条件を満たした新たなグラフを表す隣接行列を作り、ダイクストラで最小コストを作る。 解法 与えられたグラフのままでは、多くの条件あり、そのままではダイクストラをすることができない。そこ…

aoj 0569 - Illumination

問題 問題概要 場合分けが必要な6方向の幅優先探索。イルミネーションが必要なところが色塗りの感覚でわかる。 解法 まず、イルミネーションが必要なのは、外側のみであり、内側の部分は必要ない。よって、その外側の部分(周りが完全に囲まれている中の部分…

yukicoder No.3 ビットすごろく

問題 問題概要 省略。 解法 エラトステネスをイメージしてやった。アルゴリズムは幅優先探索を利用している。queueにスタート時点の1をいれて、そのあとは、2進数にした時の1の数によって、両側に動いた場所を調べている。幅優先探索で調べると、移動が少な…

aoj 0558 - Cheese

問題 問題概要 幅優先探索で最短経路を求める問題。ただしスタートとゴールがいくつもある。 解法 よくあるstartからgoalまでの最短経路を求める問題と同じ。ただし、その途中でチーズを小さい順に食べていかなければならない。そのため、(ciをチーズi番目…