백준21824 Weird Numeral System

작성일 | In

문제 링크

  • https://icpc.me/21824

문제 출처

  • 2021 CCO Day1 2번

사용 알고리즘

  • DFS/BFS

풀이

진법의 개념에서 크게 벗어나지 않기 위해서 일단 $M \leq K, n \neq 0$인 상황만 생각해 봅시다.
이런 상황에서는 매 단계마다 $n$이 존재할 수 있는 구간을 $[-K^t, K^t]$에서 $[-K^{t-1}, K^{t-1}]$으로 축소시킬 수 있습니다. $n \equiv a_i \pmod K$인 $a_i$를 마지막에 붙인다고 가정한 다음, $(n-a_i)/K$에 대해서 문제를 해결하면 되기 때문입니다. 따라서 $M \leq K$이면 재귀적으로 문제를 해결할 수 있습니다.

$n = 0$일 때 공집합을 출력하면 안 된다는 이상한 조건이 붙어있습니다. 공집합이 아니라는 것은 마지막에 어떤 원소 $a_i$를 붙여야 한다는 것이고, 당연히 $a_i \equiv 0 \pmod K$를 만족해야 합니다.
마지막에 $a_i$를 붙여서 $0$이 되기 위해서는 $(-a_i/K)\times K + a_i$ 꼴이 되어야 합니다. 따라서 위에서 설명한 풀이를 이용해 $-a_i/K$를 만드는 방법을 구하면 됩니다.

마지막으로 $M > K$인 경우를 생각해 봅시다. 이 경우에는 구간을 $K$배만큼 축소가 불가능할 수도 있기 때문에 위에서 설명한 풀이를 적용하지 못합니다.
어떤 상황에서 축소에 실패하는지 살펴봅시다. 대부분의 경우에는 $a_i$를 더하는 것보다 $K$로 나누는 것의 영향력이 더 크기 때문에 축소를 할 수 있습니다. 하지만 $\vert n \vert \leq M$이면 $a_i$를 더하는 것으로 인해서 $[-M, M]$ 범위 밖으로 벗어나는 일이 발생할 수 있습니다. 따라서 절댓값이 $M$ 이하인 수들에 대해서는 다른 방법으로 경로를 탐색해야 합니다.
다행히도 $M$이 $2\,500$ 정도로 굉장히 작기 때문에 단순히 BFS를 이용해 전처리해도 괜찮습니다. $n$을 계속 축소하다가 $\vert n \vert \leq M$이 되면 BFS로 전처리한 경로를 사용하면 됩니다.

재귀적으로 탐색하는 깊이가 $O(\log_K 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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int K, Q, D, M, A[5050];
vector<int> G[1010101];
unordered_map<ll, int> Vst, Prv;
inline ll Mod(ll t){ return (t %= K) >= 0 ? t : t + K; }

void SmallBFS(){
    for(int i=-M; i<=M; i++) Vst[i] = 0;
    queue<ll> Que; Que.push(0); Vst[0] = 1;
    while(!Que.empty()){
        ll v = Que.front(); Que.pop();
        for(int i=1; i<=D; i++){
            ll nxt = v * K + A[i];
            if(abs(nxt) > M || Vst[nxt]) continue;
            Que.push(nxt); Vst[nxt] = 1; Prv[nxt] = A[i];
        }
    }
}

int Check(ll n){
    if(auto it=Vst.find(n); it != Vst.end()) return it->second;
    for(auto i : G[Mod(n)]) if(Check((n - A[i]) / K)) { Prv[n] = A[i]; return Vst[n] = 1; }
    return Vst[n] = 0;
}

vector<int> Path(ll n){
    vector<int> res;
    if(n != 0){
        if(!Check(n)) return {};
        while(n != 0) res.push_back(Prv[n]), n = (n - Prv[n]) / K;
        reverse(res.begin(), res.end());
        return res;
    }
    else{
        for(int i=1; i<=D; i++) if(A[i] == 0) return {A[i]};
        for(auto i : G[0]){
            if(!Check(-A[i] / K)) continue;
            res = Path(-A[i] / K); res.push_back(A[i]);
            return res;
        }
        return {};
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> K >> Q >> D >> M;
    for(int i=1; i<=D; i++) cin >> A[i], G[Mod(A[i])].push_back(i);
    SmallBFS();
    for(int q=1; q<=Q; q++){
        ll n; cin >> n;
        auto path = Path(n);
        if(path.empty()) cout << "IMPOSSIBLE\n";
        else for(int i=0; i<path.size(); i++) cout << path[i] << " \n"[i+1==path.size()];
    }
}