競技プログラミング用 知識集積所
ABC404D - Goin' to the Zoo
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
同じところに3回以上行く意味はない。
つまり、各動物園について「0回行く」「1回行く」「2回行く」の3択をすればよく、全探索の候補が3^N通り、N=10の場合でも59049通りで済む。
つまり、各動物園について「0回行く」「1回行く」「2回行く」の3択をすればよく、全探索の候補が3^N通り、N=10の場合でも59049通りで済む。
今のところどの動物を何回見たかメモしつつ、深さ優先探索で最小値を探す。
動物のいる場所は、「各動物について、どこの動物園にいるか」が与えられるが、「各動物園について、どの動物がいるか」に作り替えた方が使いやすい。
動物のいる場所は、「各動物について、どこの動物園にいるか」が与えられるが、「各動物園について、どの動物がいるか」に作り替えた方が使いやすい。
解答例
注意点
答えが微妙にint型に入らない
Cの値が10^9までということは、3回以上行ってint型の範囲を超える可能性がある。
long long型を使う必要がある。
long long型を使う必要がある。
別解
bit全探索（未作成）を応用する
1つの動物園に対して2ビットずつ使って、2Nビットのbit全探索をする。
最初に各動物園にいった回数を確認するときに、3回行ったというのがあったら即continue;するのがポイント。
ループ1048576回中59049回以外はすぐに終了するので処理時間はそんなにかからない。
解答例
最初に各動物園にいった回数を確認するときに、3回行ったというのがあったら即continue;するのがポイント。
ループ1048576回中59049回以外はすぐに終了するので処理時間はそんなにかからない。
解答例
