Codeforces Round #718 (Div. 1 + Div. 2) A~C

A. Sum of 2050

C++

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

int main(){
    fastio;
    int tc;
    cin >> tc;
    while(tc--){
        ll n;
        cin >> n;
        int ans = 0;
        for(int i = 15; i >= 0; i--){
            ll v = 2050*ceil(pow(10, i));
            ans += n/v;
            n -= (n/v)*v;
        }
        if(n) cout << -1 << "\n";
        else cout << ans << "\n";
    }
    return 0;
}

제일 큰 2050 수 부터 거꾸로 n 에서 가능한대로 빼었을 때 0 이되면 몫들의 합을, 값이 남으면 -1 를 출력하면 된다.

B. Morning Jogging

C++

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

bool compare(pair<int, int> a, pair<int, int> b){
    return a.first < b.first;
}

int main(){
    fastio;
    int tc;
    cin >> tc;
    while(tc--){
        int n, m;
        cin >> n >> m;
        vector<vector<int>> b(n);
        vector<map<int, int>> M(n);
        int t;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                cin >> t;
                b[i].push_back(t);
                M[i][t]++;
            }
        }
        vector<pair<int, int>> mb;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                mb.push_back({b[i][j], i});
            }
        }
        sort(all(mb), compare);
        vector<vector<int>> ans(n, vector<int>(m, 0));
        for(int i = 0; i < m; i++){
            ans[mb[i].second][i] = mb[i].first;
            M[mb[i].second][mb[i].first]--;
        }
        vector<vector<int>> remain(n);
        for(int i = 0; i < n; i++){
            for(auto iter = M[i].begin(); iter != M[i].end(); iter++){
                for(int j = 0; j < iter->second; j++){
                    remain[i].push_back(iter->first);
                }
            }
        }
        for(int i = 0; i < n; i++){
            int s = remain[i].size();
            int j = 0;
            int k = 0;
            while(s){
                if(ans[i][j] == 0){
                    ans[i][j] = remain[i][k];
                    k++;
                    s--;
                }
                j++;
            }
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                cout << ans[i][j] << " ";
            }
            cout << "\n";
        }
    }
    return 0;
}

n+1 개의 지점 사이사이에 모든 달리기 주자가 하나씩 선택할 수 있도록 길이 m 개씩 존재한다. 주자가 목적지까지 이동하며 지나간 모든 길 중 최소 length 가 tiredness 값일 때, 모든 주자의 tiredness 값의 합이 최소가 되도록 하는 길의 선택을 찾으려고 한다. 행을 i 번째 길, 열을 i 번째 달리기 주자, 값이 주자가 선택한 길의 length 인 n x m 크기의 2차원 배열로 관리한다. 모든 주자는 순서에 상관없이 존재하는 길의 length 중 작은 값 부터 하나씩 선택했을 때가 최적해이므로, 모든 길의 length 를 행 값과 함께 배열에 따로 저장해 length 기준으로 정렬한 후 각 열 마다 하나씩 m 개를 배치한다. 동시에 map 으로 각 행마다 남은 원소의 수를 관리하여 빈 자리에 남은 원소들을 채워넣고 출력하면 된다.

C. Fillomino 2

C++

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

int main(){
    fastio;
    int n;
    cin >> n;
    vector<vector<int>> p(n, vector<int>(n, 0));
    for(int i = 0; i < n; i++){
        cin >> p[i][i];
    }
    for(int i = 0; i < n; i++){
        int x = i;
        int y = i;
        int c = p[i][i]-1;
        while(c){
            if(y-1 >= 0 && p[x][y-1] == 0){
                y--;
                c--;
                p[x][y] = p[i][i];
            }
            else if(x+1 < n && p[x+1][y] == 0){
                x++;
                c--;
                p[x][y] = p[i][i];
            }
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j <= i; j++){
            cout << p[i][j] << " ";
        }
        cout << "\n";
    }
    return 0;
}

문제에선 불가능한 경우가 있으면 -1 를 출력하라고 했지만, 많은 예제를 풀어봤을 때 맨 위에서부터 ← ↓ 우선순위로 반복하여 값을 복사해주면 항상 답이 존재했다. 혹시나 하는 마음에 크기별로 모든 순열을 구해 확인도 해 보았다. 불가능한 경우의 처리 없이 구현해도 ac 를 받을 수 있다.