과거 청산 챌린지 #2

지난번에 이어 다이아 4를 계속 풀고 있다.

 

남은 문제들이 대부분 풀기 싫게 생겼지만, 이런 문제들을 푸는 연습도 중요한 것 같다.

 

남은 문제: 69 → 65문제

BOJ 8310. Riddle

간단한 2SAT 문제이지만 문제에 등장하는 그래프의 크기가 너무 크다는 게 문제다. atcoder의 SCC 라이브러리를 이용해 짜니 2초 정도에 통과했다.

#include <bits/stdc++.h>
#include <atcoder/scc>

using namespace std;
using namespace atcoder;

typedef long long ll;

int n, m, k;
vector<int> county[1'000'005];
int where[1'000'005];
int idx[1'000'005], ord[1'000'005];
int sccNum[4'000'005];
int ans[1'000'005], has[1'000'005], which[1'000'005]; // ans 1: true, 2: false

int main(){
    #ifndef LOCAL
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #endif

    cin >> n >> m >> k;

    scc_graph G (n*4); // 0: true, 1: false, 2: L, 3: R
    for(int i=1; i<=m; i++){
        int x, y;
        cin >> x >> y;
        x--, y--;
        G.add_edge(n+x, y);
        G.add_edge(n+y, x);
    }

    int cnt = 0;
    for(int i=0; i<k; i++){
        int w;
        cin >> w;
        county[i].resize(w);

        int L = cnt;
        for(int j=0; j<w; j++){
            cin >> county[i][j];
            county[i][j]--;
            idx[county[i][j]] = cnt;
            ord[cnt] = county[i][j];
            where[county[i][j]] = i;
            cnt++;
        }
        int R = cnt - 1;

        for(int j=L; j<=R; j++){
            if(j>L) G.add_edge(ord[j], n*2+j-1);
            if(j<R) G.add_edge(ord[j], n*3+j+1);
            G.add_edge(n*2+j, n+ord[j]);
            G.add_edge(n*3+j, n+ord[j]);
        }
        for(int j=L; j<R; j++){
            G.add_edge(n*2+j+1, n*2+j);
            G.add_edge(n*3+j, n*3+j+1);
        }
    }

    vector<vector<int>> scc = G.scc();
    for(int i=0; i<(int)scc.size(); i++){
        // cout << "SCC " << i << ": ";
        for(int v : scc[i]){
            sccNum[v] = i;
            // cout << v << ' ';
        }
        // cout << '\n';
    }

    for(int i=0; i<n; i++){
        if(sccNum[i] == sccNum[i+n]){
            cout << "NIE";
            return 0;
        }
    }

    for(vector<int> &v: scc){
        bool canFalse = true;
        for(int x: v){
            if((x < n && ans[x] == 1) || (n <= x && x < 2*n && ans[x-n] == 2)){
                canFalse = false;
                break;
            }
        }

        if(canFalse){
            for(int x: v){
                if(x < n) ans[x] = 2;
                else if(n <= x && x < 2*n) ans[x-n] = 1, has[where[x-n]] = 1, which[where[x-n]] = x-n;
            }
        }
        else{
            for(int x: v){
                if(x < n) ans[x] = 1, has[where[x]] = 1, which[where[x]] = x;
                else if(n <= x && x < 2*n) ans[x-n] = 2;
            }
        }
    }

    cout << "TAK\n";
    for(int i=0; i<k; i++){
        cout << (has[i] ? which[i]+1 : county[i][0]+1) << ' ';
    }
}

BOJ 15288. Final Level

문제를 보면 알겠지만 그다지 어려워 보이는 문제는 아니다. 다만 다양한 케이스 처리를 실수 없이 깔끔하게 하는 것이 관건인 문제이다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void solve(){
    ll x, y, n;
    cin >> x >> y >> n;

    ll flipH = 1, flipV = 1;
    if(x < 0) x = -x, flipH = -1;
    if(y < 0) y = -y, flipV = -1;

    ll MIN = 0, MAX = 1e9, ANS = 1e9;
    ll P = n, Q = n-1;
    while(MIN <= MAX){
        ll MID = (MIN + MAX) / 2;
        if(max(x, y) <= P*MID-1 && x + y <= (P+Q) * MID - 1) ANS = MID, MAX = MID - 1;
        else MIN = MID + 1;
    }

    vector<pair<ll, ll> > ans;
    ll cx = 0, cy = 0;
    for(int turn=1; turn<=ANS; turn++){
        ll nx = x - cx, ny = y - cy;
        ll px, py;

        bool dir = nx >= ny;
        if(turn == ANS){
            if(ny == n || nx == 0) dir = 0;
            else dir = 1;
        }
        if(dir){
            if(turn > 1) cx++;
            px = cx, py = min(cy+n-1, y);
            cx = px + n - 1, cy = py;
        }
        else{
            if(turn > 1) cy++;
            py = cy+n-1, px = cx;
            cy = py, cx = min(cx+n-1, x);
        }
        ans.push_back(make_pair(px, py));
    }

    cout << (int)ans.size() << '\n';
    for(auto [x, y]: ans){
        ll verX = x, verY = y - n + 1;
        ll horX = x + n - 1, horY = y;
        if(flipH == -1) verX = -verX, horX = -horX;
        if(flipV == -1) verY = -verY, horY = -horY;
        cout << verX << ' ' << verY << ' ' << horX << ' ' << horY << '\n';
    }
}

int main(){
    #ifndef LOCAL
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #endif

    int t;
    cin >> t;
    while(t--){
        solve();
    }
}

BOJ 28007. LaLa and Magic Stone

문제를 보면 블록을 뭔가 그리디하게 배치하는 방식으로 풀 수 있을 것 같은 느낌이 든다. 정확히는 저것 말고 풀 수 있는 방법이 없을 것 같은 느낌이 든다. 대각선 방향으로 훑으면서 그리디하게 채우려고 노력한다면, 조금 많은 케웍을 통해 그리디한 전략을 만들 수 있다. 정확히는 주변 일부 칸들을 보면서 어떤 방향으로 채워야 하는지가 거의 확정되고, 문제의 예제 1과 같이 2가지로 채울 수 있는 경우를 제외하고는 답이 유일하거나 없다.

#include <bits/stdc++.h>

using std::string;
using std::cin, std::cout;
using std::ios_base;

typedef long long ll;
const ll MOD = 998'244'353;

int n, m;
int arr[1002][1002];

ll ans = 1;

inline int get(int x, int y){
    if(x<1 || x>n || y<1 || y>m) return 0;
    return arr[x][y];
}

inline void set(int x, int y){
    if(x<1 || x>n || y<1 || y>m || !arr[x][y]){
        cout << 0;
        exit(0);
    }
    arr[x][y] = 0;
}

int xx[]={0, 1, 0, -1}, yy[]={1, 0, -1, 0}; // RDLU
inline void set(int x, int y, int dir){
    for(int i=-1; i<=1; i++) for(int j=-1; j<=1; j++){
        if(i==0 && j==0) continue;
        if(i==xx[dir] && j==yy[dir]) continue;
        set(x+i, y+j);
    }
}

void print(){
    cout << "Ans: " << ans << "\n";
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cout << arr[i][j];
        }
        cout << "\n";
    }
}

int main(){
    #ifndef LOCAL
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #endif

    cin >> n >> m;
    for(int i=1; i<=n; i++){
        string s;
        cin >> s;
        for(int j=0; j<m; j++){
            arr[i][j+1] = (s[j] == '0');
        }
    }

    for(int s=2; s<=n+m; s++){
        for(int r=1; r<=n; r++){
            int c = s-r;
            if(c<1 || c>m || !get(r, c)) continue;

            int d[4] = {get(r+1, c+2), get(r+2, c+1), get(r+1, c), get(r, c+1)};
            int cnt=d[0]+d[1]+d[2]+d[3];
            if(cnt < 3){
                cout << 0;
                return 0;
            }

            if(cnt == 3){
                set(r+1, c+1, !d[0] ? 0 : !d[1] ? 1 : !d[2] ? 2 : 3);
                // print();
                continue;
            }

            if(get(r+1, c+1)){ // 안쪽이 차 있는 경우
                int a = get(r+1, c-1);
                if(a){
                    ans = (ans * 2) % MOD;
                    set(r+1, c+1, 2);
                    set(r+2, c, 0);
                }
                else{
                    ans = (ans * 2) % MOD;
                    set(r+1, c+1, 0);
                    set(r+2, c+2, 2);
                }
            }
            else{
                int x = get(r-1, c+2);
                int b = get(r+2, c-1);
                int y = get(r+2, c+3);
                if(x){
                    set(r+1, c+1, 0);
                    set(r, c+3, 2);
                }
                else if(b){
                    set(r+1, c+1, 1);
                    set(r+3, c, 3);
                }
                else if(y){
                    set(r+1, c+1, 1);
                    set(r+3, c+2, 3);
                }
                else{
                    set(r+1, c+1, 0);
                    set(r+2, c+3, 2);
                }
            }
            // print();
        }
    }

    cout << ans;
}

BOJ 19838. Circuit

우선 회로를 직렬/병렬로 나눠 구성하기만 하면 자명한 DP가 된다. 각 성분에 대해 트리를 만드는 경우의 수와 트리에서 한 간선을 뺀 형태, 즉 n-2개의 간선으로 cut이 된 상태를 만드는 경우의 수를 구해 둔다. 그럼 직렬/병렬에 따라 서로가 서로를 호출하는 DP 형태가 만들어져서 문제가 쉬워진다.

 

다만 문제는 저 직렬/병렬을 구현하는 파트이다. 이 부분이 엄청나게 까다롭고 전체 문제의 난이도를 결정한다.

 

문제에서 주어진 것과 같은 그래프를 series-parallel graph라고 부른다. Wikipedia에서 알게 된 사실인데, 이런 그래프는 다음 두 과정 중 하나를 반복해서 적용하는 것으로 축약할 수 있다. (즉, 반복적으로 아래 연산 중 하나를 적용하여 노드 $2$개 (소스와 싱크), 간선은 $(s, t)$ 하나뿐인 그래프로 변경할 수 있다.)

• 간선 $(u, v)$가 여러 개일 때, 하나만 남긴다.
• (소스나 싱크가 아닌) 정점 $v$의 차수가 $2$이고 두 이웃 노드가 $a$, $b$인 경우, 간선 $(a, v)$와 $(b, v)$를 제거하고 간선 $(a, b)$를 추가한다.

위 과정은 std::set을 이용해 반복적으로 처리해줄 수 있고, 위 과정을 시행하며 동시에 트리 구조를 구조체로 구조화해주는 것이 어렵지 않다. 여기까지 하고 나면 위에서 설명한 쉬운 DP를 통해 문제를 해결할 수 있다.

 

다만 여기까지 생각해 놓고도 오랜 시간 동안 TLE를 받았는데, std::multimap에서 count 함수가 선형이 될 수 있다는 사실을 인지하지 못했다. 이 부분을 고치니 정답을 받았다.

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")

using namespace std;

typedef long long ll;
const ll MOD = 998'244'353;

void input();
void encodeCircuit();
void solve();

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    input();
    encodeCircuit();
    solve();
}

int n, m;
vector<int> edge[100005];

void input(){
    cin >> n >> m;
    for(int i=1; i<=m; i++){
        int u, v;
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
}

int cm[300005], lc[300005], rc[300005], ccnt, root;

int newCircuit(){
    int idx = ++ccnt;
    cm[idx] = lc[idx] = rc[idx] = 0;
    return idx;
}
int newCircuit(int mode, int l, int r){
    int idx = ++ccnt;
    cm[idx] = mode;
    lc[idx] = l;
    rc[idx] = r;
    return idx;
}
pair<ll, ll> solveCircuit(int idx){
    if(cm[idx] == 0){
        return make_pair(1, 1);
    }
    pair<ll, ll> lp = solveCircuit(lc[idx]);
    pair<ll, ll> rp = solveCircuit(rc[idx]);
    if(cm[idx] == 1){
        return make_pair((lp.first * rp.first) % MOD,
                         (lp.first * rp.second + lp.second * rp.first) % MOD);
    }
    else{
        return make_pair((lp.first * rp.second + lp.second * rp.first) % MOD,
                         (lp.second * rp.second) % MOD);
    }
}

multimap<pair<int, int>, int> circuitMap;
map<pair<int, int>, int> circuitCnt;
set<pair<int, int>> multi;
multiset<pair<int, int>> adj;
int deg[100005];
set<int> deg2;
int totalCnt;

void insertEdge(int u, int v, int circuit = -1){
    if(u>v) swap(u, v);
    totalCnt++;

    circuitMap.insert({{u, v}, circuit != -1 ? circuit : newCircuit()});
    circuitCnt[{u, v}]++;
    if(circuitCnt.find({u, v}) != circuitCnt.end() && circuitCnt[{u, v}] == 2){
        multi.insert({u, v});
    }

    if(deg[u] == 2 && u!=1 && u!=n) deg2.erase(u);
    if(deg[v] == 2 && v!=1 && v!=n) deg2.erase(v);
    adj.insert({u, v});
    adj.insert({v, u});
    deg[u]++, deg[v]++;
    if(deg[u] == 2 && u!=1 && u!=n) deg2.insert(u);
    if(deg[v] == 2 && v!=1 && v!=n) deg2.insert(v);
}

int getOneEdge(int u, int v){
    if(u>v) swap(u, v);

    if(circuitCnt.find({u, v}) != circuitCnt.end() && circuitCnt[{u, v}] == 2){
        multi.erase({u, v});
    }

    auto it = circuitMap.find({u, v});
    int res = it->second;
    circuitMap.erase(it);
    circuitCnt[{u, v}]--;
    if(circuitCnt[{u, v}] == 0){
        circuitCnt.erase({u, v});
    }

    if(deg[u] == 2 && u!=1 && u!=n) deg2.erase(u);
    if(deg[v] == 2 && v!=1 && v!=n) deg2.erase(v);
    adj.erase(adj.find({u, v}));
    adj.erase(adj.find({v, u}));
    deg[u]--, deg[v]--;
    if(deg[u] == 2 && u!=1 && u!=n) deg2.insert(u);
    if(deg[v] == 2 && v!=1 && v!=n) deg2.insert(v);
    totalCnt--;
    return res;
}

void resolveMulti(int u, int v){
    int c1 = getOneEdge(u, v), c2 = getOneEdge(u, v);
    int nc = newCircuit(2, c1, c2);
    insertEdge(u, v, nc);
}

void resolveDeg2(int x){
    int a = -1, b = -1;
    {
        auto it = adj.lower_bound({x, -1});
        a = it->second;
        ++it;
        b = it->second;
    }

    int c1 = getOneEdge(x, a);
    int c2 = getOneEdge(x, b);
    int nc = newCircuit(1, c1, c2);
    insertEdge(a, b, nc);
}

void encodeCircuit(){
    for(int i=1; i<=n; i++){
        for(int j: edge[i]){
            if(i>j) continue;
            insertEdge(i, j);
        }
    }

    while(totalCnt > 1){
        if(!multi.empty()){
            pair<int, int> tmp = *multi.begin();
            resolveMulti(tmp.first, tmp.second);
        }
        else if(!deg2.empty()){
            int x = *deg2.begin();
            resolveDeg2(x);
        }
        else{
            cout << "Something went wrong";
            exit(1);
        }
    }

    root = circuitMap.begin()->second;
}

void solve(){
    cout << solveCircuit(root).first;
}