公式

B - Mapping 解説 by Nyaan


まずは質問を整理しましょう。着られている服の番号 \(F_1, F_2, \dots, F_N\) の重複を取り除いてできる集合 \(S\) を考えます。この時、

  • 質問 \(1\) の答えは \(|S| = N\) であることと等価で、
  • 質問 \(2\) の答えは \(|S| = M\) であることと等価です。

ここで \(|S|\) は集合のサイズを意味します。よって \(S\) のサイズを求めればこの問題を解くことが出来ます。
たいていのプログラミング言語には集合を扱うデータ構造が存在します。例えば C++ であれば std::set型、Python では set 型が集合を扱う型です。これらを使えばスムーズに実装できます。

  • 実装例(C++)
#include <iostream>
#include <set>
using namespace std;

int main() {
  int N, M;
  cin >> N >> M;
  set<int> S;
  for (int i = 0; i < N; i++) {
    int F;
    cin >> F;
    S.insert(F);
  }
  cout << ((int)S.size() == N ? "Yes" : "No") << "\n";
  cout << ((int)S.size() == M ? "Yes" : "No") << "\n";
}

投稿日時:
最終更新: