10월 3주차 PS 기록 (BOJ 13134, 4792, 16136)

강릉에 왔다!

그냥 그렇다..

 

Baseball Watching

어려웠다 ㅠㅠ

 

회차가 $9$회 이내로 제한되고, 선택의 경우가 $3$가지라는 작은 제한을 잘 이용해야 될 것 같았다.
회차마다 $3$가지 선택을 하는걸 다르게 생각하면 $N$명을 $3$개의 집합으로 분할한 거고, 결국 $9$회 걸친 합집합의 최대 크기 및 최소 크기를 구하는 문제로 바뀐다고 생각했다.

그렇게 생각해보니 $3^9\times N$에 어느 정도의 상수가 붙은 풀이가 바로 나올 수 있었는데, 간소한 차이로 못 풀 것처럼 보였다.

다른 관찰이 그다지 보이지 않아서 이걸 조금만 최적화시켜도 풀리지 않을까 생각했다.

근데 집합을 bitset<N>으로 관리하면 or 연산이 $N/32$~$N/64$에 된다는 얘기를 들어서 내 경우에 적용해보니 함수의 오버헤드가 걸리면서도 애매하게 될 것도 같았다.

 

확신없는 '될 수도 있지 않을까?'라는 생각으로 풀었을 때 결코 맞춘 적이 없었다. 그래서 포기했다. (잘했다👍)

 

결국 모범 답안의 방향은 달랐다.

완전 탐색을 최적화 시키는 것이었다. (딱히 논리적으로 어떤 선택을 할 지 정할 수는 없을 것 같다는 감이 맞았다)

$3^9$가지의 선생님의 선택에 대해서 각각 학생들의 경우를 따지긴 하는데, $3^9$ 안에 학생들의 정보를 꾸겨 넣어서 따지게 되면 $3^9\times N$이 아닌 $3^9\times 3^9$이 되어서 훨씬 효율적으로 바뀐다.

그 다음은 선생님의 선택이 고정된 상태에서 선생님의 어떤 선택과도 겹치지 않게 탐색하면 가지가 $2$개가 되기 때문에 $3^9\times 2^9$으로 줄어든다는 것을 알 수 있다. 이를 $3$진법을 이용하여 관리하면 메모리에도 문제가 사라진다.

 

문제의 특정 부분을 고정하고 나머지를 고려하자는 발상과 세는 관점을 바꿔보자는 발상이 문제의 포인트라고 생각한다. 앞으로도 이런 두 가지 생각을 자주 해보도록 하자.

 

코드

#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 dbg(x) cerr << #x << ": " << x << '\n'
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)

int n, S, cnt[19683];
int mx = 0, mn = 1e9;

int alive(int T, int k = 0) {
    if (k == 9) return cnt[S];
    int r = 0;
    rep(i,0,2) if (T%3 != i) {
        S *= 3, S += i;
        r += alive(T/3,k+1);
        S /= 3;
    }
    return r;
}

int main() {
    scanf("%d", &n);
    rep(i,1,n) {
        int s = 0;
        rep(j,0,8) {
            int x; scanf("%d", &x);
            s *= 3, s += x-1;
        }
        cnt[s]++;
    }
    rep(teacher,0,19682) {
        int a = alive(teacher);
        mup(mn,a), Mup(mx,a);
    }
    printf("%d %d", mn, mx);
}

 

레드 블루 스패닝 트리

캬- 재밌는 문제다.

뭐 이런 과정을 거쳤다.

저게 1시간 반동안 고민한 과정인데, 정리하면 이렇다:

• n이 1000인데 이유가 있다, n²도 고민해보기
• 스패닝 트리 관련 문제니까 자르기보다 잇는 방향으로 생각하기
• 총 간선 수가 n-1개니까 사실상 사용할 빨간색 간선의 개수도 n-1-k로 정해진 상황, 대칭적인 면이 있다
• 리프 노드는 없다고 생각해도 된다 (∵어차피 리프 노드에 연결된 간선은 무조건 써야 하니까 예외처리 시키면 된다)

 

• 두 서로소 집합을 연결하는 유일한 간선만 파악해서 미리 처리하면 풀 수 있다
  • 그 간선들을 제거하면 남는 컴포넌트들은 결국 사이클 덩어리? 같은 것들
  • 색깔별 간선 사용 횟수의 최댓값/최솟값을 그 컴포넌트 크기에 맞춰서 파악 가능
  • 종합하면 색깔별 사용수로 가능한 범위가 나오니까 이걸 k랑 비교하면 풀린다

이런 사고 과정이었다.

마지막 핵심 부분을 고민한 자리만 뜯어보면:

 

근데 여기서 초록색 간선들(두 서로소 집합을 연결하는 유일한 간선들)을 파악할 방법이 떠오르지를 않았다.

그래서 "종합하면 색깔별 사용수로 가능한 범위가 나오니까 이걸 k랑 비교하면 풀린다" 부분을 더 고민해보라는 힌트를 받았고,

생각해보니 초록색 간선을 따로 처리할 필요가 없다는 것을 깨달아서 바로 맞췄다. 구현은 5분 안쪽으로 끝냈다.

 

덤으로, 초록색 간선들은 무향 그래프에서의 절선이라고 부르는데, BCC를 이용하면 찾을 수 있다고 한다.

 

 

준하의 정수론 과제 (Divmaster)

발상은 쉬운데 구현이 빡셌다.

거의 문제 보자마자 키보드만 잡고 있었다고 보면 된다. 그걸 2시간동안 붙잡고 있었던게 문제...

 

그래서 이 문제는 구현을 깔끔하고, 능률적으로 하는 방법을 더 고민해야 할 것 같다.

#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 dbg(x) cerr << #x << ": " << x << '\n'
#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 = 100'003, Q = N, A = 1'000'000;
int n, q, a[N][6];
int tau[A+1];
template <typename T, const int N>
struct PURQ {
    T t[2*N]; function<T(const T&,const T&)> op;
    PURQ(T e, function<T(const T&,const T&)> f): op(f) { fill(t,t+2*N,e); }
    T &operator [] (int i) { return t[N+i]; }
    void clear() { fill(t,t+2*N,t[0]); }
    void build() {
        for (int k = N-1; k >= 1; --k) t[k] = op(t[2*k],t[2*k+1]);
    }
    void update(int k, const T &v) {
        assert(0 <= k and k < N);
        for (k += N, t[k] = tau[t[k]]; (k /= 2) >= 1; t[k] = op(t[2*k],t[2*k+1]));
    }
    T query(int a, int b) {
        assert(0 <= a and a < N and 0 <= b and b < N);
        T l = t[0], r = t[0];
        for (a += N, b += N; a <= b; ++a /= 2, --b /= 2) {
            if (a&1) l = op(l,t[a]);
            if (~b&1) r = op(t[b],r);
        }
        return op(l,r);
    }
};
ll ans[Q];
map<int,int> m;
PURQ<ll,N> rsq(0,[](ll x, ll y){return x+y;});

void input_and_precalc() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> q;
    rep(i,1,n) cin >> a[i][0], rsq[i] = a[i][0];
    rsq.build();
    rep(x,1,A) {
        for (int u = x; u <= A; u += x) tau[u]++;
    }
    rep(i,1,n) {
        m[i] = 0;
        rep(j,1,5) a[i][j] = tau[a[i][j-1]];
    }
}

int main() {
    input_and_precalc();
    rep(i,1,q) {
        int t, s, e; cin >> t >> s >> e;
        if (t == 1) { // update
            vector<int> to_delete;
            auto x = m.lower_bound(s), y = m.upper_bound(e);
            for (auto it = x; it != y; ++it) {
                auto &[k,v] = *it;
                if (v < 6) rsq.update(k,a[k][v++]);
                else to_delete.push_back(k);
            }
            for (auto d : to_delete) m.erase(d);
        } else { // query
            cout << rsq.query(s,e) << '\n';
        }
    }
}