Problem Solving

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/11920 🧐 관찰 및 접근 # 배열 $[3, 4, 1, 2, 7, 6]$이 있다고 하자. 처음 한바퀴를 돌면 어떻게 되지? $[3, 1, 2, 4, 6, 7]$이 된다. 이걸 어떻게 해석할 수 있을까? 가장 큰 수는 맨 오른쪽에 고정된다. 다른 수들은, 오른쪽에 붙어있수가 자기보다 작은것들을 왼쪽으로 다 밀고, 오른쪽으로 간다. 오큰수? 스택? 그런맛인데 이거 두번하면 어떻게? $[1, 2, 3, 4, 6, 7]$이 된다. 나 5 안썼었구나 ㅋㅋ 이런 값을 두개정도 들고있다가..? 뭔가 그런느낌…? $K$번 진행한다고 하면, 값을 $K$개정도 들고있다가, 들고있는 값중 젤 작은거보다 작으면 그대로 통과시키고, 그것보다 크다면? 어떻게 되는거지? $[5, 7, 4, 3, 6, 8, 1, 2]$를 해보자. $[5, 4, 3, 6, 7, 1, 2, 8]$ $[4, 3, 5, 6, 1, 2, 7, 8]$ 두개 들고있다가 큰거 만나면 작은값 빼버려서 튀면 되는듯?? 💻 풀이 # 코드 (C++): void solve(){ int N, K; cin >> N >> K; vector<int> A(N); rep(i, 0, N) cin >> A[i]; vector<int> ans; priority_queue<int, vector<int>, greater<int>> PQ; rep(i, 0, N){ PQ.push(A[i]); if(PQ.size() > K){ ans.push_back(PQ.top()); PQ.pop(); } } while(!PQ.empty()){ ans.push_back(PQ.top()); PQ.pop(); } for(auto x: ans) cout << x << " "; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/28068 🧐 관찰 및 접근 # 지금 어떤 책을 읽을 수 있고, $a_k <= b_k$라면, 읽지 않을 이유가 없다. 나머지 $a_k > b_k$들인 책들은 어차피 읽을수록 즐거움이 감소만 하므로, $a_k$가 큰거부터 차례대로 읽으면 되지 않을까? 어떻게 그리디하게 가야하지? 두 책 $i, j$가 있다고 해보자. 이때, 두 책을 $i \rightarrow j$로 읽기 위해선 $F \geq a_i$ $F - a_i + b_i \geq a_j \rightarrow F \geq a_i + a_j - b_i$ 따라서 $F \geq \max(a_i, a_i + a_j - b_i) = \text{Cost}_{i \rightarrow j}$ 같은 방식으로, $j \rightarrow i$로 읽기 위해선 $F \geq \max(a_j, a_i + a_j - b_j) = \text{Cost}_{j \rightarrow i}$ 이 때, $b_i \geq b_j$라고 가정하자. $a_i < a_i + (a_j - b_j)$ $a_i + a_j - b_i \leq a_i + a_j - b_j$ 이 두 식이 성립하므로, 언제나 $\text{Cost}_{i \rightarrow j} \leq \text{Cost}_{j \rightarrow i}$ 따라서 $b$의 내림차순으로 정렬 후 그리디가 성립한다. 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; vector<pii> v1, v2; rep(i, 0, N){ int a, b; cin >> a >> b; if(a <= b) v1.push_back({a, b}); else v2.push_back({a, b}); } sort(all(v1)); sort(all(v2), [](pii &p1, pii &p2){ return p1.second > p2.second; }); ll cur = 0; for(auto &p: v1){ if(cur < p.first){ cout << 0; return; } cur -= p.first; cur += p.second; } for(auto &p: v2){ if(cur < p.first){ cout << 0; return; } cur -= p.first; cur += p.second; } cout << 1; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/24452 번역 문제 번역 # JOI 연방국에는 1부터 N까지 번호가 매겨진 N개의 도시와, 1부터 M까지 번호가 매겨진 M개의 도로가 있다. 도로 i (1 ≦ i ≦ M)는 도시 Ui와 도시 Vi를 양방향으로 연결하고 있다. JOI 연방국은 1부터 K까지 번호가 매겨진 K개의 주(州)로 이루어져 있다. 도시 j (1 ≦ j ≦ N)는 주 Sj에 속해 있다. 또한, 모든 주는 적어도 하나의 도시를 포함한다.

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/18830 🧐 관찰 및 접근 # 11차원인게 조금 이슈이므로, 간단하게 3차원정도로 생각해보자. 2차원이면 그냥 누적합 배열에서 $S(a_2, b_2) - S(a_1, b_2) - S(a_2, b_1) + S(a_1, b_1)$이었던 것이 기억난다. $a_1, b_1, c_1, a_2, b_2, c_2$가 주어진다. $a_1 \leq \alpha \leq a_2, b_1 \leq \beta \leq b_2, c_1 \leq \gamma \leq c_2$ 인 어쩌구에 대해 합을 출력한다. 이를 누적합으로 생각하면, $S(a_2, b_2, c_2) - S(a_1, b_2, c_2) - S(a_2, b_1, c_2) - S(a_2, b_2, c_1) + S(a_1, b_1, c_2) + S(a_1, b_2, c_1) + S(a_2, b_1, c_1) - S(a_1, b_1, c_1)$ 인 것 같다! 아님말고 암튼 $n$차원일때 누적합 배열을 구해둔다면 $2^n$의 시간복잡도로 계산할 수 있는 것 같다. 쿼리가 4만개이므로 $40000 * 2048 = 81920000$이므로 충분히 돌 것 같다. 그런데 누적합 배열을 만드는게 $O(2^n * mno...w)$ 라서 이게 20억인데… 포함배제로 구하지 말고, 차원에 대해서 구하고 밀어버리자. 💻 풀이 # 코드 (C++): const int cdim = 11; using v11 = array<int, cdim>; v11 dim, sz; int totSz; vector<ll> A, pfsum; int point_to_idx(const v11 &point){ int idx = 0; rep(d, 0, cdim) idx += point[d] * sz[d]; return idx; } vector<ll> make_prefix_sum(int cd = 0, v11 cp = {}){ vector<ll> res; if(cd == cdim){ int idx = point_to_idx(cp); res.push_back(A[idx]); return res; } rep(i, 0, dim[cd]){ cp[cd] = i; vector<ll> tmp = make_prefix_sum(cd+1, cp); if(res.empty()) res = tmp; else{ rep(j, 0, tmp.size()) res.push_back(res[(i-1) * sz[cd] + j] + tmp[j]); } } cp[cd] = 0; return res; } void solve(){ rep(i, 0, cdim) cin >> dim[i]; sz[cdim-1] = 1; rrep(d, cdim-1, 0) sz[d] = sz[d+1] * dim[d+1]; totSz = sz[0] * dim[0]; A.resize(totSz); pfsum.resize(totSz, 0); rep(i, 0, totSz) cin >> A[i]; pfsum = make_prefix_sum(); int Q; cin >> Q; while(Q--){ v11 L, R; rep(d, 0, cdim) cin >> L[d]; rep(d, 0, cdim) cin >> R[d]; rep(d, 0, cdim) L[d]--, R[d]--; ll ans = 0; rep(mask, 0, (1<<cdim)){ v11 point = R; bool add = true, flag = true; rep(d, 0, cdim) if(mask & (1<<d)){ point[d] = L[d]-1; add = !add; if(point[d] < 0){ flag = false; break; } } if(!flag) continue; int idx = point_to_idx(point); if(add) ans += pfsum[idx]; else ans -= pfsum[idx]; } cout << ans << "\n"; } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/31055 번역 문제 번역 # Bessie는 수학 지식을 향상시키기 위해 그래프 이론 강좌를 수강하고 있는데, 다음 문제에서 막혔습니다. 그녀를 도와주세요! 연결된 무방향 그래프가 주어집니다. 정점은 $1\dots N$으로, 간선은 $1\dots M$으로 라벨링되어 있습니다 ($2\le N\le 2\cdot 10^5$, $N-1\le M\le 4\cdot 10^5$). 그래프의 각 정점 $v$에 대해 다음 과정을 수행합니다:

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/28448 🧐 관찰 및 접근 # 한 문제당 광기는 $KT$만큼 쌓이고, 해결했을때 $\text{min}(KT, 5K)$만큼 빠지므로 $T \leq 5$라면 문제를 푸는데 광기가 안쌓인다. 어라? 아니네. $KT \leq L$ 조건도 필요하다. 아 이건 문제조건에 있네. 암튼 이 친구들은 어차피 T시간 걸려서 풀기만 하면 상관이 없다. 나머지 문제들에 대해, 어차피 문제를 풀어서 쌓이는 광기의 합은 일정하다. 그러니까, 문제를 해결해서 광기를 줄이는걸 힘내야하지 않을까? 그러면 광기를 많이 해소할 수 있는 문제를 먼저 풀어야하는 거 같은데… 💻 풀이 # 코드 (C++): void solve(){ ll N, L; cin >> N >> L; vector<pll> v; ll ans = 0; rep(i, 0, N){ ll K, T; cin >> K >> T; ans += T; if(T <= 5) continue; v.push_back({K, T}); } sort(all(v), [](pll a, pll b){ return min(a.first * a.second, 5 * a.first) > min(b.first * b.second, 5 * b.first); }); ll cur = 0; for(auto [K, T]: v){ if(cur + K*T > L){ ll rest = cur + K*T - L; ans += rest; cur -= rest; } cur += K*T; cur -= min(K*T, 5*K); } cout << ans; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/20136 🧐 관찰 및 접근 # 그리디하게, 뽑아야할때 곧 쓸만한걸 남기고, 나중에 쓸만한걸 뽑으면 되지 않을까? 증명해보자. 현재 $N$개의 구멍이 꽉차있고, $A$를 새로 꽂아야한다고 가정하자. 가장 나중에 쓰는걸 뽑는 전략 $G$가 있고, 어떤 최적의 전략 $Opt$가 있다고 가정하자. 이제 $G$가 $Opt$보다 나쁘지 않음을 보이면 된다. 어느 순간, $A$를 꽂기 위해 $G$는 $X$를, $Opt$는 $Y$를 뽑았다. 이때, 이후에 $X$가 먼저 등장한다면, $G$는 한번 더 뽑/꼽을 수행해야하고, $Opt$는 아니다. $Y$가 먼저 등장했다면, $Opt$는 뽑/꼽을 수행해야 하고, $G$는 아니다. 그런데, $G$의 전략 특성상 $Y$보다 $X$가 늦게 등장해야하므로, 언제나 $Opt$보다 $G$가 나쁘지 않다. 💻 풀이 # 코드 (C++): void solve(){ int N, K; cin >> N >> K; vector<queue<int>> nxt(K+1); vector<int> A(K); rep(i, 0, K) cin >> A[i]; rep(i, 0, K) nxt[A[i]].push(i); rep(i, 1, K+1) nxt[i].push(1e9); set<pii> st; // (nxt use, val) vector<bool> inuse(K+1, false); int ans = 0; rep(i, 0, K){ int val = A[i]; if(inuse[val]){ // 이미 꽂혀있다면 st.erase({i, val}); } // 꽂혀있지 않다면 else if((int)st.size() < N){ // 남은 자리가 있으면 inuse[val] = true; } else{ // 남은 자리가 없으면 ans++; pii old = *st.rbegin(); st.erase(old); inuse[old.second] = false; inuse[val] = true; } nxt[val].pop(); if(!nxt[val].empty()) st.insert({nxt[val].front(), val}); } cout << ans << '\n'; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/9938 🧐 관찰 및 접근 # 더 자세히 생각해보면, $(1, 2), (3, 4), (2, 3)$의 술병이 있는 경우, $1, 2, 3, 4$ 4개의 서랍중 3개의 서랍에 술이 들어갈 수 있다는 것을 알 수 있다. $A_i, B_i$를 보면서 분리 집합으로 묶어버린 뒤, 그 집합의 크기에 여유가 있다면 술병을 정리할 수 있다. 💻 풀이 # 코드 (C++): void solve(){ int N, L; cin >> N >> L; UnionFind UF(L); rep(i, 0, N){ int a, b; cin >> a >> b; a--; b--; UF.merge(a, b); if(UF.val[UF.find(a)] < UF.cnt[UF.find(a)]){ cout << "LADICA\n"; UF.add(a, 1); } else{ cout << "SMECE\n"; } } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/3830 🧐 관찰 및 접근 # 두 값의 차이를 트리 형태로 저장한다고 생각하자. 간선에 가중치가 있는 트리가 될 것이다. 두 값 $a, b$가 같은 트리에 있다면 비교 가능하고, 그렇지 않다면 비교 불가능하다. 하지만 이 경우 트리가 직선형이 되면, 최악의 경우 $O(N)$이 걸린다. 우리는 이러한 경우에 UnionFind에서 경로 압축을 하는 방법을 배웠다. 결국 루트까지의 간선 가중치 합을 저장해서 이용하면 된다. 💻 풀이 # 코드 (C++): void solve(){ while(1){ int N, M; cin >> N >> M; if(N + M == 0) break; UnionFind uf(N); while(M--){ char op; cin >> op; if(op == '!'){ int a, b, w; cin >> a >> b >> w; uf.merge(a-1, b-1, w); } else{ int a, b; cin >> a >> b; auto [ra, wa] = uf.find(a-1); auto [rb, wb] = uf.find(b-1); if(ra != rb) cout << "UNKNOWN\n"; else cout << wb - wa << '\n'; } } } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/21932 번역 문제 번역 # 문제 설명 # 무방향 그래프가 주어지고, 각 노드에는 양의 정수 값이 연결되어 있습니다. 임계값(threshold)이 주어지면, 그래프의 노드들은 두 그룹으로 나뉩니다: 하나는 임계값 이하의 값을 가진 노드들로 구성되고, 다른 하나는 나머지 노드들로 구성됩니다. 이제 서로 다른 그룹에 속한 두 노드를 연결하는 모든 간선을 제거하여 얻은 원래 그래프의 부분 그래프를 고려합니다. 두 노드 그룹이 모두 비어있지 않을 때, 주어진 그래프가 연결되어 있는지 여부와 관계없이 결과 부분 그래프는 연결이 끊어집니다.