ABC167に挑んだ回
AtCoder初心者なのでまだ参加回数6回のCかD問題で死ぬ人。
その上で新しいアルゴリズム勉強して、忘れないようにメモってるだけです。
C - Skill Up
N<12だから全探索でいいよね?でやって正解できた。
買わなかったケース・買ったケースで再帰組んでます。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
struct ReferenceBook { int price; vector<ll> understandings; // すべての理解度が上回っていたらtrue bool isUnderstandOK(ll understand) { for (auto itr = understandings.begin(); itr != understandings.end(); ++itr) { if (*itr < understand) return false; } return true; } void Print() { cout << price << endl; } }; // お行儀は悪い ll ansPrice = LLONG_MAX; void func(ll index, const vector<ReferenceBook>& referenceBooks, ReferenceBook& ans, ll understand) { // 条件を満たしていたらこれまでの回答値と比較&安価なら保存 if (ans.isUnderstandOK(understand)) { //ans.Print(); if (ansPrice > ans.price) { ansPrice = ans.price; } return; } if (index >= referenceBooks.size()) return; // この参考書を買わずに次に進む func(index + 1, referenceBooks, ans, understand); // この参考書を購入する。 // 参考書の価格・理解度を加算して次の参考書を見る auto tmpAns = ans; tmpAns.price += referenceBooks[index].price; for (int i = 0; i < referenceBooks[index].understandings.size(); ++i) { tmpAns.understandings[i] += referenceBooks[index].understandings[i]; } func(index + 1, referenceBooks, tmpAns, understand); } int main(void) { ll n, m, x; cin >> n >> m >> x; vector<ReferenceBook> referenceBooks; for (int i = 0; i < n; ++i) { ReferenceBook rb; cin >> rb.price; for (int j = 0; j < m; ++j) { ll a; cin >> a; rb.understandings.push_back(a); } referenceBooks.push_back(rb); } ReferenceBook ans; ans.price = 0; ans.understandings.resize(m); // 参考書の先頭から検索する func(0, referenceBooks, ans, x); // 組み合わせが見つからなかったので上書き if (ansPrice == LLONG_MAX) { ansPrice = -1; } auto output = ansPrice; cout << output; return 0; } |
回答例もググってみた。
この手の重複なしの組み合わせ探索にはbit探索が使えたらしい
→bit全探索について簡単にまとめる
値を1ずつ増やしてbit単位で値を見ると、確かに全パターン列挙できるね。
D - Teleporter
駄目だった。(ループをゴリ押し計算したりした)
ダブリングについて初めて知った。
今回みたいに同じ要素を重複して回るときには使うことになるようだ。
コメントを残す