03/04 PS 문제풀이

작성일 | In

28424 - 의리 게임(G3)

$N$명의 학생이 각각 주량 $A_i$를 가지고 있습니다. 다음과 같은 쿼리를 처리하면 됩니다.
1 i x: $i$번 학생부터 용량 $x$만큼 의리주를 시킵니다. 학생은 자기 주량만큼 마시면 술을 다음 사람에게 넘깁니다.
2 i: $i$​번 학생이 지금까지 마신 술의 양을 출력합니다.

현재까지 주량에 도달하지 않은 학생 번호를 set으로 관리하고, 주량에 도달하게 되면 set에서 원소를 제거합니다. 주량에 도달하지 않은 다음 학생을 효율적으로 찾기 위해 set의 lower_bound 기능을 사용할 수 있습니다. 원소 제거는 최대 $N$번 일어나므로 효율적으로 문제를 풀 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, q; cin >> n >> q;
    vector<int> a(n), ans(n);
    for(int i=0; i<n; i++) {
        cin >> a[i];
    }
    set<int> st;
    for(int i=0; i<n; i++) {
        st.insert(i);
    }
    while(q--) {
        int op; cin >> op;
        if(op == 1) {
            int i, x; cin >> i >> x; i--;
            if(st.lower_bound(i) == st.end()) {
                continue;
            }
            int id = *st.lower_bound(i);
            while(1) {
                if(ans[id] + x < a[id]) {
                    ans[id] += x;
                    break;
                } else {
                    x -= a[id] - ans[id];
                    ans[id] = a[id];
                    st.erase(st.find(id));
                }
                if(st.lower_bound(id + 1) == st.end()) break;
                id = *st.lower_bound(id + 1);
            }
        } else {
            int id; cin >> id; id--;
            cout << ans[id] << '\n';
        }
    }
}

3964 - 팩토리얼과 거듭제곱(G2)

$N!(1 \leq N \leq 10^{18})$이 $K(1\leq K\leq 10^{12})$로 최대 몇번 나누어 떨어지는지 구하는 문제입니다.
$K$를 소인수분해 한 후, 각 소수 성분이 $N!$에 몇 번 들어가는지 계산 후 $K$에서의 지수로 나누어 준 값 중 최소값이 답이 됩니다. $O(T\sqrt k)$에 문제를 해결할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void solve() {
    ll n, k; cin >> n >> k;
    vector<pair<ll, int>> a;
    for(ll i=2; i*i<=k; i++) if(k%i==0) {
        int cnt = 0;
        while(k % i == 0) {
            k /= i;
            cnt++;
        }
        a.push_back({i, cnt});
    }
    if(k != 1) a.push_back({k, 1});
    ll ans = LLINF;
    for(auto [x, t] : a) {
        ll v = n;
        ll tot = 0;
        while(v) {
            tot += v / x;           
            v /= x;
        }
        ans = min(ans, tot / t);
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t; cin >> t;
    while(t--) {
        solve();
    }
}