Codeforces Round #743 (Div.2) A, B

A. Countdown

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        int n;
        cin >> n;
        string s;
        cin >> s;
        int ans = s[n-1]-'0';
        for(int i = 0; i < n-1; i++){
            if(s[i] != '0'){
                ans += s[i]-'0';
                ans += 1;
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

각 자리의 숫자들을 1의 자리수와 바꾸어 하나씩 줄이는 것이 최적해이다.

B. Swaps

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        int n;
        cin >> n;
        vector<int> a(n+1), b(n+1);
        vector<int> c(2*n+1, INF);
        for(int i = 1; i <= n; i++){
            cin >> a[i];
            c[a[i]] = i;
        }
        for(int i = 1; i <= n; i++){
            cin >> b[i];
            c[b[i]] = i;
        }
        int m;
        m = INF;
        for(int i = 1; i <= 2*n; i++){
            if(i%2 == 1) m = min(m, c[i]);
            else c[i] = m;
        }
        m = INF;
        for(int i = 1; i <= n; i++){
            m = min(m, (c[b[i]]-1)+(i-1));
        }
        cout << m << "\n";
    }
    return 0;
}

배열 a 를 b 보다 사전적으로 작게 만드는 문제였는데, 이 문장을 읽고 a 만을 바꾸어 b 보다 사전적으로 작게 만드는 문제로 잘못 해석했다.

a, b 배열 모두 원소의 위치를 바꿀 수 있으므로 다시 해결방법을 생각해야 했다.

b 배열의 어떤 수 bi 보다 작은 a 의 값들 중에서, 맨 앞으로부터 가장 가까이에 있는 원소를 빠른 시간내에 찾아야 한다.

bi 보다 작은 홀수들 중 최소값을 구할 때, bi 값을 오름차순으로 늘려가며 구하면 앞서 구해 놓았던 최소값에 하나의 새로운 값을 갱신하기만 하면 되므로 O(n) 안에 모두 계산이 가능하고, 한 번의 참조로 교체 횟수를 구할 수 있게 된다.

C. Book (Upsolving)

C++