2019 NYPC 예선 후기 및 간단한 풀이

작성일 | In

2017년에는 80점짜리 1문제 풀어서 티셔츠 받고, 2018년에는 3스테이지까지 풀고 체력이 못 버텨서 티셔츠만 받고 포기했었습니다.
결국, 제대로 참가한 건 올해가 처음입니다. 근데 올해는 여름학교때문에 처음 2일을 날려먹었네요. 그래도 1스테이지니까 상관 없어요.

작년에 비해 난이도가 쉽다/어렵다 같은 말이 많은 것 같은데, 저는 딱히 생각 안 하고 있습니다. 그냥 풀 수 있으면 풀고 못 풀면 던지고…

점수는 연습문제 제외 2000점 만점에 1707점입니다. 본선을 갈 수 있는지는 모르겠네요.
작년에는 3000점 만점에 2100점이면 갔다는데 올해는 작년이랑 난이도도 다르고, 문제 배점도 달라서 예측하기가 어렵습니다:(

연습문제 - 비밀번호 검사

문제에서 요구하는대로 코드를 짜면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	string s; cin >> s;
	int n = s.size();
	if(n < 8 || n > 15){
		cout << "invalid"; return 0;
	}
	int A = 0, a = 0, num = 0, other = 0;
	for(auto i : s){
		if('A' <= i && i <= 'Z') A++;
		else if('a' <= i && i <= 'z') a++;
		else if('0' <= i && i <= '9') num++;
		else other++;
	}
	if(A * a * num * other){
		cout << "valid";
	}else{
		cout << "invalid";
	}
}

연습문제 - 숫자 인식하기(output only)

파일을 윈도우 메모장으로 열면 줄바꿈이 제대로 되지 않습니다. 다른 에디터로 열고 눈으로 풀면 됩니다.

1스테이지 - 요리 제작

i번째 재료의 개수를 Ai, 스테이크 하나를 만드는데 필요한 i번째 재료의 개수를 Bi라고 합시다.
정답은 당연히 min(floor(Ai/Bi))가 됩니다. Bi가 0인 경우를 조심합시다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	vector<int> v(n);
	for(int i=0; i<n; i++) cin >> v[i];
	int ans = 1e9+7;
	for(int i=0; i<n; i++){
		int t; cin >> t;
		if(!t) continue;
		ans = min(ans, v[i]/t);
	}
	cout << ans;
}

1스테이지 - 달팽이 게임

이상하게 N <= 5에서 WA가 나오길래 N <= 5인 경우는 하드코딩을 했습니다.
달팽이 배열을 구현하면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <bits/stdc++.h>
using namespace std;

int arr[1010][1010];
int n;

int arr3[4][4] = {
	{0, 0, 0, 0},
	{0, 1, 2, 3},
	{0, 8, 9, 4},
	{0, 7, 6, 5}
};

int arr4[5][5] = {
	{0, 0, 0, 0, 0},
	{0, 1, 2, 3, 4},
	{0, 12, 13, 14, 5},
	{0, 11, 16, 15, 6},
	{0, 10, 9, 8, 7}
};

int arr5[6][6] = {
	{0, 0, 0, 0, 0, 0},
	{0, 1, 2, 3, 4, 5},
	{0, 16, 17, 18, 19, 6},
	{0, 15, 24, 25, 20, 7},
	{0, 14, 23, 22, 21, 8},
	{0, 13, 12, 11, 10, 9}
};

void f(){
	int k; cin >> k;
	for(int i=1; i<=3; i++){
		for(int j=1; j<=3; j++){
			if(arr3[i][j] == k) cout << j << " " << i;
		}
	}
}

void g(){
	int k; cin >> k;
	for(int i=1; i<=4; i++){
		for(int j=1; j<=4; j++){
			if(arr4[i][j] == k) cout << j << " " << i;
		}
	}
}

void h(){
	int k; cin >> k;
	for(int i=1; i<=5; i++){
		for(int j=1; j<=5; j++){
			if(arr5[i][j] == k) cout << j << " " << i;
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	if(n == 3){
		f(); return 0;
	}
	if(n == 4){
		g(); return 0;
	}
	if(n == 5){
		h(); return 0;
	}
	int i = 1, j = 1;
	int d = 1;
	memset(arr, -1, sizeof arr);
	for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) arr[i][j] = 0;
	int cnt = 0;
	while(cnt < n*n){
		while(1){
			arr[i][j] = ++cnt;
			//cout << i << " " << j << " " << cnt << "\n";
			if(!arr[i][j+d]) j += d;
			else break;
		}
		i += d;
		while(1){
			arr[i][j] = ++cnt;
			//cout << i << " " << j << " " << cnt << "\n";
			if(!arr[i+d][j]) i += d;
			else break;
		}
		d = -d;
		j += d;
	}

	int k; cin >> k;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			if(arr[i][j] == k){
				cout << j << " " << i;
				return 0;
			}
		}
	}
}

1스테이지 - 최대 HP

3번 쿼리가 들어오면 체력이 최대가 됩니다.
그 상황을 잘 캐치합시다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int h, t; cin >> h >> t;
	int ans = -1;
	while(t--){
		int op, a; cin >> op >> a;
		if(op == 1){
			h -= a;
		}else if(op == 2){
			h += a;
		}else if(op == 3){
			ans = h + a;
			h += a;
		}
	}
	cout << ans;
}

1스테이지 - ID 확인

문제에서 하라는 대로 하면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;

void solve(){
	string s; cin >> s;
	int cnt = 0;
	bool flag = 1;
	for(auto i : s){
		if(i == '@') cnt++;
		else if('0' <= i && i <= '9');
		else if('A' <= i && i <= 'Z');
		else if('a' <= i && i <= 'z');
		else if(i == '-' || i == '.');
		else flag = 0;
	}
	if(cnt != 1) flag = 0;
	if(s[0] == '@') flag = 0;
	if(s.back() == '@') flag = 0;
	if(flag) cout << "Yes\n";
	else cout << "No\n";
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while(t--) solve();
}

1스테이지 - 우산

문제에서 하라는 대로 하면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

int arr[11];
int ans;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, m, now; cin >> n >> m >> now;
	while(m--){
		int a, b; cin >> a >> b;
		if(!b) now = a;
		else{
			if(arr[now]){
				arr[now]--; arr[a]++;
			}else{
				ans++; arr[a]++;
			}
			now = a;
		}
	}
	cout << ans;
}

1스테이지 - 색상표(output only)

풀이 생략

2스테이지 - 약수(94점)

√B까지 소수를 구해준 뒤, 소인수분해를 해주면 됩니다.
100점 풀이도 비슷할 것 같은데 아직은 잘 모르겠습니다.

+) 아래 수식을 사용해 계산하면 100점을 받을 수 있습니다. (코드는 여전히 94점 코드입니다.)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
using namespace std;

typedef long long ll;

int arr[10101010];
ll res[10101010];
bool chk[10101010];

void era(){
	res[1] = 1;
	for(register int i=2; i<=10000000; i++) arr[i] = i, res[i] = 1;
	for(register int i=2; i<=1000000; i++){
		if(chk[i]) continue;
		for(register int j=i; j<=10000000; j+=i){
			chk[j] = 1;
			ll now = 1;
			while(arr[j] % i == 0){
				now++; arr[j] /= i;
			}
      res[j] = res[j] * now;
		}
	}
	for(register int i=2; i<=10000000; i++) if(arr[i] != 1) res[i] <<= 1;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int a, b; cin >> a >> b;
	era();
	ll ans = 0;
	for(int i=a; i<=b; i++){
		//cout << i << " " << res[i] << "\n";
		ans += res[i];
	}
	cout << ans;
}

2스테이지 - 수도관

변수 l, r을 관리할겁니다. 두 변수는 각각 현재 굵은 수도관이 존재할 수 있는 y좌표의 하한과 상한을 나타냅니다.
만약 다음 점에 이어주기 위해서 놓아야 하는 굵은 수도관이 [l, r]구간 사이에 있다면 굵은 수도관을 추가할 필요가 없고, [l, r]구간에 없다면 새로운 수도관을 추가해야 합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

int n; ll d;
vector<p> v;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> d; v.resize(n);
	for(int i=0; i<n; i++) cin >> v[i].x >> v[i].y;
	sort(all(v));

	int ans = 1;
	int l = 0, r = 1e9;
	for(int i=0; i<n; i++){
		int s = v[i].y - d, e = v[i].y + d;
		if(r < s || e < l){
			ans++;
			l = s, r = e;
			continue;
		}
		l = max(l, s);
		r = min(r, e);
	}
	cout << ans;
}

2스테이지 - 신호등

각 격자점마다 정점을 4개씩 만들어줍니다. 4개의 정점은 각각 왼쪽, 오른쪽, 위, 아래를 가리킬 때의 상태를 의미합니다.
그래프를 잘 만든 뒤, BFS 등의 알고리즘으로 최단 거리를 구해주면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
using namespace std;

int dist[808080];
int arr[1010][1010];
int n, m, k, si, sj;

int di[] = {0, -1, 0, 1};
int dj[] = {1, 0, -1, 0};

int f(int i, int j, int d){
	return 4 * (400 * i + j) + d;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> k >> si >> sj;
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			cin >> arr[i][j];
		}
	}

	int st = f(si, sj, (arr[si][sj] + k)%4);
	memset(dist, -1, sizeof dist);
	queue<int> q; q.push(st); dist[st] = k;

	while(q.size()){
		int now = q.front(); q.pop();
		int x = now;
		int d = x % 4; x /= 4;
		int i = x / 400, j = x % 400;

		for(int x=0; x<4; x++){
			int ii = i + di[x];
			int jj = j + dj[x];
			if(ii < 0 || jj < 0 || ii >= n || jj >= m) continue;
			if(d != x) continue;
			int dd = arr[ii][jj] + dist[now] + 1;
			dd %= 4;
			if(dist[f(ii, jj, dd)] != -1) continue;
			dist[f(ii, jj, dd)] = dist[now] + 1;
			q.push(f(ii, jj, dd));
		}
		int dd = (d + 1) % 4;
		if(dist[f(i, j, dd)] == -1){
			dist[f(i, j, dd)] = dist[now] + 1;
			q.push(f(i, j, dd));
		}
	}

	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			int res = 1e9+7;
			for(int d=0; d<4; d++){
				if(dist[f(i, j, d)] != -1) res = min(res, dist[f(i, j, d)]);
			}
			cout << res << " ";
		}
		cout << "\n";
	}
}

스테이지2 - 카트라이더 경험치

TSP문제와 거의 똑같은 문제입니다.
Bit DP를 잘 돌려줍시다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll g[16][16];
int n;

ll dp[16][1 << 16];

ll f(int now, int bit){
	ll &ret = dp[now][bit];
	if(ret != -1) return ret;
	if(bit == (1 << n) - 1) return 0;
	ret = 0;

	for(int i=0; i<n; i++){
		if(bit & (1 << i)) continue;
		ll now = 0;
		for(int j=0; j<n; j++){
			if(bit & (1 << j)) now += g[j][i];
		}
		ret = max(ret, f(i, bit | (1 << i)) + now);
	}
	return ret;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++) cin >> g[i][j];
	}

	memset(dp, -1, sizeof dp);
	ll ans = 0;
	for(int i=0; i<n; i++) ans = max(ans, f(i, 1 << i));
	cout << ans;
	return 0;
}

2스테이지 - 돌 밀기(output only)

풀이 생략

3스테이지 - 마비노기 인벤토리(output only, 90점)

풀이 생략

3스테이지 - 가위바위보

Union Find를 해주면서 각 집합의 크기를 구하면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;

int par[202020];
int sz[202020];

void init(){
	for(int i=0; i<202020; i++) par[i] = i, sz[i] = 1;
}

int find(int v){
	return v == par[v] ? v : par[v] = par[v] = find(par[v]);
}

void merge(int u, int v){
	u = find(u); v = find(v);
	if(u == v) return;
	if(sz[u] > sz[v]) swap(u, v);
	par[u] = v;
	sz[v] += sz[u];
}

int win[202020], lose[202020];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, m; cin >> n >> m;
	init();
	while(m--){
		int a, b; cin >> a >> b;
		win[a]++; lose[b]++;
		merge(a, b);
	}

	vector<int> v;
	for(int i=0; i<n; i++) v.push_back(i+1);
	sort(v.begin(), v.end(), [](int a, int b){
		if(sz[find(a)] != sz[find(b)]) return sz[find(a)] > sz[find(b)];
		if(win[a] != win[b]) return win[a] > win[b];
		if(lose[a] != lose[b]) return lose[a] < lose[b];
		return a < b;
	});
	cout << v[0];
}

3스테이지 - 넥슨 사진관

어떤 구간에서 홀수 번 등장하는 캐릭터가 중앙에 서게 됩니다.
세그먼트 트리에서 구간의 모든 원소를 xor한 값을 관리해주면 됩니다.
하루동안 고민하고 3분동안 코드를 짜서 맞은 문제입니다:(

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;

int tree[404040];
int bias;

void init(int n){
	for(bias=1; bias<=n; bias<<=1);
}

void update(int x, int v){
	x |= bias; tree[x] = v;
	while(x >>= 1){
		tree[x] = tree[x << 1] ^ tree[x << 1 | 1];
	}
}

int query(int l, int r){
	l |= bias; r |= bias;
	int ret = 0;
	while(l <= r){
		if(l & 1) ret ^= tree[l++];
		if(~r & 1) ret ^= tree[r--];
		l >>= 1, r >>= 1;
	}
	return ret;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n,q ;cin >> n >> q; init(n);
	for(int i=1; i<=n; i++){
		int t; cin >> t;
		update(i, t);
	}
	while(q--){
		int op, a , b; cin >> op >> a >> b;
		if(op == 1){
			update(a, b);
		}else{
			cout << query(a, b) << "\n";
		}
	}
}

3스테이지 - 회 문화의 회문화

S를 입력 받으면, S 뒤에 S를 다시 한 번 붙여줍니다. (cin » S; S += S;)
처음에는 [0, n)구간이 팰린드롬인지 확인해줍니다.
그 다음에는 [1, n+1)구간이 팰린드롬인지 확인합니다. 이는 맨 앞 글자만 맨 뒤로 보낸 것을 의미합니다.
그 다음에는 [2, n+2)구간이 팰린드롬인지 확인합니다. 이는 맨 앞 두 글자를 맨 뒤로 보낸 것을 의미합니다.
…
이런 방식으로 답을 구하면 되는데, 특정 구간이 팰린드롬인지 확인하는 것을 빠르게 해야 합니다.
이것은 manacher algorithm으로 해줄 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
using namespace std;

int p[5050505];
string s;

void odd(){
	int n = s.size();
	int r = -1, c = -1;
	for(int i=0; i<n; i++){
		if(r >= i) p[i] = min(r-i, p[c*2-i]);
		else p[i] = 0;
		while(i + p[i] + 1 < n && i - p[i] - 1 >= 0 && s[i + p[i] + 1] == s[i - p[i] - 1]) p[i]++;
		if(i + p[i] > r){
			r = i + p[i];
			c = i;
		}
	}
	int len = s.size() / 2;
	int ans = 0;
	for(int i=0; i<n; i++){
		int l = i;
		int r = i + len - 1;
		if(r >= n-1) break;
		int mid = l + r >> 1;
		if(p[mid] >= (len-1)/2){
			ans++;
		}
	}
	cout << ans;
}

void even(){
	int len = 2*s.size()+1;
	s += s;
	string ss = s;
	s = "#";
	for(auto i : ss){
		s += i; s += "#";
	}
	int n = s.size();
	int r = -1, c = -1;
	for(int i=0; i<n; i++){
		if(r >= i) p[i] = min(r-i, p[c*2-i]);
		else p[i] = 0;
		while(i + p[i] + 1 < n && i - p[i] - 1 >= 0 && s[i + p[i] + 1] == s[i - p[i] - 1]) p[i]++;
		if(i + p[i] > r){
			r = i + p[i];
			c = i;
		}
	}
	int ans = 0;
	for(int i=0; i<n; i++){
		int l = i;
		int r = i + len - 1;
		int mid = l + r >> 1;
		if(r >= n-1) break;
		if(s[mid] != '#') continue;
		if(p[mid] >= (len-1)/2){
			ans++;
		}
	}
	cout << ans;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> s;
	if(s.size() % 2 == 1){
		s += s;
		odd();
	}else{
		even();
	}
}

4스테이지 - VIP 쿠폰(58점)

permutation으로 O(N! * N)을 돌리면 17점을 받을 수 있습니다.
적당한 정렬 기준을 잡아서 정렬을 한뒤, O(n * 2^n)완전탐색을 하면 58점을 받을 수 있습니다.
58점 풀이를 dp느낌으로 하면 100점이 나올 것 같은데 잘 모르겠습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

vector<p> v;
int n;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n; v.resize(n);
	for(int i=0; i<n; i++) cin >> v[i].x >> v[i].y;
	sort(v.begin(), v.end(), [](p a, p b){
		return a.x+a.y < b.x+b.y;
	});

	int lim = 1 << n;
	ll ans = 0;
	for(int bit=0; bit<lim; bit++){
		ll now = 0;
		for(int i=0; i<n; i++){
			if(bit & (1 << i)){
				if(now+1 > v[i].x) continue;
				now += v[i].y;
			}
		}
		ans = max(ans, now);
	}
	cout << ans;
}

4스테이지 - 빨간, 파란 점 연결(0점)

못 풀었습니다.

4스테이지 - 메이플스토리 연주회(65점)

KMP + O(N^2)DP 조합으로 65점을 받을 수 있습니다.
100점 풀이는 감이 안 옵니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

string s;
ll dp[202020];
const ll mod = 1e9+7;
vector<p> v;

vector<int> getPi(string &p){
	int m = p.size(), j = 0;
	vector<int> pi(m, 0);
	for(int i=1; i<m; i++){
		while(j > 0 && p[i] != p[j]) j = pi[j-1];
		if(p[i] == p[j]) pi[i] = ++j;
	}
	return pi;
}

vector<int> kmp(string &s, string &p){
	vector<int> ans;
	auto pi = getPi(p);
	int n = s.size(), m =p.size(), j = 0;
	for(int i=0; i<n; i++){
		while(j > 0 && s[i] != p[j]) j = pi[j-1];
		if(s[i] == p[j]){
			if(j == m-1){
				ans.push_back(i-m+1);
				j = pi[j];
			}else{
				j++;
			}
		}
	}
	return ans;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	vector<string> str;
	int n; cin >> n;
	for(int i=0; i<n; i++){
		string t; cin >> t;
		str.push_back(t);
	}
	cin >> s;
	for(auto &i : str){
		auto res = kmp(s, i);
		for(auto j : res){
			v.push_back({j+1, j+i.size()});
		}
	}
	sort(v.begin(), v.end());

	for(auto i : v){
		int x = i.first;
		int y = i.second;
		if(x == 1) dp[y] = (dp[y] + 1) % mod;
		else{
			dp[y] = (dp[y] + dp[x-1]) % mod;
		}
	}

	cout << dp[s.size()];
}

5스테이지 - 메이플스토리 파티 구성

모스 알고리즘을 사용하면 쉽게 풀 수 있습니다.

중복 처리가 까다로운데, 각 직업별로 소수를 배정해준 다음에 모스 알고리즘으로 굴리면서 해싱을 하면 됩니다.
추가할 때는 곱해주고, 제거할 때는 모듈러 인버스로 잘 처리하고…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <bits/stdc++.h>
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("Ofast")
using namespace std;

typedef long long ll;

ll inv[2][101010];
const ll mod[2] = {993244853, 1505777891};
vector<ll> prime;
int chk[2020202];

ll sq;

inline void era(){
	for(register int i=2; i<2020202; i++){
		if(chk[i]) continue;
		prime.push_back(i);
		for(register int j=i+i; j<2020202; j+=i) chk[j] = 1;
	}
}

struct Hash{
	ll val[2] = {1, 1};
	Hash(){
		val[0] = val[1] = 1;
	}
	void insert(ll x){
		val[0] = val[0] * prime[x] % mod[0];
		val[1] = val[1] * prime[x] % mod[1];
	}
	void erase(ll x){
		val[0] = val[0] * inv[0][x] % mod[0];
		val[1] = val[1] * inv[1][x] % mod[1];
	}

	bool operator == (Hash &t){
		return val[0] == t.val[0] && val[1] == t.val[1];
	}
} now;

inline ll pw(ll a, ll b, ll c){
	ll ret = 1;
	while(b){
		if(b & 1) ret = ret * a % c;
		a = a * a % c;
		b >>= 1;
	}
	return ret;
}

inline void init(){
	for(register int i=0; i<101010; i++){
		inv[0][i] = pw(prime[i], mod[0]-2, mod[0]);
		inv[1][i] = pw(prime[i], mod[1]-2, mod[1]);
	}
}

struct Query{
	ll s, e, x;
	Query(){}
	Query(ll a, ll b, ll c) : s(a), e(b), x(c) {}
	bool operator < (Query &t){
		if(s/sq != t.s/sq) return s < t.s;
		return e < t.e;
	}
};

Hash res[202020];
vector<ll> v;
vector<Query> q;
int cnt[101010];

inline void Plus(ll x){
	if(cnt[x]++ == 0) now.insert(x);
}

inline void Minus(ll x){
	if(--cnt[x] == 0) now.erase(x);
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	era(); init();
	int n, qq; cin >> n >> qq; v.resize(n+1);
	sq = sqrt(n);
	for(register int i=1; i<=n; i++) cin >> v[i];

	for(register int i=0; i<qq; i++){
		ll a, b, c, d; cin >> a >> b >> c >> d;
		q.push_back({a, b, i << 1});
		q.push_back({c, d, i << 1 | 1});
	}
	sort(q.begin(), q.end());

	int s = q[0].s, e = q[0].e, x = q[0].x;
	for(register int i=s; i<=e; i++){
		Plus(v[i]);
	}
	res[x] = now;

	for(register int i=1; i<q.size(); i++){
		x = q[i].x;
		while(q[i].s < s) Plus(v[--s]);
		while(q[i].e > e) Plus(v[++e]);
		while(q[i].s > s) Minus(v[s++]);
		while(q[i].e < e) Minus(v[e--]);
		res[x] = now;
	}

	for(register int i=0; i<qq; i++){
		if(res[i << 1] == res[i << 1 | 1]) cout << "YES\n";
		else cout << "NO\n";
	}
}

5스테이지 - 카트 발사

못 풀었습니다.