問題

問題文

$X$ 段重ねの鏡餅 $(X \ge 1)$ とは、$X$ 枚の円形の餅を縦に積み重ねたものであって、どの餅もその真下の餅より直径が小さい（一番下の餅を除く）もののことです。例えば、直径 $10$、$8$、$6$ センチメートルの餅をこの順に下から積み重ねると $3$ 段重ねの鏡餅になり、餅を一枚だけ置くと
$1$ 段重ねの鏡餅になります。
ダックスフンドのルンルンは $N$ 枚の円形の餅を持っていて、そのうち
$i$ 枚目の餅の直径は $d_i$ センチメートルです。これらの餅のうち一部または全部を使って鏡餅を作るとき、最大で何段重ねの鏡餅を作ることができるでしょうか。

制約

・$1 \le N \le 100$
・$1 \le d_i \le 100$
・入力値はすべて整数である。

収録されている問題セット

回答

回答1 (AC)

配列に保持された値の種類をカウントする問題です。値は整数で、その範囲は狭いので、さまざまな回答が考えられます。

まずは、値の種類をカウントするための配列 m を使用します。直径 d の餅が存在するときは m.at(d)=true, 存在しないときは m.at(d)=false となるように配列の値を設定していきます。count(m.begin(),m.end(),true) によって、配列 m に含まれる true の個数をカウントできます。コードは以下のようになりました。

abc085b-1.cpp

# include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin >> n;
 
  vector<bool> m(101,false);
  int t;
  for ( int i=0; i<n; i++ ) {
    cin >> t;
    m.at(t) = true;
  }

  int answer = count(m.begin(),m.end(),true);
 
  cout << answer << endl;
}

なお、ここでは配列 m の値をブール値にしましたが、これを整数に変更することで、各値が何個存在するかを調べることもできます (が、今回の問題ではそこまでは必要なかったので、ブール値にしました)。

回答2 (AC)

カウントしたい配列の値が整数以外の場合や、整数だとしても範囲が膨大である場合には回答1を適用できません。そこでよく使用されるのが map 型変数です。map 型変数は 2 つの値 (key と value) のペアとして表され、key と呼ばれる値から value と呼ばれる値を参照することが可能です。いわゆる辞書型変数です。key の重複はできないので、この問題のように値の種類が必要な場合によく使用されます。map を使ったコードは以下のようになりました。

abc085b-2.cpp

# include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin >> n;
 
  map<int,bool> m;
  int t;
  for ( int i=0; i<n; i++ ) {
    cin >> t;
    m[t] = true;
  }
  int answer = (int)m.size();
 
  cout << answer << endl;
}

回答3 (AC)

今回の問題は値の種類をカウントしたいだけなので、set 型変数を使うことが出来ます。set 型変数の要素は重複はできないし、要素そのものしか保存されないので、今回の問題には最適です。set を使ったコードは以下のようになりました。

abc085b-3.cpp

# include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin >> n;
 
  set<int> m;
  int t;
  for ( int i=0; i<n; i++ ) {
    cin >> t;
    m.insert(t);
  }
  int answer = (int)m.size();
 
  cout << answer << endl;
}

調べたこと

AtCoder に登録したら次にやること

回答1と回答3が紹介されていました。

AtCoder の解説 → ユーザ解説

回答3と同じ方針でした。

AtCoder の解説 → コンテスト全体の解説

方針1は回答1、方針2は回答3と同じでした。

リンク

前後の記事

前の記事 → AtCoderログ：0062 - CODE FESTIVAL 2016 qual B B