SCC

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/1739 🧐 관찰 및 접근 # $(1, 1) \rightarrow (6, 6)$으로 가기 위해선 어때야 하지? $r_1, c_6$이 오른쪽 / 아래이거나, $c_1, r_6$이 아래 / 오른쪽이거나.. 오른쪽 / 아래를 참, 왼쪽/위를 거짓이라고 생각하면, $(r_1 \land c_6) \lor (r_6 \land c_1)$ 같은 느낌인가? 이걸 어떻게 잘 하면 2-sat으로 바꿀 수 있을것같은데.. $r6$이 아니라면, $r1, c6$이 참이어야하고, 이런 느낌으로 되는것같다. $(\neg r_6 \rightarrow r_1) \land (\neg r_6 \rightarrow c_6)$ 이런걸 4개에 대해서 하면 될거같은데? $(r_1, c_1) \rightarrow (r_2, c_2)$ 라고 해보자. 일단 $r_1 < r_2, c_1 < c_2$라고 하자. $(\neg r_1 \rightarrow r_2) \land (\neg r_1 \rightarrow c_1)$ $(\neg c_2 \rightarrow r_2) \land (\neg c_2 \rightarrow c_1)$ $(\neg r_2 \rightarrow r_1) \land (\neg r_2 \rightarrow c_2)$ $(\neg c_1 \rightarrow r_1) \land (\neg c_1 \rightarrow c_2)$ 이렇게 할 수 있을 것 같다. 그러면 $r_1 > r_2, c_1 > c_2$라면? 똑같이 $r_1, c_2$의 경로를 이용하거나, $r_2, c_1$의 경로를 이용해야하는건 같다. 그런데 왼쪽이라서 참이어야 하는게 아니라 목적지가 거짓이어야 한다. $(\neg r_1 \land \neg c_2) \lor (\neg r_2 \land \neg c_1)$ 처럼 되어야할 것 같다. 아하, 대소관계가 바뀌면 이게 낫으로 바뀐다. 이걸 이용해서 더 쉽게 구현이 될라나? 구현 실수하지 않게 조심하자. 💻 풀이 # 코드 (C++): void solve(){ int N, M, K; cin >> N >> M >> K; DirectedGraph tsat((N+M)*2); rep(i, 0, K){ int r1, c1, r2, c2; cin >> r1 >> c1 >> r2 >> c2; r1--; c1--; r2--; c2--; r1 *= 2; r2 *= 2; c1 = (c1 + N) * 2; c2 = (c2 + N) * 2; if(r1 == r2 && c1 == c2) continue; if(r1 == r2){ if(c1 < c2) tsat.add_edge(r1^1, r1); else tsat.add_edge(r1, r1^1); continue; } if(c1 == c2){ if(r1 < r2) tsat.add_edge(c1^1, c1); else tsat.add_edge(c1, c1^1); continue; } if(c1 > c2) r1^=1, r2^=1; if(r1 > r2) c1^=1, c2^=1; tsat.add_edge(c1^1, r1); tsat.add_edge(c1^1, c2); tsat.add_edge(r2^1, r1); tsat.add_edge(r2^1, c2); tsat.add_edge(r1^1, r2); tsat.add_edge(r1^1, c1); tsat.add_edge(c2^1, r2); tsat.add_edge(c2^1, c1); } cout << (tsat.is2SAT() ? "Yes\n" : "No\n"); } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/4013 🧐 관찰 및 접근 # 그래프가 DAG라면 위상정렬을 하면서 DP를 진행할 수 있을텐데.. 같은 정점을 여러번 들릴 수 있으므로, 어떤 정점이 사이클 안에 들어있다면 해당 사이클 내의 ATM을 모두 들릴 수 있다! 서로 자유롭게 이동 가능한 관계라면 모두 자유롭게 들릴 수 있으므로, 이를 SCC로 묶어 DAG로 만들자. 💻 풀이 # 코드 (C++): void solve(){ cin >> N >> M; DirectedGraph graph(N+1); rep(i, 0, M){ int u, v; cin >> u >> v; graph.add_edge(u, v); } DirectedGraph dag = graph.getCompressedGraph(); int sz = dag.V; vector<int> val(sz), DP(sz, -1e9), indeg(sz, 0); rep(i, 1, N+1){ int X; cin >> X; val[graph.sccId[i]] += X; } int S, P; cin >> S >> P; S = graph.sccId[S]; DP[S] = val[S]; rep(u, 0, sz) for(auto &v: dag.links[u]) indeg[v]++; queue<int> Q; rep(i, 0, sz) if(indeg[i] == 0) Q.push(i); while(!Q.empty()){ int cur = Q.front(); Q.pop(); for(auto nxt: dag.links[cur]){ DP[nxt] = max(DP[nxt], DP[cur] + val[nxt]); indeg[nxt]--; if(indeg[nxt] == 0) Q.push(nxt); } } int ans = 0; rep(i, 0, P){ int X; cin >> X; X = graph.sccId[X]; ans = max(ans, DP[X]); } cout << ans << '\n'; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/3648 🧐 관찰 및 접근 # 모든 심사위원에 대해 (and) 각 심사위원별로 표 두개중 하나를 만족해야 한다. (or) 따라서 $(A \lor B) \land (C \lor D) \land \cdots$ 의 2-sat 문제로 변환 가능하다! 모델링만 잘 해보자. 가능한 변수의 개수 $= 1000 *2 = 2000$ 에 대해 $i$ 번 참가자가 진출: $2*i$, 진출 실패: $2*i+1$로 모델링하자. 1번 참가자인 상근이는 무조건 통과해야 한다. $\neg x \to x$ 를 만족하면 되므로, $1 \to 0$을 추가하자. 💻 풀이 # 코드 (C++): void solve(){ int N, M; while(cin >> N >> M){ DirectedGraph dg(2*N); rep(i, 0, M){ int u, v; cin >> u >> v; if(u > 0) u = 2*(u-1); else u = 2*(-u-1)+1; if(v > 0) v = 2*(v-1); else v = 2*(-v-1)+1; dg.add_2sat_edge(u, v); } dg.add_2sat_edge(0, 0); cout << (dg.is2SAT() ? "yes\n" : "no\n"); } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/16367 번역 문제 번역 # Mr. Dajuda는 TV 쇼 프로그램으로 유명한 사람으로, 가끔 시청자들에게 흥미로운 게임을 제안하고 상품을 상으로 제공합니다. 이번 주에 그가 제안한 게임은 다음과 같이 설명할 수 있습니다. 무대 위의 k개(k > 3)의 램프는 게임 시작 시 모두 꺼져 있습니다. 편의상 램프는 1부터 k까지 번호가 매겨져 있습니다. 각 램프는 빨간색 또는 파란색의 색상을 가지고 있습니다. 그러나 램프의 색상은 켜지기 전까지는 알 수 없습니다. 게임 참가자들은 무작위로 세 개의 램프를 선택하고 그 색상을 예측하도록 요청받습니다. 그런 다음 각 참가자는 선택한 램프의 예측된 색상이 기록된 종이를 게임 진행자인 Mr. Dajuda에게 제출합니다. 모든 램프가 켜지면 각 참가자는 자신이 예측한 색상 중 몇 개가 램프의 실제 색상과 일치하는지 확인합니다. 두 개 이상의 색상이 일치하면 상품을 받게 됩니다.

📝 문제 정보 # 링크: 번역 문제 # Farmer John은 소들의 방목 패턴을 더 잘 관리하기 위해 농장 전체에 일방통행 소 길들을 설치했습니다. 농장은 N개의 목초지로 구성되어 있으며, 편의상 1부터 N까지 번호가 매겨져 있고, 각 일방통행 소 길은 한 쌍의 목초지를 연결합니다. 예를 들어, 목초지 X에서 목초지 Y로 연결되는 길이 있다면, 소들은 X에서 Y로는 이동할 수 있지만 Y에서 X로는 이동할 수 없습니다.