Randomization

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