📝 문제 정보 # 링크: https://www.acmicpc.net/problem/9345 🧐 관찰 및 접근 # 수열에서의 swap연산이 주어지고, 수열의 $L, R$ 범위가 주어졌을 때 해당 범위에 $L \leq x \leq R$의 모든 수가 있는지 묻는 문제이다. 합같은것으로는 저걸 구분할 수가 없다. $(3, 4)$나 $(2, 5)$나 같으니까. 아하, DVD들끼리 겹치지 않으므로 구간 최소/최댓값을 이용하면 되겠다. 💻 풀이 # 코드 (C++): void solve(){ int N, K; cin >> N >> K; vector<pii> a(N); rep(i, 0, N) a[i] = {i, i}; SegmentTree ST(N, a); while(K--){ int op, a, b; cin >> op >> a >> b; if(op == 0){ int aval = ST.query(a, a).first; int bval = ST.query(b, b).first; ST.set(a, bval); ST.set(b, aval); } else{ pii res = ST.query(a, b); if(res.first == a && res.second == b) cout << "YES\n"; else cout << "NO\n"; } } } 🔒 구현 코드 잠금
📝 문제 정보 # 링크: 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}); } } 🔒 구현 코드 잠금