AtCoder蟻本 初級編 2-4 データ構造 ②二分探索木 (set, map の練習)

ABC085 B - Kagami Mochi (200)

B - Kagami Mochi

概要

項の数列のうち、相異なる項は最大いくつあるか。

制約

方針

数字をsetに入れてsetのサイズを出力する。

感想

set初使用。setがないと100までのbool配列に数字の出現の有無を記録して解いたと思う。
set便利。

解答

Submission #4081783 - AtCoder Beginner Contest 085

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int N;
	cin >> N;
	set<int> st;
 
	rep(i, N) {
		int d;
		cin >> d;
		st.insert(d);
	}
 
	cout << st.size() << endl;
}

ABC091 B - Two Colors Card Game (200)

https://atcoder.jp/contests/abc091/tasks/abc091_b

概要

個の文字列からなる配列と個の文字列からなる配列が与えられる。
好きな文字列を1つ指定する。この文字列がに含まれていれば、含まれている個数だけ+1を得て、この文字列がに含まれていれば、含まれている個数だけ-1を得ることとする。
得ることが出来る最大の得点を出力せよ。

制約

方針

、をmapに格納する。このときkeyは文字列、valueはその文字列が配列に含まれている個数とする。
を格納したmapのそれぞれの文字列について、その文字列を指定したときの点数を計算し、その最大値を出力する。

感想

Bとしては難しい部類に入ると思う。

解答

Submission #4081827 - AtCoder Beginner Contest 091

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int N;
	cin >> N;
 
	map<string, int> mps;
	rep(i, N){
		string s;
		cin >> s;
 
		auto it = mps.find(s);
		if(it == mps.end()) mps[s] = 0;
		mps[s]++;
	}
 
	int M;
	cin >> M;
 
	map<string, int> mpt;
	rep(i, M){
		string t;
		cin >> t;
 
		auto it = mpt.find(t);
		if(it == mpt.end()) mpt[t] = 0;
		mpt[t]++;
	}
 
	int ans = 0;
	for(auto it = mps.begin(); it != mps.end(); it++){
		string key = it->first;
		int vals = it->second;
 
		auto itt = mpt.find(key);
		if(itt == mpt.end()){
			ans = max(ans, vals);
		}else{
			int valt = itt->second;
			ans = max(ans, vals - valt);
		}
	}
 
	cout << ans << endl;
}