[Codeforces] Round #739 (Div.3)

(소스코드 중요 부분만 있습니다.)

 

A. Dislike of Threes

 

Tag : 구현

Time Complexity : 전처리 $O(1666)$, 테스트 케이스 당 $O(1)$

 

3으로 떨어지는 수와 수의 일의 자리에 있는 숫자가 3인 경우를 제외한 나머지의 개수를 세면 된다.

입력으로 주어지는 수의 범위는 1000까지이므로 수가 1000개 뽑힐때까지 전처리하면 된다. (전처리 안 해도 충분히 돈다.)

 

vector<int> v;
 
bool chk(int x) {
    if(x % 3 == 0) return false;
    x %= 10;
    if(x == 3)  return false;
    return true;
}

int main(){
    fastio<>();
 
    for(int i = 1, cnt = 0; cnt < 1000; i++) {
        if(chk(i)) {
            cnt ++;
            v.push_back(i);
        }
    }
 
    int t;cin >> t;
    while(t--){
        int k ;cin >> k;
        cout << v[k - 1] << '\n';
    }
 
    return 0;
}

 

B. Who's Opposite?

 

Tag : 수학

Time Complexity : 테스트케이스 당 $O(1)$

 

1부터 $N$($N$은 짝수)까지의 번호가 원 위에 시계방향으로 존재한다. 간단한 규칙을 찾으면 되는 문제이다.

문제를 요약해보면 주어지는 입력을 보면 $a, b, c$가 주어지는데 a와 b는 서로 마주 보고 있을 때, $c$가 마주 보고 있는 것은 몇 번인지 구하는 문제이다.

 

a, b를 정보를 가지고 아래 식을 통해 N을 알 수 있다.

 

$N$ = $| a - b |$ * 2

 

 

숫자의 번호는 1부터 N까지 존재해야하므로 $a, b, c$가 1 ≤ $a, b, c$ ≤ N인지 확인한다.$c$가 마주보고 있는 수는 ($c$ + | $a$ - $b$ | - 1) % $N$ + 1로 구할 수 있다.

 

int main(){
    fastio<>();
 
    int t;cin >> t;
    while(t--){
        int a, b, c; cin >> a >> b >> c;
        if(a < b) swap(a, b);
        int d = a - b;
        int last = d * 2;
        if(d < b || last < c) cout << -1 << '\n';
        else {
            if(last < d + c) cout << d + c - last << ln;
            else cout << d + c << ln;
        }
    }

    return 0;
}

 

C. Infinity Table

 

Tag : 수학, 구현

Time Complexity : 테스트 케이스 당 $O(log k)$

 

문제에 있는 그림을 보면 (1, 1), (2, 1), (3, 1)는 제곱수인 것을 쉽게 알 수 있다. $k$보다 크거나 같은 수 중 가장 작은 제곱수를 찾고 계산을 해주면 쉽게 풀 수 있다.

 

int main(){
    fastio<>();
 
    int t;cin >> t;
    while(t--){
        int k; cin >> k;
        int c = 1;
        for(c = 1; 1LL * c * c < k; c++);
        int cnt = c * c - (c - 1) * (c - 1);
        int dis = k - (c - 1) * (c - 1) - 1;
        int mid = (cnt - 1) / 2;
        int y = 1, x = c;
        if(dis <= mid) {
            y += dis;
        }
        else {
            y += mid;
            dis -= mid;
            x -= dis;
        }
        cout << y << ' ' << x << '\n';
    }
 
    return 0;
}

 

D. Make a Power of Two

 

Tag : 완전탐색, 문자열

Time Complexity : 테스트 케이스 당 $O(log k)$

 

수가 주어지는데 두 가지 연산이 있다.

1. 수를 이루고 있는 숫자들 중에 하나를 골라 삭제한다.
2. 수의 맨 오른쪽에 하나의 숫자를 추가한다.

두 가지 연산을 통해 주어진 수를 $2^k$로 만들 때 연산의 최소 횟수를 구하는 문제이다.

 

1번 연산할 때 조심해야하는게 있다. 수 301에서 숫자 3을 지운다고 하면 1이 되는 게 아니라 01이 된다. 따라서, 이를 문자열로 처리하면 편하다.

$2^k$로 구성된 수를 보면 k가 0부터 62까지 총 63개로 바꾸는 횟수를 구하고 이 중에 최솟값을 구하면 된다. 바꾸는 횟수를 구하는 건 간단하니 설명은 생략한다.

 

int cal(const string &a, const string &b) {
    int i = 0, r = 0, ret = 0;
    for(;i<siz(a)&&r<siz(b);i++) {
        if(a[i] == b[r]) r++;
        else ret++;
    }
    return siz(a) - i + ret + siz(b) - r;
}
 
int main(){
    fastio<>();
 
    int t;cin >> t;
    while(t--){
        int N; cin >> N;
        int ans = INT_MAX;
        string s = to_string(N);
        for(int i = 0; i < 63; i++) {
            ans = min(ans, cal(s, to_string(1LL << i)));
        }
        cout << ans << ln;
    }
 
    return 0;
}

 

E. Polycarp and String Transformation

 

Tag : 구현, 문자열, 시뮬레이션

Time Complexity : 테스트 케이스 당 $O(s)$

 

문제 지문에 있는 설명대로 문자열을 처리한 결과가 입력으로 주어진다. 

어떤 순서로 문자를 지웠는지는 매우 쉽게 알 수 있다. 입력으로 주어진 문자열을 s라고 해보자. 문자열 s의 맨 뒤부터보면서 최초로 나온 문자열들을 모아서 다시 뒤집어주면 문자를 지운 순서를 알 수 있다.

abacabaaacaac 문자열 본다면 맨 뒤부터 최초로 나온 문자열을 나열해보면 cab가 된다. 이를 뒤집으면 bac로 문자를 지운 순서이다.

 

이제 abacabaaacaac 이 문자열이 어떤 문자열로부터 만들어졌는지 뽑아야한다. 그 어떤 문자열을 x라 하자. 문자열 x를 뽑는 방법은 아래와 같다. 아래 식을 이용해서 구할 수 있다.

 

주어진 문자열 s에 있는 알파벳의 개수 (s_cnt) = 문자열 x에 있는 알파벳의 개수 (x_cnt) * 해당 알파벳을 지운 index (e)

 

index(오른쪽)	1	2	3
지울 문자	b	a	c
지우기 전 문자열	abacaba	aacaa	c
알파벳 개수	(a, b, c) = (4, 2, 1)	(a, b, c) = (4, 0, 1)	(a, b, c) = (0, 0, 1)

 

주어진 문자열 abacabaaacaac에서 알파벳 개수를 구해보면 (a, b, c) = (8, 2, 3)이다. 알파벳이 지워지는 순서는 (a, b, c) = (2, 1, 3)이다. 위에 있는 식을 이용하면 문자열 x에 있는 알파벳의 개수를 구할 수 있다. 식에 적용하여 알파벳의 개수를 구해보면 (a, b, c) = (4, 2, 1)로 주어진 문자열 s에서 길이가 4 + 2 + 1 = 7인 것을 알 수 있다.

 

문자열 x를 뽑았으니, 문자를 지울 순서를 기반으로 다시 시뮬레이션 돌려 주어진 문자열 s랑 같은지 확인하면 된다.

 

-1을 출력하는 경우는 두 가지가 있다.

1. 위에 식에서 s_cnt을 e으로 나눈 나머지가 0이 아닌 경우
2. 문자열 x에서 시뮬레이션 돌렸더니 문자열 s랑 다른 경우

 

int main(){
    fastio<>();
 
    int t;cin >> t;
    while(t--){
        string s; cin >> s;
        int index[27] = { };
        string e;
        for(int i = 0; i < 26; i++) index[i] = -1;
        for(int i = siz(s) - 1; i >= 0; i--) {
            int x = s[i] - 'a';
            if(index[x] != -1) continue;
            index[x] = i;
            e += s[i];
        }
 
        int cnt[27] = {}, total = 0;
        for(char ch : s) cnt[ch - 'a'] ++;
        for(int i = 0; i < 26; i++) total += !!cnt[i];
        int l = 0, len = 0;
        bool answer = true;
 
        for(char ch : e) {
            if(cnt[ch - 'a'] % (siz(e) - l)) answer = false;
            len += cnt[ch - 'a'] / (siz(e) - l);
            l++;
        }
 
        if(!answer) {
            cout << -1 << ln;
            continue;
        }
 
        string L = s.substr(0, len);
        string res = L;
        reverseall(e);
 
        vector<int> used(L.size());
        for(int i = 0; i < siz(e); i++) {
            string cur;
            for(int j = 0; j < siz(L); j++) {
                if(e[i] == L[j]) used[j]=1;
                if(!used[j]) cur+=L[j];
            }
            res+=cur;
        }
        if(res!=s)cout << -1 << ln;
        else cout << L << " " << e << ln;
    }
    
    return 0;
}

 

F1. Nearest Beautiful Number (easy version)

F2. Nearest Beautiful Number (hard version)

 

Tag : 그리디, 완전탐색

Time Complexity : 테스트 케이스 당 $O(10*10*log 10)$

 

hard version을 풀면 easy version을 그냥 풀 수 있다.

 

문제를 요약하자면, $N$보다 크거나 같은 수에서 최대 $K$가지 숫자로 구성된 수들의 최소를 구하는 것이다.

 

주어지는 수의 길이가 $L$이라 했을 때, 찾아야 하는 수의 길이는 반드시 $L$인 것을 쉽게 알 수 있다.

따라서, 맨 앞에 숫자를 0부터 9까지 둘 수 있는지, 사용한 숫자의 가짓수가 몇인지 체크하면서 선택하면 된다.

여기서 조심해야할 것은, 수의 맨 앞에 0이 올 수 없으므로, 1부터 보도록 하면 된다.

 

int main(){
    fastio<>();
 
    int t;cin >> t;
    ll pw[11] = {1};
    ll prefix[11] = { 0 };
    for(int i = 1; i <= 10; i++) pw[i] = pw[i - 1] * 10;
    for(int i = 1; i <= 10; i++) prefix[i] = prefix[i - 1] + pw[i - 1];
    while(t--){
        set<int> st;
        ll N, K; cin >> N >> K;
        int cnt = 0;
        while(pw[cnt] <= N) cnt ++;
        int ans = 0;
        for(int i = cnt - 1; i >= 0; i--) {
            for(int j = 0; j <= 9; j++) {
                if((int)st.size() < K) {
                    bool exist = st.count(j); st.insert(j);
                    int mx = (int)st.size() == K ? *st.rbegin() : 9;
                    if(ans + pw[i] * j + prefix[i] * mx < N) {
                        if(!exist)st.erase(j);
                        continue;
                    }
                }
                else {
                    if(st.count(j)) {
                        if(ans + pw[i] * j + prefix[i] ** st.rbegin() < N) continue;
                    }
                    else continue;
                }
                ans += pw[i] * j;
                break;
            }
        }
        cout << ans << ln;
    }
    
    return 0;
}