AtCoder Beginners Selectionをやる【ABC085B - Kagami Mochi】
日記代わりになにか書かないとサボってしまうので書きます。
プログラミング初心者のコードなので同じ初心者のひとはもっと上手い人の記事のコードを参考にしてください。
ABC085B - Kagami Mochi
atcoder.jp
やること
- 最大三桁の数値Nを受け取る(intで可)
- N個(最大100個)の数値を受け取る(配列)
- 重複する数値は削除するなどして1つにする
- 残った数値の数を数える
解答1 Vectorで受け取りUniqueで重複を潰す
要素数が100と小さいので、
1.vectorの要素をソート
2.uniqueで隣り合う重複要素を潰す
3.末端に発生する空要素をeraseで削除する
4.vectorのサイズを取得
この4ステップでも計算量が膨らんだりせずACを取れるはずです。
#include <bits/stdc++.h> using namespace std; int VecCinFor(vector<int>&a,int N){//入力をvectorに挿入 for(int i=0;i<N;i++){ cin >> a.at(i); } return 0; } int main() { int N; cin>>N; vector<int>vec(N); VecCinFor(vec,N); sort(vec.begin(),vec.end()); vec.erase( unique(vec.begin(),vec.end()) ,vec.end()); cout << vec.size() <<endl; }
cpprefjp.github.io
C++日本語リファレンスによるとuniqueは要素を削除せず、
末尾に重複削除分のゴミ要素を追加します。
またuniqueの返り値が重複のない要素の末尾の次のイテレーターを返すので
eraseでuniqueの返り値(ゴミ要素先頭)-vectror末尾(ゴミ要素最後尾)の範囲を削除することで
vectorのサイズが重複なし数値の数と等しくなり、解答となります。
今回作った処理を関数化していつでも呼び出せるように加工しましょう。
int DuplicateDeth(vector<int>&a){ sort(a.begin(),a.end()); a.erase(unique(a.begin(),a.end()),a.end()); return 0; }
これでいつでもvectorの重複要素を殺せるようになりました。
解答2 Setで受け取るだけ
数値の受け取りは何もvectorでしかできないということ無く
setに入力すればその時点で重複要素を弾くことができます。
ついでに入力時点でソートもしてくれます。
#include <bits/stdc++.h> using namespace std; SetCinFor(set<int> &a,int n){//入力をsetに挿入 for(int i=0;i<n,i++){ int x=0; cin>>x; a.insert(x); } return 0; } int main(void) { int N; cin>>N; set<int> moti; SetCinFor(moti,N); cout << moti.size() <<endl; }
要素を入力する場合、set.insert(要素)を使います。
仮受取用の変数xを毎回初期化して呼び出し、cin>>x;で入力を受け取った上で
set.insert(x);でsetに要素をぶちこみます。
ぶちこみ終わったらset.size()がそのまま解答となります。
余談
要素数Nの入力を受け取るためにいちいちfor文を書くのが面倒なことにようやく気がついたので
関数のオーバーロードでいいかんじに処理を予め作っておこうとようやく思い立った。
repマクロは……えーい使っちゃえ!
#include <bits/stdc++.h> #define rep(i, n) for (int i = 0; i < (int)(n); i++) using namespace std; int VecCinRep(vector<int> &a,int X){ //一次配列の入力 rep(i,X){ cin>>a.at(i); } return 0; } int VecCinRep(vector<vector<int>> &a,int X,int Y){ //二次配列の入力 rep(i,X){ rep(j,Y){ cin>>a.at(i).at(j); } } return 0; } int VecCinRep(vector<vector<vector<int>>> &a,int X,int Y,int Z){ //三次元配列の入力 rep(i,X){ rep(j,Y){ rep(k,Z){ cin>>a.at(i).at(j).at(k); } } } return 0; }
これで三次元配列までの入力がVecCinRep()にわたす引数の数でそれぞれ対応してくれる。
だがint型なのでオーバーフローすると全滅する儚い命。
これを解決するにはlong long型(最強の数値型)にしておけばとりあえず正解なのですが
まあ、今はいいか……(300点問題以上ではintが力不足らしい)
long longを乱用するために短くしたい場合、
typedef long long ll; //c++11より前はこれ using ll=long long;//c++11以降
これで最強魔法を詠唱短縮して使える。
大体の環境はすでにC++11以降の便利なC++なので好きな方でいいんじゃないかな。
あとC++のテンプレートを使うと型を差し替え可能にできる、らしい(勉強中)
余談2 setの得意不得意
鏡餅にたいして圧倒的優位性を見せつけたset君ですが、vectorとどう使い分けるべきか初心者はわからなくなったので調べてみました!(底質なキュレーションサイト味)
setが得意
- 自動で要素の重複の削除
- 自動で要素のソート
- 要素の挿入削除が早い(log n)
- 要素を検索する時間も早い(log n)
上のコードではset.insert(x)で要素を挿入したけれど、
どうやらset.emplace(x)のほうが若干早いらしい。
setが苦手
- メモリ使用量が多め(vectorの3倍?)
- 要素の全列挙が遅め
- 重複を消してしまう(multisetを使うと重複が許される)
setにしかできないことは特に無く、vectorでも工夫(これが難しい)すれば同じことができるので
setは一分野に突出した才能があるというだけのよう。
戦う場所を選べばsetは強いみたい