Problem Solving

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/31760 번역 문제 # Apolyanka와 Büdelsdorf는 최근 접촉하게 된 두 개의 작은 신석기 시대 마을입니다. $1$부터 $N$까지 번호가 매겨진 $N$개의 자원이 있으며, 각 마을은 서로 다른 효율성을 가지고 이들 자원을 독립적으로 생산할 수 있습니다. 자원 $i$를 한 단위 생산하기 위해, Apolyanka는 $A_i$ 인시(person-hours)가 필요하고, Büdelsdorf는 $B_i$ 인시가 필요합니다. 현재 Apolyanka는 주어진 각 시간 기간에 자원 $i$를 $U_i$ 단위 생산하고 있으며, Büdelsdorf는 $W_i$ 단위를 생산하고 있습니다.

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/26969 번역 문제 번역 # Bessie는 “소 유전체학: 다큐멘터리"를 보고 싶지만, 혼자 가고 싶지 않습니다. 불행히도, 그녀의 친구들은 함께 갈 만큼 열정적이지 않습니다! 따라서 Bessie는 친구들이 영화관에 함께 가도록 뇌물을 줘야 합니다. 그녀는 두 가지 뇌물 수단을 가지고 있습니다: 무니(mooney)와 아이스크림 콘입니다.

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/26857 번역 문제 번역 # 두 형제 Aldo와 Bondan은 COVID-19 팬데믹 상황이 악화되어 도시가 다시 봉쇄되면서 집에 갇혀 있습니다. 그들은 학기를 마치고 방학 중이지만, 집 밖으로 나갈 수 없다면 무슨 방학을 즐길 수 있을까요? 하지만 지루함은 창의성을 불러일으킵니다. 그들은 지루한 방학 동안 새로운 게임을 만들었습니다.

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/13448 🧐 관찰 및 접근 # 얻는 점수가 $M_i - t * p_i$가 아닌 $M_i$라면, 단순한 배낭문제일텐데.. 이걸 위해서 $N$에 대한 비트마스킹을 추가하는건 미친짓이다 그런데, 어떤 문제들을 풀기로 결정했다면, 그 문제들에 대해 순서를 정하는건 그리디하게 되지 않나? 문제 $i, j$가 있다고 하자. $i \rightarrow j$로 풀면 $(M_i - t * P_i) + (M_j - (t + R_i)*P_j)$ 점을 얻게 되고 $j -> i$로 풀면 $(M_j - t*P_j) + (M_i - (t + R_j) * P_i)$ 점을 얻게 된다. 위에서 아래 식을 빼면 $P_i * R_j - P_j * R_i$ 이고, $i \rightarrow j$가 이득이기 위해선 이게 양수여야하므로 $\frac{P_i}{R_i} \geq \frac{P_j}{R_j}$로 정렬하는 그리디 전략이 유효하다. 그렇다면 이 순서로 냅색 DP를 수행하자. 💻 풀이 # 코드 (C++): void solve(){ int N, T; cin >> N >> T; vector<Problem> Prob(N); rep(i, 0, N) cin >> Prob[i].M; rep(i, 0, N) cin >> Prob[i].P; rep(i, 0, N) cin >> Prob[i].R; sort(all(Prob), [](Problem &A, Problem &B){ return A.P * B.R > B.P * A.R; }); vector<ll> DP(T+1); for(auto [M, P, R]: Prob) rrep(t, 0, T+1){ if(t - R < 0) break; DP[t] = max(DP[t], DP[t - R] + (M - P*t)); } ll ans = 0; rep(i, 0, T+1) ans = max(ans, DP[i]); cout << ans; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/31265 🧐 관찰 및 접근 # 이해가 조금 어려운데, 결국 $N$개의 훈련 상황에서 $d$개의 훈련 가운데 하나를 계속 고르고, 훈련 시간의 합을 최대화 하고싶다. 배낭 문제와 비슷해보인다. $d$개의 선택지가 $N$번 주어지고, 훈련시간 = 무게의 합을 최대화 해야한다. 어? 나이브하게 하면 터지나? 각 단계마다 해야하는 연산량은 $M * d_i$이다. 총 연산량은 $\sum\limits_{i = 1}^N M * d_i \leq 1000 M$ 이니 괜찮을 것 같다. 아니!!!!!!!! 왜틀렸나 했네 각 훈련 상황에서 적어도 하나의 훈련을 골라 훈련 계획에 넣으려고 한다. 한 훈련을 여러번 쓰지 않게 $M$에 대해 역순으로 돌면서, 잘 처리하자. 💻 풀이 # 코드 (C++): void solve(){ cin >> N >> M; rep(i, 0, N){ cin >> D[i]; tv[i].resize(D[i]); } rep(i, 0, N) rep(j, 0, D[i]) cin >> tv[i][j]; knapsack[0][0] = true; rep(i, 1, N+1) for(auto t: tv[i-1]) rrep(j, 0, M+1) if(j - t >= 0 && (knapsack[i-1][j-t] || knapsack[i][j-t])) knapsack[i][j] = true; rrep(j, 0, M+1) if(knapsack[N][j]){ cout << j; return; } cout << -1; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/30788 🧐 관찰 및 접근 # 대칭이동을 어떻게 수학적으로 표현할 수 있을까?? 쉬운거부터 해보자. 원래 점이 $(x, y)$에 있었다면 $90\degree$ 직선에 대칭시키면 $(-x, y)$ $45\degree$ 직선에 대칭시키면 $(y, x)$ $60\degree$ 직선에 대칭시키면 $y = \sqrt{3}x$에 대칭인거니까… 아니 이거 너무 까다로운데? 행렬연산은 하기 싫은데.. 각도를 기준으로 생각해보는것도 좋겠다. 극좌표계처럼, 원래 점이 $0\degree$에 있었다면 $60\degree$에 대해 대칭시키면 $120\degree$에 $120\degree$에 대해 대칭시키면 $240\degree$에 이런 느낌인 것 같다. 그렇다면 예제 1번은 $0\degree \rightarrow 120\degree \rightarrow 330 \degree \rightarrow 60 \degree \rightarrow 0$ 인거 같다! $45\degree = 225\degree$라고 생각하고, 가까운 곳을 찾아서 두배로 넘기고, 360으로 모듈러를 취하자. 자, 이제 한번씩 써서 0도로 돌아오는걸 어떻게 만들지? $15\degree$로 만들 수 있는건 $30\degree$ $x\degree$를 $a$에 대칭이동시키면 $(2a - x) \degree$가 되는 것 같다! 이걸 또 $b$에 대칭이동시키면 $(2b - (2a - x))\degree$ 인거같고.. 그러면 플마로 바뀌어가면서 더해지니까 결국 모듈러 360에 대해 두 그룹으로 나눈 합을 일정하게 맞출 수 있는지에 대한 문제로 바뀐다. 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; vector<int> A(N); rep(i, 0, N) cin >> A[i]; if(N%2){ cout << "NO"; return; } int sum = 0; for(auto x: A) sum += x; sum %= 360; DP[0][0][0] = true; rep(i, 0, N) rrep(j, 0, N) rep(k, 0, 360) if(DP[i][j][k]){ int nxt = (k + A[i]*2) % 360; DP[i+1][j+1][nxt] = true; DP[i+1][j][k] = true; } if(DP[N][N/2][sum] || DP[N][N/2][(sum + 180) % 360]){ cout << "YES\n"; vector<bool> used(N); int ci = N, cj = N/2, cs = sum; if(!DP[N][N/2][sum]) cs = (sum + 180) % 360; while(cj){ int prv = (cs - A[ci-1]*2) % 360; if(prv < 0) prv += 360; if(DP[ci-1][cj - 1][prv]){ used[ci-1] = true; ci--; cj--; cs = prv; } else ci--; } vector<int> v1, v2; rep(i, 0, N){ if(used[i]) v1.push_back(i+1); else v2.push_back(i+1); } rep(i, 0, N/2){ cout << v1[i] << ' ' << v2[i] << ' '; } } else cout << "NO"; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/30208 🧐 관찰 및 접근 # 업무들의 순서때문에, 자유롭게 선택하지 못하는 경우들이 생긴다. 이게 어떤 느낌이지? 예제 입력 1의 순서는 다음과 같다. $1 \rightarrow 2 \rightarrow 3$을 보자. $1$까지 수행해서 중요도 $w_1$, 처리시간 $t_1$을 얻을 수 있다. $2$까지 수행해서 중요도 $w_1 + w_2$, 처리시간 $t_1 + t_2$를 얻을 수 있다. $3$까지 수행해서 $\cdots$ 저렇게 물건을 만들고 나면, 세개중에서 택1을 하는것 빼고는 배낭문제와 동일해진다. 트리 dfs로 냅색을 잘 돌면서 DP를 할 수 있을 것 같다. 근데 안에서 분기가 일어나면… 0이 아닌 모든 $p_i$들은 모두 다르다 라는 문장이 입력에 있다. 💻 풀이 # 코드 (C++): void dfs(int cur, int root, int w, int t){ w += W[cur]; t += T[cur]; bags[root].push_back({w, t}); for(auto nxt: links[cur]) dfs(nxt, root, w, t); } void solve(){ cin >> N >> S; rep(i, 1, N+1) cin >> W[i]; rep(i, 1, N+1) cin >> T[i]; rep(i, 1, N+1){ int p; cin >> p; links[p].push_back(i); } for(auto nxt: links[0]) dfs(nxt, nxt, 0, 0); rep(i, 0, N+2) rep(j, 0, S+1) KS[i][j] = 1e9; KS[0][0] = 0; rep(i, 0, N+1) rep(j, 0, S+1) { KS[i+1][j] = min(KS[i+1][j], KS[i][j]); for(auto [w, t]: bags[i]){ int nxt = min(S, j + w); // } KS[i+1][nxt] = min(KS[i+1][nxt], KS[i][j] + t); } } if(KS[N+1][S] == 1e9) cout << -1; else cout << KS[N+1][S]; } 🔒 구현 코드 잠금

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