1. counting pairs

0. counting pairs라고 이름을 붙이긴 했는데, 조건이 있고 조건을 만족하는 $(i,j)$ 쌍들을 찾아주면 된다.

 

조건을 변형시켜서, map으로 count해주는 방법을 최근에 많이 사용하였다.

map이라는 방법론적인 측면은 제껴두고, 어떻게 문제를 접근할 건지를 위주로 살펴보자.

 

우선 기본문제부터 가져와봤다.

 

 

 

https://codeforces.com/contest/1520/problem/D

Problem - D - Codeforces

 

1. div3의 D번 문제이다.

 

$a_j-a_i=i-j$ 를 만족하는 pair들을 찾는 간단한 문제.
그냥 brute force 하면 $O(n^2)$의 시간복잡도를 가질 것이고 매우 비효율적이다.

 

그런데 식을 이렇게 바꿔보자. $a_j+j=a_i+i$
문제를 해결하기 쉬워 보이지 않는가?

$f(x)=a_x+x , f(i)=f(j)$
이런 식으로 문제를 변형할 수 있다. 

그럼 i를 iterate하면서 map에 f(i)를 넣어주고 탐색을 해주면 쉽게 해결가능하다.
첫 문제니까 소스는 첨부해놓겠다.

void solve() {
	cin >> n;
	v.resize(n);
	map<ll, ll>mp;
	for (int i = 0; i < n; i++)cin >> v[i];
	b = 0;
	for (int i = 0; i < n; i++) {
		a = v[i] - i;
		if (mp.find(a) == mp.end())mp.insert({ a,1 });
		else mp.find(a)->second++;
		b += mp[a] - 1;
	}
	cout << b << '\n';
}

 

위 문제로 조금 지레 짐작 해보자면, 대칭식꼴로 나올때, 우리가 적절히 $f(a_i)=f(a_j)$로 변형을 시켜버리자! 이말이다.
조금 조심해야 할 점은 조건식 자체가 등호가 아니라 부등호가 나오면 문제 자체가 아예 달라지니 경계해야 한다. (쿼리와 합쳐져서 고인물 알고가 나오는걸 많이 봤다...)

overkill이긴 한데... CHT를 공부했다면 약간 비슷한 부분이 있음을 느낄 것이다. 상황 자체가.

 

 

 

2. 또 이런테크닉 자체를 이미 우리는 많이 접해봤다. 언제? with prefix sum,range sum.

https://www.acmicpc.net/problem/10986

10986번: 나머지 합

 

참 유명한 문제다. 맞은 사람이 1000명이 넘어가니까 말이다.

이 문제도 똑같이 counting pairs로 볼 수 있다. $f(i)=pre(i)$ %M 으로 본다면 말이다.
그러면 또 f(i)들을 맵에 넣으면서 카운팅 할수 있다! 참 쉽죠? 

 

practice 
https://codeforces.com/problemset/problem/1215/B 

+,- 두 상태뿐이라 map안써도 된다. overflow조심하자.

https://codeforces.com/problemset/problem/742/B

map 쓰면 그냥 된다. 기본문제다.

 

 

 

 

3. 조금 더 harder version으로 가보자.

https://atcoder.jp/contests/arc119/tasks/arc119_c

 

 

결정적인 관찰을 해보면, operation을 시행할때마다 홀짝 index들의 합은 바뀌지 않는다. 또 적절히 연산을 섞어주면 0으로 만들수 있음이 보장된다. 홀짝 index들의 sum이 같다면. 그럼 어떻게 찾을까?

홀수 index들에 대해서는 -1을 곱해주고 문제를 재해석하면, 구간합이 0인 구간의 개수이다. map으로 적절히 counting 할 수 있다. 
쉽지많은 않다. 적절한 관찰이 필요한 문제였다.


https://codeforces.com/contest/1189/problem/E
사실상 이 글을 쓰는 계기가 된 문제 ㅋㅋ. 대칭식이라는 것이 하나의 중요한 관찰이다. 
스포가 될 수 있으니 .. 풀이는 접어 놓겠다. 난 이문제를 풀때 소수라는 특징을 가지고 별 이상한 짓을 많이 했는데... 사실 그보다 counting pairs의 기본 특징에서 바라봤다면 더 수월하게 접근할 수 있을것 같다.

양변에 $a_i-a_j$를 곱한다.(...) gumgood님이 알려주신 풀이.. 갓 풀이다. $f(x)$설정 자체도 매우 간단하다..

 

practice
https://codeforces.com/contest/1527/problem/C

https://www.acmicpc.net/problem/1797

https://www.acmicpc.net/problem/21757

https://codeforces.com/problemset/problem/1569/D

다음엔 game에 대해 써볼 예정이다.

 

last_update 2021.09.11