問題
問題文
$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 の個数をカウントできます。コードは以下のようになりました。
#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 を使ったコードは以下のようになりました。
#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 を使ったコードは以下のようになりました。
#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と同じでした。