atcoder abc 177

a,b번은 빠르게 풀어냈는데 c번에서 망해버린 라운드

난 c번을 기하적으로 생각 못했고, 다만 수리적으로 전체의 제곱에서 a^2+b^2+...요걸 빼주고 /2를 해주면 된다는 사실을 알아냈다

하지만 이 로직을 그대로 구현하면 오버플로우가 발생한다

실제로 앳코더 오피셜에서 선생님이 이렇게 풀면 long long 형에서는 오버플로우라고 설명하고 있다

오피셜에서는 기하적으로 좀 더 생각해서, 합이 계단처럼 증가하는 모습을 확인할 수 있고, 그 형태를 구현해 냈다

앳코더 오피셜 솔루션

 

참고로 저스티스후이님은 오버플로우 없이 1번 로직으로 구현하셨다. 대단하다.....

dp로 구현한 애도 있다 다들 구현력이 어마어마하다.