Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

ABC_166_E - This Message Will Self-Destruct in 5s #48

Open
zeikar opened this issue Oct 2, 2022 · 0 comments
Open

ABC_166_E - This Message Will Self-Destruct in 5s #48

zeikar opened this issue Oct 2, 2022 · 0 comments
Assignees
@zeikar
Labels
study Study

Comments

@zeikar
Copy link
Owner

zeikar commented Oct 2, 2022

Problem link

https://atcoder.jp/contests/abc166/tasks/abc166_e

Problem Summary

배열에서 두 원소를 선택할 때 값의 합이 인덱스의 차이의 절댓값이 되는 경우의 수를 구하는 문제.

Solution

뭔가 수학적인 것이 보일 듯 해서 정리를 해봤다.

Ai + Aj == | j - i |

j > i로 고정하고 절댓값을 풀면 j - Aj = i + Ai 가 되는데 i + Ai가 몇개인지 계속 더해주면서 j에 대해 j - Aj 개수를 더해주면 된다.

참고: https://codeforces.com/blog/entry/76833?#comment-614685

Source Code

#include <iostream>
#include <map>
using namespace std;

int a[200000];
map<int, int> diff;

int main() {
	int n;
	cin >> n;

	long long res = 0;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];

		res += diff[i - a[i]];
		diff[a[i] + i]++;
	}


	cout << res << endl;
}
@zeikar zeikar added the study Study label Oct 2, 2022
@zeikar zeikar self-assigned this Oct 2, 2022
zeikar added a commit that referenced this issue Oct 2, 2022
@zeikar
Create ABC_166_E.cpp
ac85282 
#48
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@zeikar zeikar

Labels
study Study
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@zeikar