ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

幅優先探索(BFS)

AOJ 2885 - 分割統治

問題 提出コード 解法 まず、問題の条件を満たすようなパターンについて整理します。1つめのサンプルを見てみると、例えば下のようなパターンがあり得ます。 青が太郎、黄色が次郎、緑が花子さんの統治している国になります。 結局のところ、 太郎君(花子さ…

AOJ 2153 Mirror Cave

問題 提出コード 解法 普段のグリッドに対するBFSが2次元ならば、今回は4次元です。 Len君が、Ren君がにいるときに、そこから行くことができる4通りの方向に進みます。 そして、に行くことができるかどうかを調べていき、それぞれがゴールのマスに同時にたど…

九州大学プログラミングコンテスト2018 C - Ito Campus

問題 提出コード 解法 何も考えずにうしくんのゴールへの行き方をBFSで求めようとすると、マス目を移動するたびに安全なマスかどうか調べるため、時間内に解くことができません。 しかし、この問題ではイノシシが移動することはないため、安全なマスであるか…

AOJ 2014 - 土地囲い

問題 提出コード 解法 黒の杭と拡大隣接してるマスは、幅優先探索を用いて行うことができます。白も同様です。 ということで、それぞれの色について、拡大隣接しているマスをすべて洗い出します。 その処理が終わったら、片方の色についてのみ拡大隣接してい…

ゆるふわ競プロオンサイト参加記

2/9に東京で行われました、@matsu7874さん主催の競プロオンサイトイベント、に参加してきました! コンテスト自体は全8問で、2時間のセットでした。自分は、ABCDEGの6完でした! B式A+B 集合写真 線香 最短経路は何本ありますか ガソリンスタンド 射的 感想 …

Educational DP Contest / DP まとめコンテスト G - Longest Path

問題 提出コード あきらかにこれで使えそうな問題ですね… 解法 グラフにおいて、スタート地点(入次数が0である頂点)に近い方から順番に、その頂点がゴールだったと仮定した場合における最長の距離を確定させていきます。 幅優先探索のようなものをします。…

Typical DP Contest M - 家

問題 提出コード 解法 bitDPです。だんだん詰め合わせ感が増えてきました。 同じ階層でからに移動するパターン数 とすると、これをの行列に見立てて乗すると、が答えになります。 を求めることさえできれば、あとはこの行列式のを求めていき、程度で答えが求…

ABC021 C - 正直者の高橋くん

問題 提出コード 辺被りを考慮しないコードも提出してみたのですが、どうやらないらしいです 解法 cnt[i] = i番目の町へ行く最短経路の数(で割った余りをとります) とすると、cnt[b]が答えになります。初期値は、cnt[a]=1です。 あとは、aから幅優先探索をし…

ABC075 C - Bridge

問題 提出コード 解法 橋検出アルゴリズムを用いてもいいのですが、今回は制約が小さいので、全ての辺に対して 辺を繋ぐ頂点の片方から、その辺を使わずにもう片方の辺にたどり着くことができるか という幅優先探索を行うだけで十分間に合います。 そして、…

ABC020 C - 壁抜け

問題 提出コード 解法 スタート地点から座標へ向かうルートのうち、黒のマスを合計回、白のマスを回通るようなものが存在するかどうか とします。すると、これは現在の座標と、通った黒と白のマスの個数をセットで記録しつつスタート地点から順番に幅優先探…

ARC056 B - 駐車場

問題 提出コード 解法 珍しく探索問題です。 番目の人が駐車するには、スタート地点から頂点へ向かう、次の条件を満たすルートが存在します。 スタート地点を含む、通り道に存在する頂点の番号すべてがより大きい ということで、基本的には幅優先を行い、今…

ABC067 D - Fennec VS. Snuke

問題 提出コード 解説の解法が綺麗すぎますね!! 解法 1とN以外の頂点を、 1から、Nを通らないとたどり着けない頂点 Nから、1を通らないとたどり着けない頂点 1とNどちらも、もう片方の頂点を通らずにたどり着ける頂点 の3種類に分けることができます。図で…

AOJ 2709 - 真っ暗な部屋

問題 提出コード 解法 真っ暗な部屋が多くて16個しかないので、真っ暗な部屋に関する何かしらの情報をbitで持つことができます。 基本的な考え方は、幅優先探索です。 例えば回指示を出すとしたとき、指示列の選び方は種類になります。全ての部屋に対して、…

AOJ 1296 - Repeated Substitution with Sed

問題 指定された変形方法が与えられるので、指定された単語から、目的の単語に変形する、最小回数を求めなさいというものです(できなければ-1を出力します)。 提出コード 解法 後ろから見てもいいことが特にない(実装してWAを出しました)ので、前から素直に…

AGC027 C - ABland Yard

問題 提出コード なんか最近すごい似た問題を見たような…(前日の練習会でこの問題を解いていました) ある頂点から、AとBが書かれている頂点どちらか片方にしかいけなくなった時点でその頂点を消してしまいます。 これを繰り返していき、頂点が残っていればYe…

Benelux Algorithm Programming Contest 2016 C Brexit

問題 N個の国と、P個の友好関係があります。 自分の国はXです。今、ある団体からLという国が脱退することを表明したので、回りの国も脱退するかどうかを考えています。 ある国は、友好関係を結んでいる国のなかで半分以上が脱退を表明していたら、その国も脱…

AOJ 0503 - Cup(JOI2005予選4)

コップ | Aizu Online Judge 提出コード ハノイの塔の制限をきつくしたような問題です。 基本的には幅優先探索をベースに考えます。 1回の手順で行う操作はA→B、B→A、B→C、C→Bの4通りなので、ある状態に対して、その4通りを行えれば行う、ということを繰り返…