ツバサの備忘録

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

深さ優先探索(DFS)

ABC149 F - Surrounded Nodes

問題 提出コード 解法 ある頂点が白であったときに、その頂点がに含まれる確率を計算します。すると、この確率は、どの頂点についても独立に計算できるので、全ての頂点について同じことを計算して足すことで、その総和が答えとなります。 また、確率は、に…

AOJ 1168 - ぐらぐら

問題 提出コード 解法 愚直に、それぞれのピースに対して条件を満たしているか確認していきます。 ピースそれぞれを頂点、上下で接しているかどうかを辺としたグラフを作成していき、あるピースに対してのバランスを調べる際は、そのグラフを辿って見ていき…

AOJ 1131 - Unit Fraction Partition

問題 提出コード 解法 DFSで答えを探します。 まず、分母の値が小さいものから順番に使用していくとします。そして、以下の情報を持ちながら探索していきます。 一番最後に使用した単位分数の分母の値 現在の総和(分母、分子) 現在いくつの単位分数を利用し…

ABC126 D - Even Relation

問題 提出コード 解法 木、とは書かれているのですが辺に重みがあるのでダイクストラをしてしまいました。 ある頂点と別の頂点の距離が奇数の場合、その部分は確実に色が異なります。 これを繰り返すと、結局はある頂点を一つ決めた際に、そこからの距離の偶…

WUPC2019のお話(解法編)

ということで、今回は各問題についての簡単な解法と、その感想です。 まだ解けていない問題もいくつかあるので、ご容赦ください… 運営側としてどんなことをしたか、についてはこちらの記事をご覧ください。 emtubasa.hateblo.jp 各問題の方針と感想 A - WAse…

AOJ 1174 - 同色パネル結合

問題 提出コード i回目に色xを選ぶ、とすると6種類の色を5回選ぶので、全体でパターンあります。 現在、左上に結合しているパネルの位置の情報がわかれば、i回目に色xを選んだ際に新しく結合する部分は深さ優先探索で求めることができます。 あとは、i回目に…

AOJ 2891 - な◯りカット (Namo.. Cut)

問題 提出コード 解法 再帰を書いていたらバグが取れなかったのでグーグル先生を使ったところ、このような記事が見つかったのでこちらの橋検出の考え方を参考にさせていただきました。 ノードを見た順番に番号を振っていきます。これを再帰的に繰り返し、一…

AOJ 1197 - サイコロ職人

サイコロ職人の朝は早い。 サイコロ職人 | Aizu Online Judge 提出コード さて、立方体を転がしてある面が下になった回数をカウントしたときに、指定された6つの数字のグループと一致するように転がせ、という問題です。 転がす方向は東西南北の4通りであり…