<div id="readability-page-1" class="page"><div>
 

 <header id="header" itemscope="" itemtype="http://schema.org/WPHeader">
 
 </header>

 <main id="main">
 <div id="content">
 
 

 

 
 
 

 <article itemscope="" itemtype="http://schema.org/Article">
 

 

 

 
 <header>

 
 
 
 

 
 </header>
 

 <div itemprop="articleBody">
 
 
 
 

 
 
 
 












 <h3 id="문제-링크">문제 링크</h3>
<ul>
 <li>http://icpc.me/21824</li>
</ul>

<h3 id="문제-출처">문제 출처</h3>
<ul>
 <li>2021 CCO Day1 2번</li>
</ul>

<h3 id="사용-알고리즘">사용 알고리즘</h3>
<ul>
 <li>DFS/BFS</li>
</ul>

<h3 id="풀이">풀이</h3>
진법의 개념에서 크게 벗어나지 않기 위해서 일단 $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 &gt; 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)$ 정도로 매우 작기 때문에 시간 제한 안에 문제를 해결할 수 있습니다.

<h3 id="전체-코드">전체 코드</h3>
<div><table><tbody><tr><td><pre>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</pre></td><td><pre><code>#include &lt;bits/stdc++.h&gt;
using namespace std;
using ll = long long;

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

void SmallBFS(){
 for(int i=-M; i&lt;=M; i++) Vst[i] = 0;
 queue&lt;ll&gt; Que; Que.push(0); Vst[0] = 1;
 while(!Que.empty()){
 ll v = Que.front(); Que.pop();
 for(int i=1; i&lt;=D; i++){
 ll nxt = v * K + A[i];
 if(abs(nxt) &gt; 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-&gt;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&lt;int&gt; Path(ll n){
 vector&lt;int&gt; 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&lt;=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 &gt;&gt; K &gt;&gt; Q &gt;&gt; D &gt;&gt; M;
 for(int i=1; i&lt;=D; i++) cin &gt;&gt; A[i], G[Mod(A[i])].push_back(i);
 SmallBFS();
 for(int q=1; q&lt;=Q; q++){
 ll n; cin &gt;&gt; n;
 auto path = Path(n);
 if(path.empty()) cout &lt;&lt; "IMPOSSIBLE\n";
 else for(int i=0; i&lt;path.size(); i++) cout &lt;&lt; path[i] &lt;&lt; " \n"[i+1==path.size()];
 }
}
</code></pre></td></tr></tbody></table></div>


 
 </div>

 

 

 

 
 </article>

 
</div>
 </main>

 

 
 
 

 </div></div>

JusticeHui가 PS하는 블로그

문제 링크
http://icpc.me/21824
문제 출처
2021 CCO Day1 2번
사용 알고리즘
DFS/BFS
풀이
진법의 개념에서 크게 벗어나지 않기 위해서 일단 $M \leq K, n \neq 0$인 상황만 생각해 봅시다.
$n = 0$일 때 공집합을 출력하면 안 된다는 이상한 조건이 붙어있습니다. 공집합이 아니라는 것은 마지막에 어떤 원소 $a_i$를 붙여야 한다는 것이고, 당연히 $a_i \equiv 0 \pmod K$를 만족해야 합니다.
마지막으로 $M > K$인 경우를 생각해 봅시다. 이 경우에는 구간을 $K$배만큼 축소가 불가능할 수도 있기 때문에 위에서 설명한 풀이를 적용하지 못합니다.
재귀적으로 탐색하는 깊이가 $O(\log_K N)$ 정도로 매우 작기 때문에 시간 제한 안에 문제를 해결할 수 있습니다.
전체 코드
#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()];
 }
}

백준21824 Weird Numeral System

댓글