EX25 - 3.05
Editorial
/
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
0から49までの整数からなる集合A, Bがあります。
プログラムの雛形をもとに、集合A, Bに対して操作を行う関数を実装してください。
実装する操作は以下の通りです。
操作 | 説明 | 例 |
---|---|---|
intersection |
AとBに共通して含まれる要素からなる集合を返す。 | A: {1, 2, 3}, B:{2, 3, 4} 結果:{2, 3} |
union_set |
AとBのうち少なくとも一方に含まれる要素からなる集合を返す。 | A: {1, 2, 3}, B:{2, 3, 4} 結果:{1, 2, 3, 4} |
symmetric_diff |
AとBのうちどちらか一方にだけ含まれる要素からなる集合を返す。 | A: {1, 2, 3}, B:{2, 3, 4} 結果:{1, 4} |
subtract x |
集合Aから値xを削除する。xは存在することが保証される。 | A: {1, 2, 3}, x: 2 結果:{1, 3} |
increment |
集合Aに含まれる要素すべてに1を加える。 ただし、操作前の集合に含まれる49は操作後は0になるものとする。 |
A: {1, 2, 49} 結果:{2, 3, 0} |
decrement |
集合Aに含まれる要素すべてから1を引く。 ただし、操作前の集合に含まれる0は操作後は49になるものとする。 |
A: {0, 1, 2} 結果:{49, 0, 1} |
プログラムの雛形
#include <bits/stdc++.h> using namespace std; // 各操作を行う関数を実装する // AとBに共通して含まれる要素からなる集合を返す bitset<50> intersection(bitset<50> A, bitset<50> B) { } // AとBのうち少なくとも一方に含まれる要素からなる集合を返す bitset<50> union_set(bitset<50> A, bitset<50> B) { } // AとBのうちどちらか一方にだけ含まれる要素からなる集合を返す bitset<50> symmetric_diff(bitset<50> A, bitset<50> B) { } // Aから値xを除く bitset<50> subtract(bitset<50> A, int x) { } // Aに含まれる要素に1を加える(ただし、要素49が含まれる場合は0になるものとする) bitset<50> increment(bitset<50> A) { } // Aに含まれる要素から1を引く(ただし、要素0が含まれる場合は49になるものとする) bitset<50> decrement(bitset<50> A) { } // Sに値xを加える bitset<50> add(bitset<50> S, int x) { S.set(x, 1); // xビット目を1にする return S; } // 集合Sの内容を昇順で出力する(スペース区切りで各要素の値を出力する) void print_set(bitset<50> S) { vector<int> cont; for (int i = 0; i < 50; i++) { if (S.test(i)) { cont.push_back(i); } } for (int i = 0; i < cont.size(); i++) { if (i > 0) cout << " "; cout << cont.at(i); } cout << endl; } // これより下は書き換えない int main() { bitset<50> A, B; int N; cin >> N; for (int i = 0; i < N; i++) { int x; cin >> x; A = add(A, x); } int M; cin >> M; for (int i = 0; i < M; i++) { int x; cin >> x; B = add(B, x); } // 操作 string com; cin >> com; if (com == "intersection") { print_set(intersection(A, B)); } else if (com == "union_set") { print_set(union_set(A, B)); } else if (com == "symmetric_diff") { print_set(symmetric_diff(A, B)); } else if (com == "subtract") { int x; cin >> x; print_set(subtract(A, x)); } else if (com == "increment") { print_set(increment(A)); } else if (com == "decrement") { print_set(decrement(A)); } }
制約
- Aの要素数はNで、要素はA_1, A_2, \cdots, A_Nです。
-
Bの要素数はMで、要素はB_1, B_2, \cdots, B_Mです。
-
1 \leq N, M \leq 50
- 0 \leq A_i \leq 49 (1 \leq i \leq N)
- 0 \leq B_i \leq 49 (1 \leq i \leq M)
- \mathrm{command}は以下のうちのいずれか
intersection
union_set
symmetric_diff
subtract x
- 0 \leq x \leq 49
- 集合Aにxが存在することが保証される
increment
decrement
入力
入力は次の形式で標準入力から与えられます。
N A_1 A_2 \cdots A_N M B_1 B_2 \cdots B_M \mathrm{command}
出力
操作の結果の集合について、含まれる要素を昇順、空白区切りで1行に出力してください。 末尾に空白を含めないことに注意してください。
ジャッジでは以下の入力例以外のケースに関してもテストされることに注意。
入力例1
3 0 1 2 3 1 2 3 intersection
出力例1
1 2
集合Aには{0, 1, 2}が含まれ、集合Bには{1, 2, 3}が含まれるので、これらに共通して含まれる要素は{1, 2}となります。
入力例2
3 0 1 2 3 1 2 3 union_set
出力例2
0 1 2 3
入力例3
3 0 1 2 3 1 2 3 symmetric_diff
出力例3
0 3
入力例4
3 0 1 2 3 1 2 3 subtract 2
出力例4
0 1
入力例5
3 0 1 49 3 1 2 3 increment
出力例5
0 1 2
入力例6
3 0 1 49 3 1 2 3 decrement
出力例6
0 48 49
ヒント
クリックでヒントを開く
intersection
はビット毎のAND演算を用いて実装できます。union_set
はビット毎のOR演算を用いて実装できます。-
symmetric_diff
はビット毎のXOR演算を用いて実装できます。 -
subtract x
はSを表すビット列のxビット目を0にすればよいです。 -
increment
,decrement
は全ての要素が1ずつ増える(減る)ので論理シフト演算が利用できます。
テスト入出力
書いたプログラムがACにならず、原因がどうしてもわからないときだけ見てください。
クリックでテスト入出力を見る
テスト入力1
3 0 1 2 3 10 11 12 intersection
テスト出力1
テスト入力2
50 0 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 3 1 2 3 increment
テスト出力2
0 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
テスト入力3
50 0 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 3 1 2 3 decrement
テスト出力3
0 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
解答例
必ず自分で問題に挑戦してみてから見てください。
クリックで解答例を見る
#include <bits/stdc++.h> using namespace std; // 各操作を行う関数を実装する // AとBに共通して含まれる要素からなる集合を返す bitset<50> intersection(bitset<50> A, bitset<50> B) { return A & B; } // AとBのうち少なくとも一方に含まれる要素からなる集合を返す bitset<50> union_set(bitset<50> A, bitset<50> B) { return A | B; } // AとBのうちどちらか一方にだけ含まれる要素からなる集合を返す bitset<50> symmetric_diff(bitset<50> A, bitset<50> B) { return A ^ B; } // Aから値xを除く bitset<50> subtract(bitset<50> A, int x) { A.set(x, 0); return A; } // Aに含まれる要素に1を加える(ただし、要素49が含まれる場合は0になるものとする) bitset<50> increment(bitset<50> A) { bitset<50> ret = A << 1; // 左シフトでまとめて+1する if (A.test(49)) { ret.set(0, 1); } return ret; } // Aに含まれる要素から1を引く(ただし、要素0が含まれる場合は49になるものとする) bitset<50> decrement(bitset<50> A) { bitset<50> ret = A >> 1; // 右シフトでまとめて-1する if (A.test(0)) { ret.set(49, 1); } return ret; } // Sに値xを加える bitset<50> add(bitset<50> S, int x) { S.set(x, 1); // xビット目を1にする return S; } // 集合Sの内容を昇順で出力する(スペース区切りで各要素の値を出力する) void print_set(bitset<50> S) { vector<int> cont; for (int i = 0; i < 50; i++) { if (S.test(i)) { cont.push_back(i); } } for (int i = 0; i < cont.size(); i++) { if (i > 0) cout << " "; cout << cont.at(i); } cout << endl; } // これより下は書き換えない int main() { bitset<50> A, B; int N; cin >> N; for (int i = 0; i < N; i++) { int x; cin >> x; A = add(A, x); } int M; cin >> M; for (int i = 0; i < M; i++) { int x; cin >> x; B = add(B, x); } // 操作 string com; cin >> com; if (com == "intersection") { print_set(intersection(A, B)); } else if (com == "union_set") { print_set(union_set(A, B)); } else if (com == "symmetric_diff") { print_set(symmetric_diff(A, B)); } else if (com == "subtract") { int x; cin >> x; print_set(subtract(A, x)); } else if (com == "increment") { print_set(increment(A)); } else if (com == "decrement") { print_set(decrement(A)); } }