Problem Solving

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/30478 문제 # 러시아워입니다! 오늘 퇴근 후, 쇼핑몰이 닫기 전에 가족 모두에게 줄 사탕을 사야 합니다. 가족들은 독점성과 균일성을 매우 중요하게 여기기 때문에, 당신은 그들을 감동시키기 위한 계획을 세웠습니다. 각 가족 구성원에게 주는 사탕은 모두 단일 브랜드여야 하며, 동일한 브랜드의 사탕을 다른 가족 구성원이 받아서는 안 됩니다. 또한, 누군가를 더 사랑한다는 사실을 들키고 싶지 않기 때문에 모든 가족 구성원이 같은 수의 사탕을 받아야 합니다.

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/14587 🧐 관찰 및 접근 # 전처리를 적당히 할 수 있을까? 이분탐색을 좀 하면서 밀면서 하면, 특정 도미노를 한쪽으로 밀었을때 어디까지 넘어가는지 할 수 있나? 아, min/max 세그먼트 트리로 되는거같다 마지막은 그리디가 아니라 DP로 해야한다! 아니근데 X가 정렬되어 주어지지 않는다;;;;; 그래도 구현이 막 어렵지 않은듯 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; vector<ll> X(N), H(N); vector<pll> dominos(N); rep(i, 0, N) cin >> dominos[i].first >> dominos[i].second; sort(all(dominos)); rep(i, 0, N){ X[i] = dominos[i].first; H[i] = dominos[i].second; } SegmentTreeMinMax ST_min(N), ST_max(N); // calc leftmost ST_min.set(0, 0); rep(i, 1, N){ ll val = X[i] - H[i]; auto idx = lower_bound(all(X), val) - X.begin(); auto Q = ST_min.query(idx, i-1); ST_min.set(i, min((ll)i, ST_min.query(idx, i-1).first)); } // calc rightmost ST_max.set(N-1, N-1); rrep(i, 0, N-1){ ll val = X[i] + H[i]; auto idx = upper_bound(all(X), val) - X.begin() - 1; auto Q = ST_min.query(i+1, idx); ST_max.set(i, max((ll)i, ST_max.query(i+1, idx).second)); } vector<int> DP(N, 1e9); DP[0] = 1; DP[ST_max.get_val(0)] = 1; rep(i, 1, N){ int lft = ST_min.get_val(i)-1; if(lft < 0) DP[i] = 1; else DP[i] = min(DP[i], DP[lft] + 1); int rht = ST_max.get_val(i); DP[rht] = min(DP[rht], DP[i-1] + 1); } cout << DP[N-1]; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/11111 🧐 관찰 및 접근 # 대충봐도 격자그래프에서 MCMF같은데.. 덜끊어도 되니까 MaxFlow가 아닌가? 아하 뒤집으면 된다 아하, Flow 자체도 다 보내기 전이 최적일수도 있는것만 잊지 말자 💻 풀이 # 코드 (C++): void solve(){ int N, M; cin >> N >> M; vector<vector<int>> costs = { {10, 8, 7, 5, 1}, {8, 6, 4, 3, 1}, {7, 4, 3, 2, 1}, {5, 3, 2, 2, 1}, {1, 1, 1, 1, 0} }; vector<vector<int>> board(N, vector<int>(M)); map<char, int> mp; mp['A'] = 0; mp['B'] = 1; mp['C'] = 2; mp['D'] = 3; mp['F'] = 4; rep(i, 0, N){ string S; cin >> S; rep(j, 0, M) board[i][j] = mp[S[j]]; } MinCostMaxFlow MCMF(N*M+2); MCMF.setST(N*M, N*M+1); vector<int> dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1}; rep(i, 0, N) rep(j, 0, M){ if((i+j)%2){ MCMF.add(i*M+j, N*M+1, 1, 0); continue; } MCMF.add(N*M, i*M+j, 1, 0); rep(d, 0, 4){ int nx = i + dx[d], ny = j + dy[d]; if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue; MCMF.add(i*M + j, nx*M + ny, 1, -costs[board[i][j]][board[nx][ny]]); } } cout << max(0LL, -MCMF.match()); } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/35108 🧐 관찰 및 접근 # $N$이 2500이니까 뭔가 제곱로그?까진 돌지 않을까 싶다. 음, 어떻게 잡으면 좋을지 모르겠지만, 저 주어진 게국지 그래프에서 안쪽의 네모중 왼쪽 위부터 반시계방향으로 $1, 2, 3, 4$ 라고 하면, $2, 4$번 정점을 기준으로 카운팅하고싶게 생기긴 했다. 일단 예제 그래프를 그려보자. 여기서 저 게국지모양을 찾아야 하는데… $1, 2, 3, 4$를 기7준으로 하면 $1, 2, 4$에 $5, 7, 6$을 붙이거나, $6, 7, 5$를 연결하는 두가지가 있겠다. 어.. 정점을 기준으로 세려고 하니 좀 까다로운거 같기도..? 그러면 간선을 기준으로..? 그러면 아무래도 양쪽에 날개가 붙어있는 간선으로 생각하자. 크아아아악 이래도 안되는데 일단 두 간선을 골라서 사이클을 고정시키는건 맞는거같다. 잉 이러면 걍 포함배제로 되는거 아닌가? 그러면 두 정점에 중복되는 정점, 세 정점에 중복되는 정점 뭐 그런게 필요한거같은데… 비트셋으로 하면 될라나? $O(M^2N/64)$ 정도인거같은데;; 일단 짜보자 좀 빡빡하다. 전처리를 잘 하면 시간 내로 들어간다. Clang이 훨 빠르네. 왜지? 💻 풀이 # 코드 (C++): void solve(){ int N, M; cin >> N >> M; vector<pii> edges; vector<bitset<2500>> con(N); rep(i, 0, M){ int u, v; cin >> u >> v; u--; v--; edges.push_back({u, v}); con[u][v] = 1; con[v][u] = 1; } vector<ll> cnt1(N); rep(i, 0, N) cnt1[i] = con[i].count(); vector<vector<bitset<2500>>> con2(N, vector<bitset<2500>>(N)); rep(i, 0, N) rep(j, i+1, N) con2[i][j] = con2[j][i] = con[i]&con[j]; vector<vector<ll>> cnt2(N, vector<ll>(N)); rep(i, 0, N) rep(j, i+1, N) cnt2[i][j] = cnt2[j][i] = con2[i][j].count(); auto calc = [&](int v1, int v2, int v3, int v4) -> ll { auto &b1 = con[v1], &b2 = con[v2], &b3 = con[v3]; ll n1 = cnt1[v1] - (con[v1][v2] + con[v1][v3] + con[v1][v4]); ll n2 = cnt1[v2] - (con[v2][v1] + con[v2][v3] + con[v2][v4]); ll n3 = cnt1[v3] - (con[v3][v1] + con[v3][v2] + con[v3][v4]); ll n12 = cnt2[v1][v2] - (con2[v1][v2][v3] + con2[v1][v2][v4]); ll n23 = cnt2[v2][v3] - (con2[v2][v3][v1] + con2[v2][v3][v4]); ll n31 = cnt2[v3][v1] - (con2[v3][v1][v2] + con2[v3][v1][v4]); bitset<2500> b123 = b1&b2&b3; ll n123 = b123.count() - b123[v4]; return n1*n2*n3 - (n12*n3 + n23*n1 + n31*n2) + 2*n123; }; ll ans = 0; rep(i, 0, M) rep(j, i+1, M){ auto [a, b] = edges[i]; auto [c, d] = edges[j]; if(a == c || a == d || b == c || b == d) continue; if((!con[a][c] || !con[b][d]) && (!con[a][d] || !con[b][c])) continue; ll ret = 0; ret += calc(a, b, c, d); ret += calc(b, c, d, a); ret += calc(c, d, a, b); ret += calc(d, a, b, c); if(con[a][c] && con[b][d]) ans += ret; if(con[a][d] && con[b][c]) ans += ret; } cout << ans/2; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/11493 🧐 관찰 및 접근 # 동전들을 swap해서 잘 옮겨서 맞춰야한다.. 일단 색을 모두 신경쓰긴 싫으니까, 1의 위치를 맞춘다고만 생각하자. 뭔가 이분그래프적으로 생각할 수 있지 않을까? 이게 움직이는것만 신경쓰면 플로이드워셜 + 이분그래프 매칭 최소비용…으로 하면 되는거같은데? 근데 swap이다보니 이렇게 맘대로 하는것보다 효율적인 방법이 무시될 것 같다. 일단 이분그래프로 생각을 좀 해보긴 하자. 그림을 그려보자. 그림 1의 예시이다. 어우 난잡해 ㅋㅋ 뭔가 증가경로 맛처럼 할 수 있는거같기는 한데.. ….가 아니라 그냥 이상태로 최소비용 최대유량 아닌가? 끝이네? 이분그래프로 분할할 필요도 없이, 그냥 유량으로 달리면 된다. 💻 풀이 # 코드 (C++): void solve(){ int N, M; cin >> N >> M; MinCostMaxFlow MCMF(N+2); MCMF.setST(0, N+1); rep(i, 0, M){ int u, v; cin >> u >> v; MCMF.add(u, v, 1e9, 1); MCMF.add(v, u, 1e9, 1); } rep(i, 1, N+1){ int x; cin >> x; if(x == 1) MCMF.add(0, i, 1, 0); } rep(i, 1, N+1){ int x; cin >> x; if(x == 1) MCMF.add(i, N+1, 1, 0); } cout << MCMF.match() << '\n'; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/23887 🧐 관찰 및 접근 # 설명을 대충 읽는데, BFS맛이 난다 허걱, 최대 학생이 25000명이라 나이브하게는 조금 곤란하긴 하다 근데 뭔가 트리처럼 해석할 수도 있을 것 같은데? MST인가? 아 근데 좀 유향 그래프? 맛인데… 위상정렬이네 이거 엥? 근데 이게 $2$번 학생이 $5, 6$번한테 받을 수 있다고해서 무조건 $5$번한테만 받는건 아니네? 그러면 다시 트리맛으로? 그러면 뭔가 트리의 지름을 최소화하는 느낌으로 가야하는 것 같은데… 그래프에서 가장 먼 두 점을 어떻게 구할 수 있을까? ???????? 아니 문제에서 $S$가 주어지는거였네 그러면 그냥 BFS를 돌리자 구현이 상당히 재밌다! 💻 풀이 # 코드 (C++): void solve(){ int N, M, K; cin >> N >> M >> K; vector<vector<int>> board(N, vector<int>(M, 0)); vector<pii> students(K+1); vector<bool> visited(K+1); rep(i, 1, K+1){ int x, y; cin >> x >> y; x--; y--; students[i] = {x, y}; board[x][y] = i; } int S; cin >> S; set<int> Q; Q.insert(S); visited[S] = true; vector<vector<int>> links(K+1); vector<int> dx = {-1, -1, -1, 0, 0, 1, 1, 1}; vector<int> dy = {-1, 0, 1, -1, 1, -1, 0, 1}; while(!Q.empty()){ set<int> nQ; for(auto cur: Q){ auto [cx, cy] = students[cur]; rep(d, 0, 8){ int nx = cx + dx[d]; int ny = cy + dy[d]; if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue; if(board[nx][ny] == 0) continue; int nxt = board[nx][ny]; if(visited[nxt]) continue; visited[nxt] = true; links[cur].push_back(nxt); nQ.insert(nxt); } } swap(Q, nQ); } rep(i, 1, K+1) if(!visited[i]){ cout << -1; return; } vector<int> sz(K+1); function<void(int)> dfs = [&](int cur){ sz[cur] = 1; for(auto nxt: links[cur]){ dfs(nxt); sz[cur] += sz[nxt]; } }; dfs(S); rep(i, 1, K+1) cout << sz[i] << ' '; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/15309 🧐 관찰 및 접근 # 이진트리..는 아니고 삼각형이구나. 걍 좀 펴서 생각하면, 이항계수처럼 생각하면 되는 것 같다. $i$번째 줄은 $(Ax + B)^i$ 의 계수처럼 생각하면 되는듯? 아 근데 그 뭐냐 겹치게 하면 안되는구나 특정 삼각형은 그 초항만 생각하면 되는것같으니까, $m$개의 행을 포함하는 정삼각형을 어떻게 계산할지 생각해보자. 대충 로그정도에 계산하면 되는데.. 일단 초항이 1일때 식은 뭐랑 같지? $1 + (A+B) + (A^2 + AB + B^2) + \cdots$ 같은 느낌인건데… 어차피 행 자체에는 누적합 맛으로 할 수 있겠네. 어라? 이건 그냥 윗 행에다가 $A$를 곱하고, $B^N$만 더하면 될거같은딩. 대충 해버리죠? 아니 잠깐만!!!!!!!!! $m$이 $10^{18}$이다!! 비상!!!!!!!!! 로그가 붙을만한곳은 분할정복 거듭제곱같은거밖에 없는데… 아 잠깐만. 이거 그냥 그 유명한 고딩때 그 공식처럼 $(A-B)$곱하면 정리되는 꼴 아닌가? 그러면 $(A-B) + (A^2 - B^2) + (A^3 - B^3) + \cdots$ 이건 $(A + A^2 + \cdots + A^m) - (B + B^2 + \cdots + B^m)$이자나! $\frac{A^{m+1} - 1}{A-1} - \frac{B^{m+1} - 1}{B-1}$ 로 계산할 수 있을 것 같고, 이걸 $A-B$로 나눠서 끝내자. 아!! $A = B$인 경우를 조심해야할 것 같고, $A = 1$이나 $B = 1$인경우도 조심해야할 것 같다. $A = B$라면? $1 + 2A + 3A^2 + \cdots + mA^{m-1}$ 를 구해야하는데, 저 합을 $S$라고 하자. 그러면 $AS - S = 1 + A + A^2 + \cdots + A^m$ 니까, $A = 1$인 경우 말고는 이걸 구해서 $A-1$로 나누면 될 것 같은데? 케이스 처리를 조심하자. 💻 풀이 # 코드 (C++): void solve(){ mint A, B; cin >> A >> B; int Q; cin >> Q; while(Q--){ ll x, y, m; cin >> x >> y >> m; x--; y--; mint cho = 1; cho *= A.pow(x-y); cho *= B.pow(y); mint trig = 0; if(A == B){ if(A == 1) trig = mint(m)*(m+1)/2; else trig = (A.pow(m+1) - 1) / (A - 1).pow(2); } else{ if(A == 1) trig += m; else trig += (A.pow(m+1) - 1) / (A - 1) - 1; if(B == 1) trig -= m; else trig -= (B.pow(m+1) - 1) / (B - 1) - 1; trig /= (A-B); } cout << cho * trig << '\n'; } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/34609 번역 문제 # $1$번부터 $n$번까지 번호가 매겨진 $n$송이의 꽃이 왼쪽에서 오른쪽으로 일렬로 놓여 있다. 각 꽃은 백합(lily) 또는 장미(rose) 중 하나이다. $0$ 이상 $n$ 이하의 정수 $j$에 대해, $l_j$를 왼쪽 $j$개의 꽃 중 백합의 수, $r_j$를 오른쪽 $n - j$개의 꽃 중 장미의 수라 하자.

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/28359 🧐 관찰 및 접근 # 일단 모두 $P$에 몰아넣거나, $Q$에 몰아넣거나는 가능하니 일단 기본적으로 모든 원소의 합정도는 여유롭게 가능하다. 그런데, 모든 수가 같다고 생각해보자. 그러면 모든 수는 $P$와 $Q$에 동시에 속하는데… 동시에 속할 수 있는 수를 어떻게 제어할 수 있지? 동시에 속한 수가 서로 다른 여러개의 수일 수는 없다. 어떤 수와 그 개수를 곱한 값이 최대인 수를 골라서, 맨 뒤로 보내자. 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; map<int, int> mp; int ans = 0; rep(i, 0, N){ int x; cin >> x; mp[x]++; ans += x; } int mxIdx = -1, mxVal = -1; for(auto [k, v]: mp){ if(k*v > mxVal){ mxVal = k*v; mxIdx = k; } } ans += mxVal; vector<int> v1, v2; for(auto [k, v]: mp){ if(k < mxIdx) rep(i, 0, v) v1.push_back(k); else if(k > mxIdx) rep(i, 0, v) v2.push_back(k); } rrep(i, 0, v2.size()) v1.push_back(v2[i]); rep(i, 0, mp[mxIdx]) v1.push_back(mxIdx); cout << ans << '\n'; for(auto x: v1) cout << x << ' '; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/1006 🧐 관찰 및 접근 # 유명한 통곡의 벽 문제 초라기 문제가 $2 \times N$의 원형이라 조금 곤란하다. 쉬운 경우부터 생각하자. $1 \times N$의 선형이라면, 계단 수처럼 DP로 풀 수 있을 것 같다. $2 \times N$의 선형이라도 DP로 가능한 것 같다. 두칸 전에서 오는 것에 대해 가로두개 / 위에 가로와 아래 따로 / 아래 가로와 위에 따로 한칸 전에서 오는 것에 대해 세로 / 위아래 따로 이 5가지 경우에서 가능한 것 같다! 그런데 원형이라 조금 곤란한데.. 뭔가 케이스를 나눌 수 있을 것 같긴 하다. 선형으로 생각했을때 맨 왼쪽에 대해, 그게 반대쪽과 이어진경우 / 안이어진경우. 위아래니까 각각 두가지, 총 4가지 경우의수를 따지면 될듯? 근데 이걸 어떻게 깔끔하게 코딩하지? 큰일났다. 둘다 반대쪽과 이어진 경우는 문제를 한칸 밀어서 풀기만 하면 되는 것 같은데, 한쪽만 밀린 경우가 까다롭다. 그런데 사실 모든 칸이 지그재그로 연결된 경우 빼고는 언젠가는 선형으로 풀어도 되는 타이밍이 있는 것 같다! 위에서 말한 타이밍은 예제에서는 $1-2, 10-11, 3-4, \cdots$로 연결된 느낌과 같다. 시간복잡도가 $O(NW)$이 되긴 하는데, 돌만하지 않을까? 저 지그재그만 예외처리를 해버리자. ㄲㅂ 시간초과네. 테케가 여러개라 그런 것 같다. 엥? 이거 그냥 길이를 $2N$으로 늘려서 하면 되지 않을까? …인줄알았는데 전이식 자체부터 두개 전에서 땡겨오다보니 차분트릭이 안먹히는것 같다. 전이식 자체에서도 여러칸 단위로 지그재그로 오면 할 수 있는게 없다.. DP에서, 상태공간을 조금 더 정의해보자. $\text{DP}[i][j]$라고 하면, i번째칸까지 봤을때 위아래 찬게 j상황이라고 생각해보자. $j = 0, 1, 2, 3$에서 위아래 모두 빔, 위 참, 아래 참, 위아래 모두 참과 같은 느낌이다. 이렇게해서 전이식을 잘 세우면 저 예외상황들을 처리하기 용이할 것 같다. 3번은 0번과 같으니 없애고, 나머지 3개로 정말 잘 처리해보자… 💻 풀이 # 코드 (C++): void solve(){ ll N, W; cin >> N >> W; vector<array<ll, 2>> v(N); rep(i, 0, N) cin >> v[i][0]; rep(i, 0, N) cin >> v[i][1]; auto calc = [&](bool con1, bool con2) { vector<array<ll, 3>> DP(N+1); // 0: 둘다끝, 1: 위가 튀어나감, 2: 아래가 튀어나감 rep(i, 0, N+1) rep(j, 0, 3) DP[i][j] = 1e18; DP[0][0] = 0; if(con1) DP[0][1] = 0; if(con2) DP[0][2] = 0; if(con1 && con2) DP[1][0] = 0; rep(i, 1, N+1){ DP[i][0] = min(DP[i][0], DP[i-1][0] + (v[i-1][0] + v[i-1][1] <= W ? 1 : 2)); DP[i][0] = min(DP[i][0], DP[i-1][1] + 1); DP[i][0] = min(DP[i][0], DP[i-1][2] + 1); if(i-2 >= 0 && v[i-2][0]+v[i-1][0] <= W && v[i-2][1]+v[i-1][1] <= W){ DP[i][0] = min(DP[i][0], DP[i-2][0] + 2); } DP[i][1] = min(DP[i][1], DP[i][0] + 1); if((i == N && con1) || (i < N && v[i-1][0] + v[i][0] <= W)){ DP[i][1] = min(DP[i][1], DP[i-1][0] + 2); DP[i][1] = min(DP[i][1], DP[i-1][2] + 1); } DP[i][2] = min(DP[i][2], DP[i][0] + 1); if((i == N && con2) || (i < N && v[i-1][1] + v[i][1] <= W)){ DP[i][2] = min(DP[i][2], DP[i-1][0] + 2); DP[i][2] = min(DP[i][2], DP[i-1][1] + 1); } } if(!con1 && !con2) return DP[N][0]; if(con1 && !con2) return DP[N-1][2] + 1; if(!con1 && con2) return DP[N-1][1] + 1; if(con1 && con2) return DP[N-1][0] + 2; }; auto origin = v; ll ans = 2*N; rep(con1, 0, 2) rep(con2, 0, 2){ if(con1 && v[0][0] + v[N-1][0] > W) continue; if(con2 && v[0][1] + v[N-1][1] > W) continue; ans = min(ans, calc(con1, con2)); } cout << ans << '\n'; } 🔒 구현 코드 잠금