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

ABC085 B - Kagami Mochi (200)

B - Kagami Mochi

概要

N項の数列dが与えられ、数列dは鏡餅の直径を表している。
鏡餅iと鏡餅jはdi < djであるときiをjの上に重ねることができるものとする。また、鏡餅は何段でも重ねられるものとする。
重ねられる鏡餅の枚数の最大値を答えよ。

制約

1 ≦ N ≦ 100
1 ≦ di ≦ 100

方針

diをsetにinsertしてゆき、sizeを出力すればよい。

解答

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)

概要

N項の文字列からなる列sとM項の文字列からなる列tが与えられる。
文字列を1つ指定し、それがsに含まれていればその個数分得点が加算され、tに含まれていればその個数分点数が減算される。
得られる得点の最大値を答えよ。

制約

1 ≦ N, M ≦ 100

方針

sにもtにも含まれていない文字列を指定すると、0点が得られる。
これ以上の得点、すなわち正の得点を得るにはsに含まれる文字列を指定する必要がある。
これは次のようにして得られる。
つまり、sに含まれる各文字列について、その文字列を指定して得られる得点を計算する。tも同様に計算する。
そしてsに含まれる各文字列について、最終的な得点をすべて比較し、最も大きいものを答えればよい。
各文字列の得点計算にはmapを使用すると便利。

解答

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;
}