い

いもす法

# include<iostream>
using namespace std;
int main() {
	int C,T;
	cin >> C >> T;
	int S[100], E[100];
	for (int j = 0; j < C; ++j) {
		cin >> S[j] >> E[j];
	}
	int table[100];
	for (int i = 0; i < T; ++i) {
		table[i] = 0;
	}
	for (int i = 0; i < C; ++i) {
		table[S[i]]++;//入店処理：カウントを1増やす
		table[E[i]]--;//出店処理：カウントを1減らす
	}
	//シュミレート
	for (int i = 0; i < T; ++i) {
		if (0 < i)table[i] += table[i - 1];
	}
	//最大値を調べる
	int M = 0;
	for (int i = 0; i < T; ++i) {
		if (M < table[i])M = table[i];
	}
	return 0;
}

同時刻に喫茶店にいた客の数の最大値を求める問題

次は、二次元に拡張して、１つのタイル上で現れるモンスターの種類の最大値を求める問題

ナイーブな解法
それぞれのモンスターについて、現れる短形の範囲に含まれるすべてのタイルについて１を足す方法が挙げられます。しかし、これの計算量はO(NWH)です。

# include<iostream>
using namespace std;
int tiles[100][100];
int main() {
	int N,W, H;
	cin >> N >> W >> H;
	int A[100], B[100], C[100], D[100];
	for (int i = 0; i < W; ++i)
		cin >> A[i] >> B[i];
	for (int i = 0; i < H; ++i)
		cin >> C[i] >> D[i];
	for (int y = 0; y < H; ++y) {
		for (int x = 0; x < W; ++x) {
			tiles[y][x] = 0;
		}
	}
	for (int i = 0; i < N; ++i) {
		for (int y = C[i]; y < D[i]; ++y) {
			for (int x = A[i]; x < B[i]; ++x) {
				tiles[y][x]++;
			}
		}
	}
	int tile_max = 0;
	for (int y = 0; y < H; ++y) {
		for (int x = 0; x < W; ++x) {
			if (tile_max < tiles[y][x]) {
				tile_max = tiles[y][x];
			}
		}
	}
	cout << tile_max << endl;
	return 0;
}

これをいもす法で解きたい

# include<iostream>
using namespace std;
int tiles[100][100];
int main() {
	int N,W, H;
	cin >> N >> W >> H;
	int A[100], B[100], C[100], D[100];
	for (int i = 0; i < W; ++i)
		cin >> A[i] >> B[i];
	for (int i = 0; i < H; ++i)
		cin >> C[i] >> D[i];
	for (int y = 0; y < H; ++y) {
		for (int x = 0; x < W; ++x) {
			tiles[y][x] = 0;
		}
	}
	//重みの加算
	for (int i = 0; i < N; ++i) {
		tiles[C[i]][A[i]]++;
		tiles[C[i]][B[i]]--;
		tiles[D[i]][A[i]]--;
		tiles[D[i]][A[i]]++;
	}
	//横方向への累積和
	for (int y = 0; y < H; ++y) {
		for (int x = 1; x < W; ++x) {
			tiles[y][x] += tiles[y][x - 1];
		}
	}
	//縦方向への累積和
	for (int y = 1; y < H; ++y) {
		for (int x = 0; x < W; ++x) {
			tiles[y][x] += tiles[y - 1][x];
		}
	}
	int tile_max = 0;
	for (int y = 0; y < H; ++y) {
		for (int x = 0; x < W; ++x) {
			if (tile_max < tiles[y][x]) {
				tile_max = tiles[y][x];
			}
		}
	}
	cout << tile_max << endl;
	return 0;
}

abc 080 D

# include<iostream>
# include<vector>
# include<algorithm>
# include<string>
# include<map>
# include<math.h>
# include<queue>
# include<deque>
# include<stack>
# include<cstdio>
# include<utility>
# include<set>
# include<list>
# include<cmath>
# include<stdio.h>
# include<string.h>
# include<iomanip>
using namespace std;
# define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
# define REP(i, n) FOR(i, 0, n - 1)
# define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
////////////////////////////////////////

int main() {
	int N, C; cin >> N >> C;
	int dp[31][100100];
	int table[31][100100];
	memset(dp, 0, sizeof(dp));
	memset(table, 0, sizeof(table));
	for (int i = 0; i < N; ++i) {
		int s, t, c;
		cin >> s >> t >> c;
		dp[c][s]++;
		dp[c][t + 1]--;
	}
	for (int i = 1; i <= C; ++i) {
		for (int j = 1; j < 100100; ++j) {
			dp[i][j] += dp[i][j - 1];
		}
	}
	for (int i = 1; i <= C; ++i) {
		for (int j = 0; j < 100100; ++j) {
			if (dp[i][j] > 1) {
				dp[i][j] = 1;
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < 100100; ++i) {
		int count = 0;
		for (int j = 1; j <= C; ++j) {
			count += dp[j][i];
		}
		ans = max(ans, count);
	}
	cout << ans << endl;
	return 0;
}