問題 問題概要 木構造の情報が与えられる. すべての辺のコストを1として, コストLいないで通ることができる頂点の種類数の最大値を求める問題. ただしstart地点を0として, start,goal も通った頂点としてカウントする. 解法 一番の方針として, 頂点を巡った…

問題 問題概要 連結成分の中で、閉路がなく、木である連結成分の個数を求める。 解法 閉路を検出する問題。dfsで探索して、すでに探索した頂点をmemoで記録しておいて、同じところに2度来たら、その連結成分は閉路を持つので木ではないのでカウントしない。 …

問題 問題概要 省略 解法 メモ化再帰で解いた。サンプルで与えられている図のように辺を張り、dp[i] := i番目の商品が必要な数 とおき、自分の子で必要なものの数から、i番目に必要な個数を計算する形にした。商品nが必要な個数は1個なので、dp[n - 1] = 1と…

問題 問題概要 省略 解法 上司から直属の部下に対して辺を張り、有向グラフを作成する。それを利用して、dfsを行う。部下がいないとき、つまり、グラフ上で葉の部分に該当する部下の給料は1なので、1を返す。部下が存在するとき、つまり、葉以外の頂点では、…

問題 問題概要 省略 解法 dfsで友達の友達を求めることにした。この時に、dfsの引き数として、現在の頂点と、前回の頂点、探索回数、スタート時点の頂点を持つことにした。前回の頂点は元の頂点に戻るのを禁止しするため。スタート時点を保持しておくのは、…

問題 問題概要 省略 解法 nやkは小さいので、全探索できるな。でも、kが毎回変わるから、単純にループを書こうと思うと、kに応じて、ループの回数を変えたコードを書かなければならなくなり、めんどくさいので、dfsで何回ループをしなければならないかを引数…

問題 問題概要 LとRをK回2分探索をして、最終的な答えが、T-E < h' < T + Eに入る確率を求める問題。確率Pで誤った2分探索をして、確率(1-P)で適切な2分探索をする。 解法 全探索で、やろうと思うと、2k(k=30)でTLE?? ただし、2分探索をしていく途中で、 (T …

問題 問題概要 連結成分の数. 解法 dfsで連結成分の数を求めればいい. ミス なし. コード #include <iostream> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++) int dy[] = {1, 0, 0, -1}; int dx[] = {0, 1, -1, 0}; bool used[</iostream>…

問題 問題概要 スタートからゴールまでたどり着けるか。 解法 dfsで、スタートからゴールまでdfsでたどり着けるかやった。usedを使い、一度巡ったところをdfsしないようにしないと、オーバーフローで落ちた。 ミス なんか始めバグってた。でもなんか治った。…

問題 問題概要 nこの数字を使って、合計sにするパターンの総数 解法 dfsで周り4方向と連結した部分を塗りつぶしていく。連結成分を塗り終わると、dfsが終わる。次に、まだ塗り終わっていない場所からdfsを始めて、塗りつぶしていく。これを何回繰り返したか…

問題 問題概要 nこの数字を使って、合計sにするパターンの総数 解法 dfsで解いた。dfs(n, s, now) = (n := 残りの選択する数字の数 s := 残りの合計 now := 現在選択可能な数字) を要素として持ち、再帰関数を書けばいい。 ミス 教育的 コード #include <iostream> #in</iostream>…

問題 問題概要 与えられた数字を2つに分けて、共に、数字が昇順になるようにできるか。 解法 dfsで解いた。dfs(B, C, cnt) := (B:=Bの一番上の数 C:=Cの一番上の数 cnt:=何個目の数字か)を要素として持ち、再帰関数を書けばいい。 ミス シンプルなdfs コード…

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