2022년 2월 PS일지 ★ (BOJ 7040, 12630, 7915)

밥 먹기

문제 링크

7577번: 탐사의 마이너 버전이라고 할 수 있다.

필자는 '탐사'를 자력으로 못 풀었지만, 어쨌든 '탐사'에 사용되는 방법을 배워서 이 문제를 수월하게 풀 수 있었다.

어쩌면 '밥 먹기'를 푼 뒤 '탐사'를 시도하면 풀 수 있을 것 같기도 하다.

풀이

상당히 어려운 문제이고, 아이디어성 문제이다.

문제에서 요구하는 것을 간단하게 바꾸면 '연립 부등식의 해를 결정해라' 정도의 얘기가 된다.

완전한 결정을 의미하는 것은 아니지만 아무튼.

 

신기하게도 떨어지는 거리의 범위가 큰 것이 문제의 힌트가 된다.

'탐사'의 경우는 범위가 적어서 오히려 접근이 어려웠다.

 

따라서 DP의 가능성은 적다.

$1\cdots N$을 쭉 나열하고 범위를 표시하면서 파악하면 감을 잡기 쉽다.

 

$D_1$을 원점으로 잡고 $0$값을 매기자.

나머지 $D_i$들은 원점으로부터의 최대 거리를 나타낸다.

$D_1\le D_2\le \cdots \le D_N$의 상관관계가 보인다.

$|D_1-D_N|$을 찾는 것이 목표이다.

 

$|D_a-D_b|\le k$인데, $|D_a-D_b|\le |D_a-D_c|+|D_c-D_b|\le l$이라면 $D_b=D_a+k$가 아닌 $D_b=D_a+l$이 더 어울린다. (단 $a\le c\le b$)

사이에 최대 거리를 낮춰주는 매개체가 있는 것 같다.

 

위와 같은 관찰로, 문제를 방향 그래프로 모델링하고, 최단경로를 구하면 된다는 것을 알 수 있다.

코드

음의 사이클을 어떻게 다루면 좋을까요?

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>;
#define REP(i,a,b) for (auto i = (a); i <= (b); ++i)
#define mup(x,y) x = min(x,y)

const int N = 1003;
int n, ml, md;
int dist[N];
vector<ii> adj[N];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> ml >> md;
    REP(i,2,n) adj[i].emplace_back(i-1,0);
    REP(i,1,ml) {
        int a, b, d; cin >> a >> b >> d;
        adj[a].emplace_back(b,d);
    }
    REP(i,1,md) {
        int a, b, d; cin >> a >> b >> d;
        adj[b].emplace_back(a,-d);
    }
    fill(dist,dist+N,1e9);
    dist[1] = 0;
    REP(i,1,n) {
        REP(a,1,n) for (auto [b,w] : adj[a])
            mup(dist[b],dist[a]+w);
    }
    REP(a,1,n) for (auto [b,w] : adj[a]) {
        if (dist[b] > dist[a]+w) {
            cout << -1;
            return 0;
        }
    }
    if (dist[n] >= 1e9) cout << -2;
    else cout << dist[n];
}

Crazy Rows

문제 링크

고수분들도 기여를 해두셨던데, 아무리 봐도 어려운 면이 없다.

풀이

댓글 남겨주시면 도와드리겠습니다.

코드

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

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int tc, n; cin >> tc;
    REP(tt,1,tc) {
        cin >> n;
        list<int> l;
        REP(i,1,n) {
            int m = 0;
            REP(j,1,n) {
                char c; cin >> c;
                if (c == '1') m = j;
            }
            l.push_back(m);
        }
        int answer = 0;
        REP(i,1,n) {
            int j = 0;
            bool found = false;
            for (auto it = l.begin(); it != l.end(); ++it, ++j) {
                if (*it <= i) {
                    answer += j;
                    l.erase(it);
                    found = true;
                    break;
                }
            }
            assert(found);
        }
        cout << "Case #" << tt << ": " << answer << '\n';
    }
}

Cave

문제 링크

개 잘 만든 문제. 트리 좋아하면 꼭 풀어보세요.

트리를 같은 크기의 서브트리 $k$개로 분할 가능한 모든 $k$를 구하여라.

풀이

사실 $k$가 정해지면 분할의 형태는 유일하다.

 

'서브트리'는 본래의 의미, '분할트리'는 분할된 서브트리들로 명칭을 구분하자.

전형적이게 $S_i:=i$번 노드의 서브트리의 크기라고 정의하자.

 

분할트리에 집중해보자.

각 분할트리의 루트 노드 $R$은 해당 분할트리의 크기 $n/k$를 $S_R$에 포함하고 있다.

더불어, $S_R$은 $R$의 서브트리 속 다른 분할트리들의 크기의 총합 $t\times n/k$까지도 포함하고 있다.

 

따라서 $S_R=(t+1)\times n/k$이므로 $n/k\mid S_R$.

각 분할트리의 루트노드들은 $n/k$의 배수라는 공통적인 특징을 가진다.

또한, 루트노드가 아니라면 $n/k$의 배수일 수 없다.

 

결국 $S_R$ 중 $n/k$의 배수인 것들의 개수가 $k$라면 제대로 분할된 것이라 할 수 있다.

증명을 해본다면 이런 식으로 생각해 볼 수 있을 것 같다...

$n/k\mid S_i$인 $i$번 노드와 그 부모를 연결하는 간선을 절단하는 시행을 반복하자. 전체트리의 루트노드는 제외하고 생각하자.

그러면 간선을 절단할 때마다 $t\times n/k$와 $u\times n/k$의 두 트리로 쪼개진다.

그런데 이를 $k-1$번 한다면? 크기가 $n/k$인 트리 $k$개로 쪼개질 것이다.

이를 $k-1$번 하는 필요충분조건은 $n/k\mid S_i$인 $i$가 $k-1$개 존재하는 것이다.

따라서 증명 완료.

코드

플3 중에 이렇게 코드 짧은 문제도 없을걸요? ㅋㅋ

진짜 아름다운 문제입니다...

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

const int N = 3e6+3;
int n, sub[N], cnt[N], par[N];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    REP(i,1,n-1) cin >> par[i+1];
    for (int i = n; i >= 1; --i) {
        sub[par[i]] += (++sub[i]);
        cnt[sub[i]]++;
    }
    for (int i = n; i >= 1; --i) {
        if (n%i == 0) {
            int x = 0;
            for (int j = i; j <= n; j += i) x += cnt[j];
            if (x == n/i) cout << n/i << ' ';
        }
    }
}