Cutting

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/30449 🧐 관찰 및 접근 # $R(n)$의 길이는 몇일까? $R(1) = 2$이고, $R(k) = R(k-1) + k$와 서로소인 자연수의 개수 인 것 같다. 오일러 피함수의 부분합 개수랑 같다. 암튼 나이브하게 돌려보니, 7600459개가 나온다. 이걸 0.5초안에 이걸 정렬하고 찾을?수?있을까? ㅋㅋ 수열이 좌우로 대칭인걸 고려하면 380만개정도만 정렬해도 될거같긴 한데… 그래도 빡세보인다. 0.5초라서 흠.. 답에 대한 이분탐색이 될까? 사실 깔끔하게 이분탐색 하기 위해선, 정수조건으로 바꾸려면 1~5000의 LCM을 구해야 한다.. 진짜 개에바 $10^{-4}$에 대한 정밀도까지만 하면 되지 않을까? 해봤자 가장 작은 수는 $\frac{1}{5000}$이니까… 라기엔 두 분수의 차는 결국 더 빡세지네. 해봤자 $\frac{1}{5000*4999}$인거같긴 한데… 아니 잠깐만, 생각해보니까 1~5000에 대해서 따로 정렬하면 시간복잡도가 꽤나 줄어드는것같다. 이렇게 해서 답에 대한 이분탐색을 해볼까..? 다 실패하고, nth_element와 short와 pragma Ofast와 Clang까지 섞은 최적화로 풀엇다… 하 이게 뭐하는 문제냐 ㄱ- 헉, 앞에 최대공약수를 구하는 부분을 반복문으로 전처리하면 훨씬 빠르게 돈다. 거기가 병목이었다니 💻 풀이 # 코드 (C++): void solve(){ int N, K; cin >> N >> K; vector<pair<short,short>> v; v.reserve(N * N / 2); v.push_back({0, 1}); v.push_back({1, 1}); rep(i, 1, N+1) rep(j, i+1, N+1){ if(__gcd(i, j) != 1) continue; v.push_back({(short)i, (short)j}); } int sz = (int)v.size(); if(K*2 > sz){ K = sz - K + 1; nth_element(v.begin(), v.begin() + K - 1, v.end(), [](auto& a, auto& b){ return a.first * b.second > a.second * b.first; }); } else { nth_element(v.begin(), v.begin() + K - 1, v.end(), [](auto& a, auto& b){ return a.first * b.second < a.second * b.first; }); } cout << v[K-1].first << " " << v[K-1].second << '\n'; } 🔒 구현 코드 잠금