Algorithm

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/7008 번역 문제 # Alice Catherine Morris와 그녀의 여동생 Irene Barbara는 자주 이메일을 주고받습니다. 항상 도청을 경계하며 통신 내용을 비밀로 유지하고자, 그들은 메시지를 두 단계로 암호화합니다. 모든 비알파벳 문자를 제거하고 모든 문자를 대문자로 변환한 후: 각 문자를 알파벳에서 s 위치 뒤의 문자로 치환합니다 (1 <= s <= 25) - 이를 s만큼의 시프트라고 합니다. 단계 1의 결과를 m개의 문자로 된 그룹으로 나누고 각 그룹의 문자들을 역순으로 배열합니다 (5 <= m <= 20). 메시지의 길이가 m으로 나누어떨어지지 않으면, 마지막 k개(m보다 작은)의 문자들을 역순으로 배열합니다. 예를 들어, s = 2이고 m = 6이라고 가정합시다. 평문이 “Meet me in St. Louis, Louis.“라면, 불필요한 문자를 제거하고 대문자로 변경하면:

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/16225 🧐 관찰 및 접근 # 약간 게임이론적이네. $(A_i, B_i), (A_j, B_j)$ 두가지를 고른다. 이때, $B_i > B_j$라면 $A_j$, $B_i < B_j$라면 $A_i$를 얻게된다. 직관적인것들을 생각해보자. $A_i$가 크고, $B_i$가 작은것들이 있으면 좋겠다. 위 친구들을 $A_i$가 작거, $B_i$가 큰 친구들이랑 매칭시켜서 없애버리면 좋다. $B$가 가장 작은 문제는 언제나 내가 풀게 된다. $B$가 가장 큰 문제는 언제나 상대가 풀게 된다. 이쪽에서 출발해볼까? $B$에 대한 오름차순으로 정렬해보자. 그러면 버릴 문제를 하나 고를 수 있다. 일단 예제를 $B$에 대한 오름차순으로 정렬한 후, $A$만 남기면 $(2, 4, 8, 6)$ 이 된다. 이때 2를 택하고 4를 버려고, 8을 택하고 6을 버리면 10이 된다. 여러개로 생각해보니, 약간 올바른 괄호 문자열 맛으로 되는데… 20만 $O(N^3)$ DP는 안된다이 $\text{DP}[i][j]$: $i$번째까지 봤을때, 여는괄호가 $j$개일때 최댓값 이라고 하면 $O(N^2)$도 된다만… 근데 열리는 괄호는, 생각보다 빠르게 열어줘야한다. 1번을 먹었으니, $(2, 3)$중에 하나는 무조건 열어야 한다. $2$를 먹었다면, $3, 4, 5$중 하나는 무조건 열어야 한다. $3$을 먹었다면, $2, 4, 5$중 하나는 무조건 먹어야 한다. $k$개 먹었다면, $2 \leq i \leq 2*k + 1$ 범위 내에서 한개를 더 먹어줘야한다. 이때 최댓값을 먹어줘야하고, 점 업데이트가 있으니 세그먼트 트리로 되겠다. 세그워킹 ㄱ.ㄱ 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; vector<pii> A(N); rep(i, 0, N) cin >> A[i].first; rep(i, 0, N) cin >> A[i].second; sort(all(A), [](pii a, pii b){ return a.second < b.second; }); vector<ll> v; rep(i, 0, N) v.push_back(A[i].first); ST.init(N); rep(i, 0, N) ST.set(i, v[i]); ST.build(); ll ans = v[0]; rep(i, 1, N/2){ auto [val, idx] = ST.seg_walk(1, i*2); ans += val; ST.update(idx, 0); } cout << ans << '\n'; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/28433 🧐 관찰 및 접근 # 수열을 원하는 개수의 연속된 구간으로 나누어서 구간의 합이 양수인 개수 - 구간의 합이 음수인 개수를 양수로 만들자. 직관적으로 생각해보자. 지금까지의 합이 양수면 -> 걍 잘라버리는게 이득이다. 지금까지의 합이 음수면 -> 이게 좀 고민이네 다음 놈이 음수면 -> 계속 먹으면 되는데, -100 -100 -100 1 -100 같은 경우에는 한번에 큰덩이로 먹는게 이득일수도 있지 않나? 일단 양수/음수는 묶어서 생각할 수 있을거같고, 음수 친구를 왼쪽/오른쪽으로 보내서 양수 덩어리에 합류시킬지 말지만 고민하면 되는것같다. 그렇다면 양수 / 양수 / 음수 / 양수 / 음수 / 양수 이렇게 생겼을텐데, 이제는 음수인 것이 두개 이상 붙어서 등장하지 않는다. 양수 개수 > 음수 개수라면 1을 출력하면 된다! 양수 개수 = 음수 개수라면 한 칸이 결합 가능한지 생각하면 된다! 양수 개수 < 음수 개수라면 두 칸이 결합 가능한지 생각하면 된다! 이게 두번 확인해야해서 문제지만, 결합 가능하면 무조건 결합한다는 방식이 그리디하게 가능하다. 직관적이긴 하네 라고!!!!!!!! 생각했지만!!!!!!!!! 틀렸다. $[2, -1, -1, 2, -1, -1]$ 의 경우.. $(2, -1), (-1, 2), (-1, -1)$로 묶으면 된다. 그러니까 맘대로 묶으면 안된다는건데…. 그리디 문제 추천받아서 풀던거라 여기서 DP로 틀진 않았고, 솔직히 평소같았으면 세그DP로 튀었을듯 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; vector<ll> v; ll sum = 0; rep(i, 0, N){ ll x; cin >> x; if(x != 0) v.push_back(x); sum += x; } if(v.size() == 0){ cout << "NO\n"; return; } ll cur = 0; int pcnt = 0, ncnt = 0; for(auto x: v){ if(x > 0){ if(cur <= 0 && cur +x > 0) cur += x; else{ if(cur > 0) pcnt++; if(cur < 0) ncnt++; cur = x; } } else{ if(cur > 0 && cur + x <= 0){ if(cur > 0) pcnt++; if(cur < 0) ncnt++; cur = x; } else{ cur += x; } } // cout << "cur: " << cur << " pcnt: " << pcnt << " ncnt: " << ncnt << "\n"; } if(cur > 0) pcnt++; if(cur < 0) ncnt++; cout << (pcnt > ncnt ? "YES" : "NO") << "\n"; } 🔒 구현 코드 잠금

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