Algorithm

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/34088 🧐 관찰 및 접근 # $K$로 나눈 나머지가 같다 = 고른 부분집합의 원소들의 차이가 모두 $K$의 배수이다. 그러면? 분위기상 소수만? 신경써도 되는거같다. 근데 숫자들의 차이가 $10^9$까지인데… 그러면 너무 많은데 흠 근데 일단 직관적으로, $K = 2$일때 비둘기집의 원리에 의해 답은 ${N/2}$ 이상이긴 하다. 그리고 직관적으로, 웬만한 경우에 $K$가 작을때 답이 있을 것 같다. $K$가 클때를 억지로 만들 수 있나? $K > 1000$ 쯤듸는 어떤 소수라고 하면, 억지로 만들 수 있는 것 같긴 하다. 그런데, 이때 $K$가 $N/2$개 이상의 부분집합에 대해 나머지가 같아야하므로, 다르게 말하면 어떤 두 수를 뽑앗을때 50% 이상의 확률로 $K$는 해당 수의 약수이다. 랜덤으로 풀 수 있지 않을까? 💻 풀이 # 코드 (C++): void solve(){ auto start = chrono::high_resolution_clock::now(); bitset<32000> isPrime; isPrime.set(); isPrime[0] = isPrime[1] = 0; rep(i, 2, 32000) if(isPrime[i]){ for(ll j = (ll)i*i; j < 32000; j += i) isPrime[j] = 0; } vector<int> primes; rep(i, 2, 32000) if(isPrime[i]) primes.push_back(i); int N; cin >> N; vector<ll> A(N); rep(i, 0, N) cin >> A[i]; int ans = (N+1)/2; while(1){ auto end = chrono::high_resolution_clock::now(); auto duration = chrono::duration_cast<chrono::milliseconds>(end - start); if(duration.count() > 900) break; int a = rand() % N, b = rand() % N; int diff = abs(A[a] - A[b]); vector<int> divs; for(int p: primes){ if(p*p > diff) break; if(diff % p == 0){ divs.push_back(p); while(diff % p == 0) diff /= p; } } if(diff > 1) divs.push_back(diff); for(int d: divs){ map<int, int> mp; for(auto x: A) mp[x%d]++; for(auto [_, c]: mp) ans = max(ans, c); } } cout << ans; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/25563 🧐 관찰 및 접근 # 일단 세개를 따로 구하면 되는 것 같다. XOR이 제일 쉬워보인다. XOR은 역연산이 존재하므로, $A_i \oplus A_j = K$를 만족하는 $A_j$는 $A_i \oplus K$로 구할 수 있다. $A_i \leq 1\,000\,000$이므로 그냥 구하면 될듯. 양쪽에서 구했으니 2로 나누는것만 조심하면 되겠다. $K = 0$일때를 주의하자. AND를 다음으로 봐보자. $A_i, A_j$ 모두 $K$와 and연산한 결과는 $K$여야 한다. 그리고 $A_i - K, A_j - K$는 and 연산한 결과가 $0$이어야 한다. 숫자 $N$개에서 두 수의 and 결과가 $0$인 조합 개수를 빠르게 구할수가 있나? 이 같은 아이디어로 OR도 해결할 수 있는 것 같으니, 이걸 고민해보자. 약간 포함배제같은맛으로 될라나? 일단 쉽게 $A_i$에서 $k$번째 비트 하나가 켜져있다고 해보자. 그러면 나머지들에서 $k$번째 비트가 꺼져있기만 하면 된다. 이건 뭐 $k$번째 비트가 켜져있는 / 꺼져있는 집합으로 하면 될틴데,… $A_i$에서 $k_1, k_2$번째 비트 두개가 켜져있다고 해보자. 이번에는 나머지들에서 $k_1, k_2$ 번째 비트 모두가 꺼져있어야 한다. 그거 개수는 $k_1$이 켜진거 + $k_2$가 켜진거 - $k_1, k_2$가 켜진것으로 구할 수 있고, 이거까진 또 쉽게 되는거같기도? 왜냐면 둘다 켜진건 처음에 보고있으니까. $A_i$에서 $k_1, k_2, k_3$ 세개가.. 나머지들에서 세개가 다 꺼져있어야.. 근데 이건 각자 더하고 둘둘 빼고 세개 더하고.. 는 까다롭네. 앞에서 하면서 저장해왔으면 되는거같긴 한데.. 그런데, 이렇게 하다보면 결국 비트가 20개정도니까… 어? 되는거같기도 한데? 어떻게 풀 수 있나 고민해봤는데, 결국 각 비트 자체 대해서 저장한다음에, 다른 배열에서 이를 이용해서 만들어보자. $\text{cntExact}$를 해당 비트가 그대로 켜져있는것 (그 숫자 자체) $\text{cntOr}$을 켜져있는 비트중 하나라도 켜져있는것이라고 생각하면, 이걸 앞에서 얻은것들로 계산할 수 있을 것 같다. 이를 SOS_DP 로 알려져있다. 두 수의 and 결과가 0인 것의 개수는, $A_i$를 정했다면 ${A_i}$ 를 뒤집은 비트에서 부분집합의 합과 같다. OR은 어떻게 풀릴까? $A_i, A_j$ 모두 $K$랑 or 연산한 결과가 $K$여야 한다. 예를들어 목표가 $1101$이고, $A_i$가 $1000$이라면 $A_j$는 $?101$이어야 한다. $A_i$에서 꺼진 비트는 모두 켜져있어야 한다. 부분집합의 합을 구할때, $A$를 뒤집어서 저장하는 것으로 가능할 것 같다. $?$ 인 부분들에 대해 부분집합의 합을 계산하면 된다. 💻 풀이 # 코드 (C++): void solve(){ int N, K; cin >> N >> K; vector<int> A(N); rep(i, 0, N) cin >> A[i]; int all1 = (1 << 20) - 1; // count and { ll ans = 0; vector<int> cnt(1<<20, 0), SOS(1<<20, 0); rep(i, 0, N) if((A[i] & K) == K){ cnt[A[i] - K]++; SOS[A[i] - K]++; } rep(i, 0, 20) rep(mask, 0, 1<<20) if(mask & (1<<i)) SOS[mask] += SOS[mask^(1<<i)]; rep(i, 0, N) if((A[i] & K) == K){ int mask = all1 - (A[i] - K); ans += SOS[mask]; } ans -= cnt[0]; cout << ans/2 << ' '; } // count or { ll ans = 0; vector<int> cnt(1<<20, 0), SOS(1<<20, 0); rep(i, 0, N) if((A[i] | K) == K){ cnt[A[i]]++; SOS[K - A[i]]++; } rep(i, 0, 20) rep(mask, 0, 1<<20) if(mask & (1<<i)) SOS[mask] += SOS[mask^(1<<i)]; rep(i, 0, N) if((A[i] | K) == K){ ans += SOS[A[i]]; } ans -= cnt[K]; cout << ans/2 << ' '; } // count xor { ll ans = 0; vector<int> cnt(1<<20, 0); rep(i, 0, N) cnt[A[i]]++; rep(i, 0, N) ans += cnt[A[i] ^ K]; if(K == 0) ans -= N; cout << ans/2; } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/2042 🧐 관찰 및 접근 # 자명한 세그먼트 트리 연습 문제이다. 기본적으로 업데이트가 없이 구간의 합을 구해야 한다면, 이는 누적합으로 빠르게 해결할 수 있다. 이때 합을 구하는 쿼리는 $O(1)$, 업데이트는 $O(N)$이다. 업데이트를 빠르게 하기 위해선, 합을 나이브하게 구하는 방법이 있겠다. 이때 합을 구하는 쿼리는 $O(N)$, 업데이트는 $O(1)$이다. 버킷을 잘 나누어서, 두 방법의 이득만을 취하면 제곱근 분할법을 이용해서 $O(Q\sqrt{N})$까지 줄일 수 있고, 해당 문제에서는 $N \leq 10^6$이므로 약 2천만정도에 바운드된다. 지금과 같이 두 노드를 합치는 것이 직관적이고 용이할 경우에는 세그먼트 트리를 쓸 수 있으며, 두 노드를 이용해 역원과 역연산을 정의할 수 있는 경우 펜윅트리도 이용할 수 있다. 💻 풀이 # 코드 (C++): void solve(){ ll N, M, K; cin >> N >> M >> K; SegmentTreeSum ST(N); rep(i, 0, N){ ll x; cin >> x; ST.set(i, x); } ST.build(); rep(i, 0, M+K){ ll a, b, c; cin >> a >> b >> c; if(a == 1) ST.update(b-1, c - ST.query(b-1, b-1)); else cout << ST.query(b-1, c-1) << "\n"; } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/14504 🧐 관찰 및 접근 # 수열과 쿼리 1과 비슷한데, 업데이트 쿼리가 추가되었다. 같은 방법으로 풀되, 배열 정렬 말고 multiset으로 관리하면 되지 않을까? 헉, multiset에서 거리를 계산할때 쓰는 distance함수가 $O(N)$이라고 한다!! 어차피 버킷의 크기가 작으니, 나이브하게 정렬해버려도 문제가 없겠다. 💻 풀이 # 코드 (C++): const int sq = 700; struct sqrtDecomposition{ int N; vector<int> A; vector<vector<int>> bucket; sqrtDecomposition(int N, vector<int> &A): N(N), A(A){ bucket.resize((N-1)/sq+1); rep(i, 0, N) bucket[i/sq].push_back(A[i]); for(int i = 0; i < (int)bucket.size(); i++) sort(all(bucket[i])); }; void update(int i, int val){ int b = i/sq; auto it = lower_bound(all(bucket[b]), A[i]); *it = val; A[i] = val; sort(all(bucket[b])); } int query(int L, int R, int val){ int ret = 0; for(int i = L; i <= R;){ if(i%sq == 0 && i+sq-1 <= R){ ret += bucket[i/sq].end() - upper_bound(all(bucket[i/sq]), val); i += sq; } else{ ret += A[i] > val; i++; } } return ret; } }; void solve(){ int N; cin >> N; vector<int> A(N); rep(i, 0, N) cin >> A[i]; sqrtDecomposition sd(N, A); int Q; cin >> Q; while(Q--){ int op; cin >> op; if(op == 1){ int i, j, k; cin >> i >> j >> k; cout << sd.query(i-1, j-1, k) << "\n"; } else{ int i, k; cin >> i >> k; sd.update(i-1, k); } } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/13537 🧐 관찰 및 접근 # 부분수열에서 물어보는 쿼리가 있으니, 세그먼트 트리가 먼저 생각이 난다. 그런데 쿼리가 좀 까다롭다. 이럴때, $N, M$모두 10만이므로 제곱근 분할법을 한번 생각해보자. 수가 $C$개 들어있는 버킷을 $B$개 만든다면 $(C = N/B$), 버킷 내의 수들을 정렬하는데 $O(B \times C\log{C})$, 버킷들에 대해 답을 구하는데에 $O(B \times \log{C})$ 따라서 이들을 최소화하기 위해서는 적당히 $\sqrt{N}$보다 약간 크게 잡으면 될 것 같다. 💻 풀이 # 코드 (C++): const int sq = 700; struct sqrtDecomposition{ int N; vector<int> A; vector<vector<int>> bucket; sqrtDecomposition(int N, vector<int> &A): N(N), A(A){ bucket.resize((N-1)/sq+1); rep(i, 0, N) bucket[i/sq].push_back(A[i]); for(int i = 0; i < (int)bucket.size(); i++) sort(all(bucket[i])); }; int query(int L, int R, int val){ int ret = 0; for(int i = L; i <= R;){ if(i%sq == 0 && i+sq-1 <= R){ ret += bucket[i/sq].end() - upper_bound(all(bucket[i/sq]), val); i += sq; } else{ ret += A[i] > val; i++; } } return ret; } }; void solve(){ int N; cin >> N; vector<int> A(N); rep(i, 0, N) cin >> A[i]; sqrtDecomposition sd(N, A); int Q; cin >> Q; while(Q--){ int i, j, k; cin >> i >> j >> k; cout << sd.query(i-1, j-1, k) << "\n"; } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/10868 🧐 관찰 및 접근 # 구간 최솟값을 $M$번 구하는 문제이다. 구간합은 누적합 배열을 이용해서 $O(1)$에 구할 수 있다. 하지만 구간 최솟값은 역원과 역연산이 없기에, 누적 최솟값 배열을 이용하기 곤란하다. 세그먼트 트리를 이용해서 구간 $O(logN)$개의 구간만을 관리하는 방법으로 풀 수 있겠다. 하지만, 업데이트가 없는 경우 희소 배열을 이용해서 $O(1)$에 구할 수 있음이 알려져있다. 💻 풀이 # 코드 (C++): struct RMQ{ // Range Minimum Query int N, H; vector<vector<int>> table; RMQ(int N, vector<int> &arr): N(N){ H = 1; while((1 << H) <= N) H++; table.assign(N, vector<int>(H)); rep(i, 0, N) table[i][0] = arr[i]; rep(j, 1, H) rep(i, 0, N){ int right = i + (1 << (j-1)); if(right < N) table[i][j] = min(table[i][j-1], table[right][j-1]); else table[i][j] = table[i][j-1]; } } int query(int l, int r){ // [L, R] r++; int k = 31 - __builtin_clz(r-l); return min(table[l][k], table[r-(1 << k)][k]); } }; void solve(){ int N, M; N = getu<6, int>(); M = getu<6, int>(); vector<int> A(N); rep(i, 0, N) A[i] = getu<10, int>(); RMQ rmq(N, A); while(M--){ int l, r; l = getu<6, int>(); r = getu<6, int>(); putu<10, int>(rmq.query(l-1, r-1)); } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/25229 번역 번역 # 문제 # 방향이 없는 간선으로 이루어진 트리가 있으며, 각 노드는 정수 값을 가지고 있습니다. 인접한 두 노드의 값의 최대공약수(GCD)가 $1$보다 엄밀히 클 때, 이 두 노드를 **GCD-조화롭다(GCD-harmonic)**고 합니다.

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/15896 🧐 관찰 및 접근 # bitwise and들의 합과, 합들의 bitwise and 값을 구해야한다. 일단 앞에껏부터 해보자. $N$은 100만??이다. 개크네 모든 $(A_i \& B_j)$의 합을 1999로 나눈 나머지 나이브하게 제곱은 될 리가 없다. bitwise and의 특성을 생각해보자. $A_i$에서도, $B_j$에서도 켜져있어야 한다. 각 비트에 대해서 생각하면, $A$에서 해당 비트가 켜진 개수 * $B$에서 해당 비트가 켜진 개수와 같이 구할 수 있을 것 같다. 전처리에 $O(N\times29)$, 계산하는데에 $O(29)$가 걸릴 것 같다. 모든 $(A_i + B_j)$의 bitwise and 연산 값 자 이제 이게 문젠거같은데… 합이 이슈다. 받아올림이 있다보니 조금 신경쓰인다. 다시한번 bitwise and의 특성을 생각해보자. 모두 켜져있어야 한다는건, 모든 순서쌍 $(i, j)$에 대해 $A_i + B_j = C_k$라고 할때, 어떤 $C_k$의 비트가 꺼져있으면, 정답에서 해당 비트는 꺼진다. 일단 첫번째 비트에 대해서는 쉽게 구할 수 있는 것 같다. 더했을때 모두 $1$이 남기 위해선 $1 + 0, 0 + 1$ 두가지만 가능하기에, 개수가 $(N, 0), (0, N)$이 아니라면 비트가 꺼질 수밖에 없다. 하지만 해당 윗 비트부터는 받아올림이 생긴다… $11_2 + 01_2 = 100_2$ 와 같이 $(1, 0)$이었음에도 비트가 꺼질 수 있다. 혹은 $11_2 + 11_2 = 110_2$와 같이 $(1, 1)$이었으메도 비트가 켜질 수 있다. 하 이게 무슨 의미지? 예를들어 $4$의자리 비트가 켜져있나? 라는 질문은 $8$로 나눈 나머지들의 합에 대해, 나머지가 모두 $4$ 이상인가? 하는 질문과 같긴 하다. $0$$3$, $8$$11$은 안된다는거지. 그 사이에 값이 있는지 없는지를 체크할 수가 있나? 일반화시키면, $2^k$의 비트가 켜져있는건 $\mod 2^{k+1}$ 에 대해 나눈 애들의 합에 대해 $0 \leq s < 2^k$ 또는 $2^{k+1} \leq s < 2^{k+1} + 2^k$ 인게 있으면 안된다. 이걸 각 비트에 대해 한다고 하면 그래도 정렬해서 이분탐색으로 구할 순 있을거같긴 한데…… $N$ 제한이 100만이라 $O(29 \times N\log{N})$을 하면 죽여버리겠다는 말과 같은 것 같다. 어? 근데 내가 필요한건, 비트단위로 하나씩 확장해나가면서 정렬하는거다. 이게 바로 Radix Sort 아닌가? 게다가 배열 두개로 쪼개져있을때, 다른 배열에서 하나하나 합이 저 안에 들어있는지 확인하는건 그리디하게 0/1로 쪼개진 두 배열의 맨앞/맨뒤를 보는것만으로 해결할 수 있는 것 같다. 덱을 이용해서 관리해보자. 💻 풀이 # 코드 (C++): void solve(){ ll N; cin >> N; vector<ll> A(N), B(N); rep(i, 0, N) cin >> A[i]; rep(i, 0, N) cin >> B[i]; vector<ll> bitCountA(30), bitCountB(30); rep(i, 0, N) rep(j, 0, 30){ if((A[i] >> j) & 1) bitCountA[j]++; if((B[i] >> j) & 1) bitCountB[j]++; } ll ans1 = 0; rep(i, 0, 30){ ans1 += (1LL << i) % 1999 * (bitCountA[i] * bitCountB[i]) % 1999; ans1 %= 1999; } cout << ans1 << " "; ll ans2 = 0; vector<ll> dq[2], ndq[2]; dq[0].reserve(N); dq[1].reserve(N); ndq[0].reserve(N); ndq[1].reserve(N); rep(i, 0, N) dq[0].push_back(A[i]); rep(bit, 0, 30){ ndq[0].clear(); ndq[1].clear(); for(ll x: dq[0]) (x >> bit) & 1 ? ndq[1].push_back(x) : ndq[0].push_back(x); for(ll x: dq[1]) (x >> bit) & 1 ? ndq[1].push_back(x) : ndq[0].push_back(x); swap(dq[0], ndq[0]); swap(dq[1], ndq[1]); vector<ll> cand; if(!dq[0].empty()){ cand.push_back(dq[0].front()); cand.push_back(dq[0].back()); } if(!dq[1].empty()){ cand.push_back(dq[1].front()); cand.push_back(dq[1].back()); } bool flag = true; for(auto x: B) for(auto c: cand) if((((x+c) >> bit) & 1) == 0){ flag = false; break; } if(flag) ans2 += (1LL << bit); } cout << ans2 << "\n"; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/32528 🧐 관찰 및 접근 # 오늘도 찾아온 게임이론 문제이다. 주어진 그래프는 함수형 그래프이다. 함수형 그래프는 사이클 하나와, 해당 사이클로 들어가는 간선들의 모양을 가진다. 정점은 $N$개, 간선은 $N$개이다. 일단 선공 $A$가 $B$의 앞 칸을 끊어버렸다고 가정하자. 함수형 그래프이므로 앞 칸은 언제나 존재한다. 후공 $B$는 자신의 이웃한 정점으로 이동할 수가 없다. 따라서, 어떤 정점 하나를 삭제하는 수밖에 없다. 선공 $A$의 턴의 경우의 수를 줄이기 위해, 해당 정점도 $A$의 앞 칸이었다고 가정하자. 그렇다면 현재 남은 정점은 $N-2$개이므로, $N$이 짝수일때는 후공이, 홀수일때는 선공이 이기게 된다. 그렇다면 $N$이 짝수일때는 선공이 $B$의 앞칸을 끊는것이 손해인가? 시작 위치에서 $B$가 $A$의 앞에 있었다고 생각해보자. 그렇다면 $A$는 두번째 자신의 턴에서 $B$의 위치로 이동할 수 있고, 이후 삭제할 수 있는 정점의 개수는 $N-1$개, 턴은 $B$의 턴이다. 따라서 이때는 선공이 승리한다. 따라서, $N$이 홀수이거나, $N$이 짝수이면서 $B$가 $A$의 앞 칸이라면 선공이 무조건 승리할 수 있다. $N$이 짝수고 $B$가 $A$의 앞칸이 아니라면 라면 선공이 어떻게 하면 좋을까? 상대한테 턴을 넘기는 편이 유리할 것 같다. 그러면 $A$가 한칸 앞으로 간다고 해보자. 이때 $B$는 또한 $A$를 억제하기 위해 위와 같은 행동을 할 수 있고, 이때 $N$은 짝수로 고정되어있으므로 $A$가 $B$의 앞칸이라면 후공이 무조건 승리할 수 있고, 그렇지 않다면 $B$도 한칸 앞으로 갈 것이다. 이는 사이클 안에 갇힐때까지 반복된다! 풀이를 요약해보자. 둘이 같은 칸에 있을때는, 그때부터 N-1개 정점 지우기 게임이 된다. $N$이 홀수일때는 나중에 행동하는 쪽이, 짝수일때는 먼저 행동하는 쪽이 이기게 된다. 상대의 앞 칸을 지울 수 있고, $N$이 홀수라면 바로 들어가서 삭제를 거는게 이득이다. 아니라면 이동을 할텐데, 그 이동을 한 결과 상대의 승리조건을 만족시켜버린다면 그냥 아무 정점이나 지워버려서 그런 상황이 오지 못하게 만들자. 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; int A, B; cin >> A >> B; vector<int> nxt(N+1); rep(i, 1, N+1) cin >> nxt[i]; set<tuple<int, int, bool>> st; st.insert({A, B, true}); bool Aturn = true; while(true){ // cout << A << ' ' << B << ' ' << Aturn << '\n'; if(A == B){ if(N%2) cout << (Aturn ? "second" : "first"); else cout << (Aturn ? "first" : "second"); return; } if(Aturn && (nxt[B] != A && N%2)){ cout << "first"; return; } if(!Aturn && (nxt[A] != B && N%2)){ cout << "second"; return; } if(Aturn && nxt[nxt[A]] != B && N%2) N--; else if(!Aturn && nxt[nxt[B]] != A && N%2) N--; else if(Aturn) A = nxt[A]; else B = nxt[B]; Aturn = !Aturn; if(st.count({A, B, Aturn})){ cout << "draw"; return; } st.insert({A, B, Aturn}); } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: 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'; } 🔒 구현 코드 잠금