3.차이 살펴보기

최근 코포에서 이런 문제가 나왔었다.

 

https://codeforces.com/contest/1687/problem/C

 

어려운 문제였는데, 아이디어 자체가 발상적이기도 하고 몇번 본거 같아서 적어본다.
(사실 대회때는 나올때마다 틀렸음.)

 

두 수열에 관한 연산을 시행할 때 두 수을 보는게 아니라, 두 수열의 차이를 보자.

라는게 핵심 아이디어 이다.

 

위의 관찰만 하게 되면, 구간의 연산들이 어떻게 바뀌는지 쉽게 살펴볼 수 있다.

두 구간의 합이 같을 때, Ai=Bi를 시행하는 것은 Ci=Ai-Bi라는 수열을 생각하면,

Ci의 구간합이 0이되는 구간에, Ci들을 전부 0으로 바꿔준다는 것이다. 이를 이용하면 문제가 

새롭게 바뀌게 되고, 쉽게 풀린다.

 

https://codeforces.com/problemset/problem/1634/F

위의 문제도 마찬가지이다.
위 문제의 핵심 아이디어도 두 수열의 차이 Ai-Bi =Ci 로 새롭게 정의하는 것이다.

 

굉장히 어려운 유형인듯 하다.

(애초에 둘다 div2 F이다.)

이런 문제들 추천 부탁드립니다.. ㅎㅎ...