AtCoder Beginner Contest 119 후기

AtCoder Beginner Contest 119

A - Still TBD
\(\text{년도}\times 800 + \text{월}\times 40 + \text{일}\)로 계산하면 그나마 구현이 편하다.

#include <bits/stdc++.h>
 
int main() {
    int a, b, c;
    scanf("%d/%d/%d", &a, &b, &c);
 
    a = a * 40 * 20 + b * 40 + c;
 
    printf("%s", a <= 2019 * 40 * 20 + 4 * 40 + 30 ? "Heisei" : "TBD");
 
    return 0;
}

B - Digital Gifts
실수오차를 엄청 신경써야되는줄알고 계속 끙끙맸는데, 자꾸 안 돼서 대충 해서 냈더니 풀렸다.
여기에 시간을 너무 많이 썼다.

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int n;
    cin >> n;
    
    long long tot1 = 0;
    double tot2 = 0;
    while (n--) {
        string x, u;
        cin >> x >> u;
 
        if (u == "JPY")
            tot1 += stoll(x);
        else
            tot2 += stod(x);
    }
 
    printf("%.10lf", tot1 + tot2 * 380000);
 
    return 0;
}

C - Synthetic Kadomatsu
구현을 편하게 하려면 일단 \(A,B,C\)가 될 대나무들을 정한 다음에, 남은 대나무들을 합치지 않거나, \(A\)에 합치거나, \(B\)에 합치거나, \(C\)에 합치는 4가지 경우로 나눠서 백트래킹을 하는 것이다.
이게 구현이 아주 짜증나서 D번으로 넘어갔었는데, D번이 더 짜증났다.

#include <bits/stdc++.h>
 
using namespace std;
 
int n, a, b, c, l[8];
 
int f(int i, int j, int k, int idx, int mp) {
    if (idx == n) {
        return mp + abs(l[i] - a) + abs(l[j] - b) + abs(l[k] - c);
    }
    if (idx == i || idx == j || idx == k)
        return f(i, j, k, idx + 1, mp);
 
    int mn = 1e9;
    mn = min(mn, f(i, j, k, idx + 1, mp));
    l[i] += l[idx];
    mn = min(mn, f(i, j, k, idx + 1, mp + 10));
    l[i] -= l[idx];
    l[j] += l[idx];
    mn = min(mn, f(i, j, k, idx + 1, mp + 10));
    l[j] -= l[idx];
    l[k] += l[idx];
    mn = min(mn, f(i, j, k, idx + 1, mp + 10));
    l[k] -= l[idx];
 
    return mn;
}
 
int main() {
    scanf("%d %d %d %d", &n, &a, &b, &c);
 
    for (int i = 0;i < n;++i)
        scanf("%d", &l[i]);
 
    int mn = 1e9;
    for (int i = 0;i < n;++i)
        for (int j = 0;j < n;++j)
            for (int k = 0;k < n;++k) {
                if (i == j || j == k || k == i)
                    continue;
 
                mn = min(mn, f(i, j, k, 0, 0));
            }
 
    printf("%d", mn);
 
    return 0;
}

D - Lazy Faith
이분탐색으로 \(x\)에서 가까운 신전과 사원을 찾으면 된다.
왼쪽신전->왼쪽사원의 경우, 왼쪽신전->오른쪽사원의 경우, ... 로 8가지 정도를 아주 잘 처리해주면 되는데... 아주 잘 처리하기가 매우 까다로웠다.

#include <bits/stdc++.h>
 
using namespace std;
 
vector<long long> shr, tem;
 
int main() {
    int a, b, q;
    scanf("%d %d %d", &a, &b, &q);
    shr.assign(a, 0);
    tem.assign(b, 0);
 
    for (int i = 0;i < a;++i)
        scanf("%lld", &shr[i]);
 
    for (int i = 0;i < b;++i)
        scanf("%lld", &tem[i]);
 
    while (q--) {
        long long x;
        scanf("%lld", &x);
 
        long long mn = 1e18;
 
        auto rshr = lower_bound(shr.begin(), shr.end(), x);
        auto rtem = lower_bound(tem.begin(), tem.end(), x);
        auto lshr = rshr;
        auto ltem = rtem;
        if (rshr != shr.begin())
            lshr--;
        if (rtem != tem.begin())
            ltem--;
        if (rshr != shr.end() && *rshr == x)
            lshr = rshr;
        if (rtem != tem.end() && *rtem == x)
            ltem = ltem;
 
        if (rshr == shr.end())
            rshr--;
        if (rtem == tem.end())
            rtem--;
 
        mn = min(mn, abs(x - *lshr) + abs(*lshr - *ltem));
        mn = min(mn, abs(x - *lshr) + abs(*lshr - *rtem));
        mn = min(mn, abs(x - *rshr) + abs(*rshr - *ltem));
        mn = min(mn, abs(x - *rshr) + abs(*rshr - *rtem));
        mn = min(mn, abs(x - *ltem) + abs(*lshr - *ltem));
        mn = min(mn, abs(x - *rtem) + abs(*lshr - *rtem));
        mn = min(mn, abs(x - *ltem) + abs(*rshr - *ltem));
        mn = min(mn, abs(x - *rtem) + abs(*rshr - *rtem));
 
        printf("%lld\n", mn);
    }
 
    return 0;
}

앳코더치고 문제가 너무 불편했다. 문제 주제 상으로도 너무 일본 문화적인 요소를 많이 넣었고, 구현이 까다로운 문제가 꽤 많았다.

96등으로 1055점이 됐다. 코포에 비해 레이팅이 오르는 속도가 느리기는 한 것 같다.