USACO 2024 December Contest

1. Roundabout Rounding

이 문제의 체인반올림은 1의자리에서부터 반올림을 해가면서 가장 높은자리까지 반올림을 하는 새로운 계산법이다. 이때, 체인반올림과 그냥 반올림을 한 수가 다른 1 ~ 주어진 N까지의 모든 수의 개수를 구하는 문제이다.

간단히 45…55이 수부터 가장 높은자리에서의 반올림과 체인반올림이 달라지고, 50…00부터 같아짐으로 이 사이의 수를 모두구하면된다.

만약 N이 50…00보다 크다면 50…00으로 N을 갱신후, 45…54를 빼주면 된다.

code

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;
using ll = long long;

ll P[11];

int main()
{
    int t;
    scanf("%d", &t);
    P[2] = 5;
    for(int i=3;i<=10;i++) {
        P[i] = P[i - 1];
        ll res = 0;
        for(int j = 0;j<i - 1;j++) {
            res += 4 * pow(10, j);
        }
        res++;
        P[i] += pow(10, i - 1) - res;
    }
    while(t--) {
        int N;
        vector <int> vec;
        scanf("%d", &N);
        ll n = (ll)N;
        while(N >= 10) {
            vec.push_back(N % 10);
            N /= 10;
        }
        vec.push_back(N);
        reverse(vec.begin(), vec.end());
        ll ans = P[vec.size() - 1];
        ll res = 0;
        for(int i = 0;i<vec.size();i++) {
            res += (ll)(4 * pow(10, i));
        }
        if(vec[0] >= 5) {
            n = (ll)(5 * pow(10, vec.size() - 1));
            n--;
        }
        res++;
        if(res <= n) ans += (ll)(n - res + 1);
        printf("%lld\\n", ans);
    }
    return 0;
}

2. Farmer John's Cheese Block

이 문제는 3차원 공간에 NxNxN크기의 꽉 차있는 치즈블럭을 각 쿼리마다 하나씩 부셨을 때, 남은 공간에 1xN크기의 블럭이 얼마나 들어갈 수 있는 지를 각 쿼리마다 출력하는 문제이다.

N범위는 1000으로 작은편이지만 하나의 쿼리마다 3중for문을 돌면서 검사하기에는 쿼리의 개수가 최대 2x$10^5$임으로 오래걸린다.

나는 이 문제를 check배열을 이용해서 풀었다. 좌표쌍을 xy, xz, yz로 묶어 초반에미리 N으로 초기화를 해놓고 쿼리에서 주어진 좌표쌍 x, y, z에서 checkxy[x][y]—, checkxz[x][z]—, checkyz[y][z]—를 해준뒤, 0이 되었다면 ans를 1씩늘려주는 방식으로 구현하였다.

code

#include <stdio.h>
#include <algorithm>

using namespace std;

int chxy[1010][1010];
int chxz[1010][1010];
int chyz[1010][1010];
int n, q;

int main()
{
    int i, j;
    scanf("%d %d", &n, &q);
    for(i=0;i<n;i++) {
        for(j=0;j<n;j++) {
            chxy[i][j] = n;
            chxz[i][j] = n;
            chyz[i][j] = n;
        }
    }
    int ans = 0;
    while(q--) {
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        chxy[x][y]--;
        chxz[x][z]--;
        chyz[y][z]--;
        if(chxy[x][y] == 0) ans++;
        if(chxz[x][z] == 0) ans++;
        if(chyz[y][z] == 0) ans++;
        printf("%d\\n", ans);
    }
    return 0;
}

3. It's Mooin' Time

구현이 어려웠던 문제이다. 문제에서 주어진 문자열에서 abb형태(즉, 맨 앞의 알파벳이 다르고 그 뒤는 같은 문자 2개가 연속해서 나오는 경우)의 개수가 F이상인 abb형태의 문자열을 모두 구하는 문제이다. 다만 문자열에서 1개의 문자까지는 변경이 가능하다.

이 문제는 map자료구조와 간단한 아이디어를 통해 구현이 가능하다.

a~z는 총26개의 문자로 이루어져있고, 주어진 문자열에서 문자를 한번 바뀔때, 영향을 미치는 범위는 앞뒤 2문자씩 총 5문자로 제한되어있음으로, N을 돌면서, 각 위치에서 문자를 a~z로 바꾸고, 문자가 바뀌어 영향을 미친 범위만 업데이트 해주는 식으로 구현하면 된다.

code

#include <iostream>
#include <string>
#include <map>
#include <set>
#include <vector>

using namespace std;

int n, f;
string s;
map <string, int> mp;
set <string> ans, st;

void ReRange(int l, int r, int val)
{
    for(int i=l;i<=r - 2;i++) {
        string res;
        res += s[i];
        res += s[i + 1];
        res += s[i + 2];
        if(res[0] != res[1] && res[1] == res[2]) {
            mp[res] += val;
        }
    }
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);
    int i, j;
    cin >> n >> f;
    cin >> s;
    ReRange(0, n - 1, 1);
    for(i=0;i<n;i++) {
        char now = s[i];
        map<string, int> imsi = mp;
        for(char ch = 'a';ch <= 'z';ch++) {
            int l = i - 2, r = i + 2;
            if(l < 0) l = 0;
            if(r >= n) r = n - 1;
            ReRange(l, r, -1);
            s[i] = ch;
            ReRange(l, r, 1);
            for(auto itr = mp.begin();itr != mp.end();itr++) {
                if(itr->second >= f) {
                    ans.insert(itr->first);
                }
            }
        }
        mp = imsi;
        s[i] = now;
    }
    cout << ans.size() << '\\n';
    for(auto itr = ans.begin();itr!=ans.end();itr++) {
        cout << *itr << '\\n';
    }
    return 0;
}