[ABC] AtCoder Beginner Contest 270

https://atcoder.jp/contests/abc270

TOYOTA MOTOR CORPORATION Programming Contest 2022(AtCoder Beginner Contest 270) - AtCoder

 

A - 1-2-4 Test (10:47)

나는 A 또는 B가 

1, 3, 5, 7 이면 C는 1 맞춤

2, 3, 6, 7 이면 C는 2 맞춤

4보다 크면 C는 4 맞춤

이라고 조건문을 이용해서 풀었다.

 

근데, 1, 2, 4가 모두 2의 거듭 제곱으로 만들어진 수라는 점에 집중했으면, 비트 연산으로 더 쉽게 풀 수 있었다.

결국 그냥 'A | B'가 답이다.

 

B - Hammer (17:28)

그냥 경우를 나눠서 처리하여 주면 된다.

'X, Y의 부호가 같고, X의 절댓값 > Y의 절댓값'인 경우를 제외하면, 답은 'X의 절댓값'이다.

위의 경우에는 다시 세가지 경우로 나뉘는데,

1) Z, X의 부호가 다른 경우, 답은 '2*Z의 절댓값 + X의 절댓값'

2 -1) 'Z. X의 부호가 같고, Z의 절댓값 < Y의 절댓값'인 경우 답은, 'X의 절댓값'

2 -2) 'Z. X의 부호가 같고, Z의 절댓값 > Y의 절댓값'인 경우 답은 '-1' 이다.

 

C - Simple path (28:57)

트리에서의 X에서 Y로 가는 최단 경로를 찾으면 된다. 그냥 X에서 DFS를 시작해서 Y가 나오면 종료하면 된다. 경로를 출력해줘야 하므로, 역추적도 해주면 된다.

 

D - Stones (Upsolved)

대회 중에는 뒤에서터 보는 그리디 풀이를 써서 내서 틀렸다. 결국 못풀고, 에디토리얼을 보고 풀었다.

dp[i] = i개의 돌으로 같은 규칙의 게임을 했을 때, 선공이 가져갈 돌의 개수 (즉, N이 i일때의 답)

라 하면,  dp[i] = max(dp[i], a[j] + (i - a[j]) - dp[i - a[j]]) 의 점화식을 세울 수 있다. 

선공이 a[j]를 가져가고, 후공이 남은 i - a[j] 중에서 dp[i - a[j]]를 가져간다고 생각하면 된다.

ll n, k;
ll a[10005];
ll dp[10005];

void solve()
{
    cin >> n >> k;
    for (ll i = 1; i <= k; i++) cin >> a[i];
    
    dp[0] = 0;
    for (ll i = 1; i <= n; i++)
        for (ll j = 1; j <= k; j++)
            if (i - a[j] >= 0)
                dp[i] = max(dp[i], a[j] + (i - a[j]) - dp[i - a[j]]);
 
    cout << dp[n];
}

https://atcoder.jp/contests/abc270/editorial/4885

Editorial - TOYOTA MOTOR CORPORATION Programming Contest 2022(AtCoder Beginner Contest 270)

 

E - Apple Baskets on Circle (Upsolved)

얘도 에디토리얼을 보고 해결했다.

1번의 사이클을 [1, N]을 돌아 가능하면 사과를 1개씩 먹는 것이라 하자. 이때, 어떤 m번의 사이클을 기준으로 m번 초과의 사이클을 돌면 사과를 K개 이상 먹을 수 있고, m번 이하의 사이클을 돌면  사과를 K개 이상 먹을 수 없다. 이런 m을 이분 탐색을 통해 찾아주면 된다. 

1번의 사이클을 돌았을 때, 먹은 사과의 개수는 O(N)으로, m을 찾는데 O(logK)가 걸리므로 O(NlogK)에 해결할 수 있다.

ll n, k;
ll a[100005];

bool apple(ll c)
{
    ll ret = 0;
    for (ll i = 0; i < n; i++) ret += min(a[i], c);
    return ret <= k;
}

void solve()
{
    cin >> n >> k;
    for (ll i = 0; i < n; i++) cin >> a[i];
    ll l = 0, r = 1e12 + 2;
    while (l < r)
    {
        ll mid = (l + r) / 2;
        if (apple(mid)) l = mid + 1;
        else r = mid;
    }
    l--;

    for (ll i = 0; i < n; i++)
    {
        ll mn = min(a[i], l);
        a[i] -= mn; k -= mn;
    }

    for (ll i = 0; k > 0; i++)
        if (a[i]) { a[i]--; k--; }

    for (ll i = 0; i < n; i++) cout << a[i] << ' ';
}

https://atcoder.jp/contests/abc270/editorial/4883

Editorial - TOYOTA MOTOR CORPORATION Programming Contest 2022(AtCoder Beginner Contest 270)

 

E번 구현 할 때에, 이분 탐색 경계 설정에서 애를 많이 먹었는데, 아래 글이 잘 정리해 둔 것 같다.

https://blossoming-man.tistory.com/entry/%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-Binary-Search-%EA%B2%BD%EA%B3%84-%EC%84%A4%EC%A0%95%EC%9D%84-%EC%96%B4%EB%96%BB%EA%B2%8C-%ED%95%B4%EC%95%BC-%ED%95%98%EB%8A%94%EA%B0%80

이진 탐색 Binary Search 경계 설정을 어떻게 해야 하는가