ツバサの備忘録

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

深さ優先探索(DFS)

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通りであり…