Problem Solving

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

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/4817 🧐 관찰 및 접근 # 최대한 괄호를 제거해야 한다. 괄호 안에 덧셈이 없다면, 해당 괄호는 제거해도 된다. 어떨 때 괄호를 살려야 하는가? $((x+y)z)$와 같이, 어떤 괄호로 이루어진 덧셈이 포함된 식과 어떤 식이 곱해지는 경우 남겨야 한다. 라곤 했지만… 구현이 만만치 않다. 이를 위해 추상 구문 트리 라는것을 보통 사용한다고 한다. 노드단위로 연산을 나타내자. 이때 파싱 과정에서, 연산 우선순위가 낮은걸 먼저 해야한다. (상위 노드가 먼저 계산되므로) 따라서 덧셈 -> 곱셈 -> 괄호의 순서로 진행하자. 쉽지 않은데.. 이런 생각보다 파서를 만드는 과정이 재밌다. 전산언어학 문제를 좀더 풀어보도록 하자. 💻 풀이 # 코드 (C++): struct Node{ char type; char var; Node *left, *right; Node(char c){ // var type = 'v'; var = c; left = right = nullptr; } Node(char op, Node *l, Node *r){ // op type = 'o'; var = op; left = l; right = r; } }; struct AST{ Node *root; AST(Node *r) : root(r) {} string emit(Node *n, char parOp){ if(n->type == 'v') return string(1, n->var); if(n->var == '+'){ string L = emit(n->left, '+'); string R = emit(n->right, '+'); if(parOp == '*') return "(" + L + "+" + R + ")"; return L + "+" + R; } return emit(n->left, '*') + emit(n->right, '*'); } string toString(){ return emit(root, 0); } }; struct Parser{ const string &S; int pos; Parser(const string &s): S(s), pos(0){} Node *parseVal(){ if(S[pos] == '('){ pos++; Node *node = parsePlus(); pos++; return node; } return new Node(S[pos++]); } Node *parseMul(){ Node *node = parseVal(); while(pos < (int)S.size() && (islower(S[pos]) || S[pos] == '(')){ Node *right = parseVal(); node = new Node('*', node, right); } return node; } Node *parsePlus(){ Node *node = parseMul(); while(pos < (int)S.size() && S[pos] == '+'){ pos++; Node *right = parseMul(); node = new Node('+', node, right); } return node; } AST parse(){ return AST(parsePlus()); } }; void solve(){ string S; while(cin >> S){ Parser parser(S); AST ast = parser.parse(); cout << ast.toString() << "\n"; } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/17435 🧐 관찰 및 접근 # 함수 $f$가 주어질 때, 최대 $500\,000$번 합성한 값을 구해야 한다. 나이브하게 계산하면 $O(QN)$으로 시간초과다. 전체를 전처리해두기엔, 공간복잡도가 $O(mN)$으로 너무 커진다. 따라서 적당히 전처리를 해두자. 이는 LCA에서 했던것과 같이, 희소 배열로 가능할 것 같다. 각 정의역에 대해 $1$번, $2$번, $4$번, $\cdots 2^k$번 합성한 결과를 저장해서 쿼리를 처리하자. 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; vector<vector<int>> f(20, vector<int>(N+1)); rep(i, 1, N+1) cin >> f[0][i]; rep(k, 1, 20) rep(i, 1, N+1) f[k][i] = f[k-1][f[k-1][i]]; int Q; cin >> Q; while(Q--){ int n, x; cin >> n >> x; rep(k, 0, 20) if(n & (1 << k)) x = f[k][x]; cout << x << "\n"; } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/7562 🧐 관찰 및 접근 # 가중치가 없으니, 간단한 BFS로 풀릴 것 같다. 시간복잡도는 $O(V + E) \approx O(N^2)$이다. 💻 풀이 # 코드 (C++): void solve(){ int dx[8] = {-2, -2, -1, -1, 1, 1, 2, 2}; int dy[8] = {-1, 1, -2, 2, -2, 2, -1, 1}; int N; cin >> N; vector<vector<int>> board(N, vector<int>(N, -1)); int sx, sy, ex, ey; cin >> sx >> sy >> ex >> ey; queue<pii> q; q.push({sx, sy}); board[sx][sy] = 0; while(!q.empty()){ auto [cx, cy] = q.front(); q.pop(); if(cx == ex && cy == ey){ cout << board[cx][cy] << "\n"; return; } rep(d, 0, 8){ int nx = cx + dx[d]; int ny = cy + dy[d]; if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue; if(board[nx][ny] == -1){ board[nx][ny] = board[cx][cy] + 1; q.push({nx, ny}); } } } 🔒 구현 코드 잠금