백준 1055 - 끝이없음

Created At: 2025/03/05

3 min read

핵심 아이디어

문자열이 재귀적으로 반복하는 것을 알 수 있다.

이때 min과 max의 차이가 최대 100개 정도임을 알 수 있고, 우리는 i번째 문자가 주어졌을 때 해당 i 번째 문자가 무엇인지를 알아차리는 함수를 작성하고 이를 100번만 반복하면 원하는 정답을 얻을 수 있다.

i번째 문자가 무엇인지를 알아차리는 것은 이분탐색을 이용해서 찾을 것이다.

예를 들어, abc와 $x$y$z$가 주어졌을 때, 2번 연산한다고 하면 첫번째 $는 abcxabcyabczabc로 변화할 것이다.

연산을 해보면 다음과 같은 수식으로 정리할 수 있다.

k번 연산했다고 가정했을 때, 다음과 같은 전체 문자열 길이를 얻을 수 있다.

n \times \$^{k-1} + m \times \frac{\$^{k-1}-1}{\$-1}

이때, n은 처음 입력 문자열의 길이, $는 문자열 S의 $의 개수, m은 문자열 S에서 $가 아닌 문자의 개수가 된다.

위 수식을 이용해서 이분 탐색을 하여 i번째 문자가 무엇인지를 찾아내는 것이다.
이분 탐색을 해서 k번째 연산을 했을 때 다음 $로 이동해야 할 때가 온다.
(예를 들어, $x$y$z$을 k번 연산했더니 i가 첫번째 $안에 포함되지 않은 경우가 생긴다.)
이때 이동하면서 $가 아닌 문자 번호인지를 체크하고, 만약 $ 영역에 포함된다면 다시 재귀적으로 해결해주고, 그렇지 않다면 해당 문자열을 반환해준다.

코드


cpp
1#include <bits/stdc++.h>
2
3#define endl "\n"
4#define all(v) (v).begin(), (v).end()
5#define all1(v) (v).begin()+1, (v).end()
6#define For(i, a, b) for(int i=(a); i<(b); i++)
7#define FOR(i, a, b) for(int i=(a); i<=(b); i++)
8#define Bor(i, a, b) for(int i=(a)-1; i>=(b); i--)
9#define BOR(i, a, b) for(int i=(a); i>=(b); i--)
10#define ft first
11#define sd second
12
13using namespace std;
14using ll = long long;
15using lll = __int128_t;
16using ulll = __uint128_t;
17using ull = unsigned long long;
18using ld = long double;
19using pii = pair<int, int>;
20using pll = pair<ll, ll>;
21using ti3 = tuple<int, int, int>;
22using tl3 = tuple<ll, ll, ll>;
23
24template<typename T> using ve = vector<T>;
25template<typename T> using vve = vector<vector<T>>;
26
27template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
28template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
29
30const int INF = 987654321;
31const int INF0 = numeric_limits<int>::max();
32const ll LNF = 987654321987654321;
33const ll LNF0 = numeric_limits<ll>::max();
34
35const ll mxn = 1e9+99;
36string p, s;
37ve<string> notDollar;
38ll op, Min, Max;
39// a^b mod c
40ll pow(ll a, ll b) {
41    ll res = 1;
42    while(b) {
43        if(a > mxn) return LNF;
44        if(b%2) res = (res * a);
45        a = (a * a);
46        b >>= 1;
47    }
48    return res;
49}
50
51ll n, dollar, m;
52ll f(ll k) {
53    if(--k == 0) return p.length();
54    if(dollar == 1) return n + m*k;
55    ll dk = pow(dollar, k);
56    if(dk == LNF) return LNF;
57
58    return n*dk + m*(dk-1)/(dollar-1);
59}
60
61void solve() {
62    cin >> p >> s >> op >> Min >> Max;
63    Min--; Max--;
64    string str;
65    int _=0;
66    for(auto c : s) {
67        dollar += (c == '$');
68        m += (c != '$');
69        if(c != '$') str += c;
70        else if(_ != 0) {
71            notDollar.emplace_back(str);
72            str = "";
73        }
74        _++;
75    }
76    if(!str.empty()) notDollar.emplace_back(str);
77    n = p.length();
78
79    string ans;
80    ll opop = f(op+1);
81    for(ll i=Min; i<=Max; i++) {
82        if(i >= opop) {
83            ans += '-';
84            continue;
85        }
86        ll target = i;
87        while(target >= (int)p.length()) {
88            ll lo=1, hi=1e9;
89            while(lo < hi) {
90                ll mid = lo + (hi-lo)/2 + (hi-lo)%2;
91                ll res = f(mid);
92                if(res <= target) lo = mid;
93                else hi = mid-1;
94            }
95            ll res = f(lo);
96            target -= res;
97            for(auto only : notDollar) {
98                if(target < only.length()) {
99                    ans += only[target];
100                    target = -1;
101                    break;
102                }
103                target -= only.length();
104                if(target < res) break;
105                else target -= res;
106            }
107        }
108        if(target != -1) ans += p[target];
109    }
110    cout << ans << endl;
111
112}
113
114int main(void) {
115    ios_base::sync_with_stdio(false);
116    cin.tie(nullptr);
117    cout.tie(nullptr);
118
119    int TC=1;
120//    cin >> TC;
121    FOR(tc, 1, TC) {
122//        cout << "Case #" << tc << ": ";
123        solve();
124    }
125
126
127    return 0;
128}

후기

솔직히 아이디어 자체는 그리 까다롭지 않다고 생각하지만, 구현적인 아이디어가 상당히 까다롭고 반례가 잘 생길 수 밖에 없는 문제라고 생각한다.
필자는 https://testcase.ac/problems/1055 여기의 도움을 받아서 해결했다.
여기서 찾은 반례는 알고보니 pow 연산 시, a가 너무 커지면 안 돼서 막아놓았는데 이걸 $a \times a$ 전에 했어야 했는데 그러지 않아서 생겼던 문제였다.