2022.10.01 PS 일지 (BOJ 3830, 8112, 5573)

교수님은 기다리지 않는다

문제 링크

쉽다.

DSU를 잘 변형해서 풀면 된다. 'JOI 국가의 행사'를 풀어본게 도움이 된 것 같다.

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define all(x) (x).begin(), (x).end()
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)

const int N = 100003, M = N;
int n, m;

int par[N];
ll val[N];
vector<int> sub[N];

void clear() {
    iota(par,par+N,0);
    fill(val,val+N,0);
    rep(i,1,N) sub[i] = {i};
}
int find(int x) {
    if (x == par[x]) return x;
    return par[x] = find(par[x]);
}
int size(int x) {
    return siz(sub[x]);
}
ll diff(int a, int b) { return val[b]-val[a]; }
bool merge(int a, int b, ll w) { // b가 a보다 w만큼 크다, complexity: O(min(sub a, sub b))
    w = val[b]-val[a]-w;
    a = find(a), b = find(b);
    if (a == b) return false;
    if (size(a) > size(b)) swap(a,b), w = -w;
    // b에다가 a 붙여버리고 a의 값들 전부 apply
    for (int x : sub[a]) val[x] += w, sub[b].push_back(x);
    sub[a].clear();
    par[a] = b;
    return true;
}
bool same(int a, int b) {
    return find(a) == find(b);
}

int main() { while (scanf("%d %d ", &n, &m), n != 0)
{
    clear();
    rep(i,1,m) {
        int a, b, w; char c;
        scanf("%c ", &c);
        if (c == '!') {
            scanf("%d %d %d ", &a, &b, &w);
            merge(a,b,w);
        } else {
            scanf("%d %d ", &a, &b);
            if (same(a, b)) {
                printf("%lld\n", diff(a,b));
            } else puts("UNKNOWN");
        }
    }
}}

0과 1-2

문제 링크

어렵다.

$\mathrm{mod}\ N$에 대해 구성해나가면 된다.

$N=1$인 경우를 예외 처리해야 한다.

너무 정수론적으로 접근한게 흠이었다.

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define all(x) (x).begin(), (x).end()
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)

const int N = 1e6+3;
int n;
pair<int,bool> dist[N];
bool visited[N];
queue<int> q;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t; cin >> t; rep(_,1,t)
    {
        cin >> n;
        if (n == 1) {
            cout << "1\n";
            continue;
        }
        fill(visited,visited+n,0);
        visited[1] = true, dist[1] = {-1,1}, q.push(1);
        while (not empty(q)) {
            int s = q.front(); q.pop();
            for (auto [u,d] : {pair<int,bool>((s*10)%n,0),
                               pair<int,bool>((s*10+1)%n,1)}) {
                if (visited[u]) continue;
                visited[u] = true;
                dist[u] = {s,d};
                q.push(u);
                if (u == 0) while (not empty(q)) q.pop();
            }
        }
        if (visited[0]) {
            stack<bool> s; int x = 0;
            while (x >= 0) {
                s.push(dist[x].second);
                x = dist[x].first;
            }
            while (not empty(s)) cout << s.top(), s.pop();
            cout << '\n';
        }
        else cout << "BRAK\n";
    }
}

산책

문제 링크

아이디어가 지린다. $n-1$번 했을 때 배열의 구성을 찾을 수 있으므로 구성한 뒤, 그 위에서 찾아나가면 된다.

간단한데 생각하기 어렵다. 좋은 문제.

#include <bits/stdc++.h>
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
using namespace std;

const int H = 1003, W = 1003;
int h, w, n;
int dp[H][W];
bool b[H][W];

void solve(int i = 1, int j = 1) {
    if (i > h or j > w) {
        printf("%d %d\n",i,j);
        return;
    }
    if (b[i][j]) solve(i,j+1);
    else solve(i+1,j);
}

int main() {
    scanf("%d %d %d", &h, &w, &n);
    rep(i,1,h) rep(j,1,w) {
        int t; scanf("%d ", &t);
        b[i][j] = t;
    }
    dp[1][1] = n-1;
    rep(i,1,h) rep(j,1,w) {
        dp[i+1][j] += dp[i][j]/2+(dp[i][j]%2)*(b[i][j] == 0);
        dp[i][j+1] += dp[i][j]/2+(dp[i][j]%2)*(b[i][j] == 1);
        b[i][j] ^= dp[i][j]%2;
    }
    solve();
}