#728 div2 6/26

https://codeforces.com/contest/1541

Dashboard - Codeforces Round #728 (Div. 2) - Codeforces

A Pretty Permutations

 

수열에서 자신의 수와 자신의 인덱스의 차이의 합이 최소가 되도록 주어진 길이의 수열을 만드는 문제 

오랜만에 코포를 하다보니깐 그냥 결과만 보고 n을 앞에 두고 나머지 전개하는 코드를 짜고 제출하였지만 WA

짝이면 번갈아가면서 

홀이면 세개를 보기처럼 만든 뒤 번갈아가면서 

 

B Pleasant Pairs

 

i<j 에 대해서 ai*aj = i+j 가 되도록 하는 갯수 

네개의 변수처럼 보이지만 실제로는 세 개의 고정 값에 aj만 찾으면 되는 문제 

i+j의 값이 ai의 배수가 되는 j만 확인하면 됨 

수들이 모두 distinict하므로 최악의 경우는 1 부터 n의 수들로 이루어진 케이스 

n/1 + n/2 + ... + n/n-1 + n/n 모두 더하면 O(nlogn) 

 

대회때는 nlogn을 계산하지는 못 했지만 n^2보다 훨씬 작다는 것은 인지하였기에 그냥 풀었다. 

처음 j가 될 수 있는 값을 그냥 ++해서 두번의 시초가 발생 

long long을 안 써서 WA가 떴지만 오버플로가 난걸 어케 알까 

 

그래서 그냥 또 탈주 30분 유튜브 정주행 후 오버플로 발견 

 

C Great Graphs

 

대충 어떤 문제인지를 인지하긴 했었다. 대회 때 생각한건 무조건 -max값 아닌가 생각하였다가 

보기에서 아닌걸 보고 바로 탈주... 병신 

 

우선 주어진 값들로 이어지려면 정렬한 상태에서 index 기준 0 -> 1 -> 2 ...

이런식으로 계속해서 간선을 이어나가면 된다. 

+간선은 이런식으로 이어나가고, -간선은 +간선 역방향에 합은 0이니깐  

이제 그어지지 않은 모든 케이스를 계산하면 된다. 

 

근데 이 계산이 좀 까다롭다. 

개인적으로는 모두 sum에 저장하고 따로 계산을 하였지만 

 

자주 참고하는 jiangly 님의 코드를 보면 

 

1. for (int i = 0; i < n; i++) {
2. ans += i64(d[i]) * (std::max(0, n - i - 2) - std::max(0, i - 1));
3. }

이런식으로 sum을 사용하지 않고도 계산이 가능한 문제였다. 

물론 내가 이런 방식의 계산을 앞으로도 못 할것 같지만 

 

총합에 대한 접근을 하면 저런 코드가 생각이 떠오를지도 모르겠다는 생각이 든다. 

 

몇 번째 다짐인지는 모르겠지만 이번에는 진짜 공부를 할 수 있을 것 같다. 컨디션도 그렇고, 상황도 그렇고, 의지도 그렇고, 그래서 진짜 이번에도 안하면 넌 병신 머저리