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));
  }
}