$$\newcommand{\Z}{\mathbb{Z}} \newcommand{\R}{\mathbb{R}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\N}{\mathbb{N}}\newcommand{\C}{\mathbb{C}} \newcommand{\oiv}[1]{\left] #1 \right[} \newcommand{\civ}[1]{\left[ #1 \right]} \newcommand{\ad}[1]{\text{ad}(#1)} \newcommand{\acc}[1]{\text{acc}(#1)} \newcommand{\Setcond}[2]{ \left\{\, #1 \mid #2 \, \right\}} \newcommand{\Set}[1]{ \left\{ #1 \right\}} \newcommand{\abs}[1]{ \left\lvert #1 \right\rvert}\newcommand{\norm}[1]{ \left\| #1 \right\|}\newcommand{\prt}{\mathcal{P}}\newcommand{\st}{\text{ such that }}\newcommand{\for}{\text{ for }} \newcommand{\cl}[1]{\text{cl}(#1)}\newcommand{\oiv}[1]{\left] #1 \right[}\newcommand{\interior}[1]{\text{int}(#1)}$$

AtCoder Beginner Contest 136::::Gratus' Blog

AtCoder Beginner Contest 136

알고리즘 문제풀이/AtCoder 2019. 8. 6. 02:32

Performance : 2079 

Rating : 703 -> 1178 (앳코더 레이팅은 수렴하기 전까지는 빠르게 오른다. 대략 10~15번 정도 치러야 Provisional이 빠지고 대충 수렴했다고 보는듯하다)

 

진짜 오랫만에 해보는 ABC인데, 나름 재밌게 했다. ABC의 경우 문제간 난이도 편차가 워낙 커서 사실상 2문제 (D + E) 를 40분~1시간 정도에 풀고, 남은 시간동안 F를 생각해 본다 정도 느낌으로 라운드를 풀 생각이었는데 딱 그렇게 됐다. 


A. Transfer

풀이 생략. 시키는 대로 구하면 된다.

...더보기
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int a, b, c;
    cin >> a >> b >> c;
    cout << (c-min(a-b,c));
}

B. Uneven Numbers

풀이 생략. 시키는 대로 구하면 된다. 숫자가 별로 크지 않으니 그냥 전부 Manually 더하기로 했다. 

...더보기
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    int ct = 0;
    cin >> n;
    for (int i = 1; i<=9; i++)
        if (i<=n)
            ct++;
    for (int i = 100; i<=999; i++)
        if (i<=n)
            ct++;
    for (int i = 10000; i<100000; i++)
        if (i<=n)
            ct++;
    cout << ct;
}

C. Build Stairs

어디선가 본 문제랑 똑같은거 같은데, 대체 어딘지 잘 모르겠다. 아무튼 앞에서부터 그리디하게 내릴 수 있으면 최대한 내리는게 이득이라는걸 별로 어렵지 않게 파악할 수 있고, 이렇게 끝까지 다 내린 다음 처음부터 끝까지 돌면서 되는지 아닌지만 파악하면 OK.

...더보기
#include <bits/stdc++.h>
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;

int stair[101010];
int main()
{
    usecppio
    int n;
    cin >> n;
    for (int i = 1; i<=n; i++)
        cin >> stair[i];
    for (int i = 1; i<=n; i++)
        if (stair[i] > stair[i-1])
            stair[i]--;
    bool ok = true;
    for (int i = 1; i<=n; i++)
        if (stair[i] < stair[i-1])
            ok = false;
    cout << (ok?"Yes":"No");
}

D. Gathering Children

길이가 최대 10만 정도인 컨베이어 벨트에 L 또는 R이 쓰여있다. L은 이 칸에 서 있는 사람이 1시간 후에 왼쪽으로 한칸 이동한다는 뜻이고, R은 오른쪽으로 1칸 이동한다는 뜻이다. 이때, 시작할 때 각 칸에 1명씩 사람이 서 있다면, $10^{100}$ 시간 후에 각 칸에는 사람이 몇 명이나 서 있을지를 구하는 문제이다.

정해와 약간 다르게 풀었다. 

먼저 정해는 대략 이런 느낌인데...

- 만약에 RRR...RL..LLL 형태의 구간이 있다면, 어느정도 시간이 지나고 나면 모든 사람이 가운데 R와 L로만 모이게 된다. 

- 어느정도 시간이 지나고 나면, 그다음부터는 시간의 홀짝에만 영향을 받는다.

- 투포인터 같은걸로 잘 구간을 쪼개서 관리하면서, 이 구간에 있는 사람이 충분히 큰 짝수 시간 후에 어떻게 모일지 찾으면 된다.

 

굉장히 자연스럽게 이런 생각들을 할 수 있지만, 사실 나는 이다음 투포인터를 어떻게 잘 써야 구현뇌절을 안 할지 고민하다가 다음과 같은 풀이를 얻었다.

$\texttt{dp[i][t]}$ 를, "처음에 $i$번째 칸에 서 있었던 사람이 $2^{t}$ 만큼의 시간이 지나면 어디에 가는가?" 라고 정의하자. 이제, 이 정보를 빨리 계산하기 위해서는, $i$ 번째 칸에 서 있었던 사람이 $2^{t-1}$ 시간 후에 어디로 가는지 먼저 파악한다. 이 칸을 $u$ 라고 하자. 이제, $u$번째 칸에 서 있었던 사람은 $2^{t-1}$ 시간 후에 어디로 가는지 알아내면 되는데, 코드로는 $\texttt{dp[i][t] = dp[dp[i][t-1]][t-1]}$ 로 간단히 쓸 수 있다. 짤때는 별 생각 없이 짰는데 결과적으로는 LCA Sparse Table이랑 비슷한 느낌?

 

컨베이어 벨트의 길이가 10만이므로, 10만 번 정도가 지나면 모든 사람의 위치가 둘 중 하나로 고정되게 된다. 그 후에는, 시간의 짝수 / 홀수에 따라서만 위치가 바뀌므로, 10만을 넘는 짝수 시간 후의 배치는 $10^{100}$ 시간 후의 배치와 정확히 같아진다. 

 

나는 그냥 넉넉히 $2^{20} = 1,048,576$ 시간 후의 배치를 구했다.

...더보기
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define ll long long
#define int ll
#define eps 1e-7
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
typedef pair <int, int> pii;

int n;
int initposition[101010];
int position[101010][25];
int ct[101010];
string str;
int32_t main()
{
    cin >> str;
    n = str.length();
    for (int i = 0; i<n; i++)
        initposition[i] = i;
    for (int i = 0; i<n; i++)
    {
        if (str[i] == 'L')
            position[i][0] = initposition[i]-1;
        if (str[i] == 'R')
            position[i][0] = initposition[i]+1;
    }
    for (int t = 1; t<=20; t++)
        for (int i = 0; i<n; i++)
            position[i][t] = position[position[i][t-1]][t-1];
    for (int i = 0; i<n; i++)
        ct[position[i][20]]++;
    for (int i = 0; i<n; i++)
        printf("%lld ",ct[i]);
    printf("\n");
}

E. Max GCD

나름 재밌었던 수학 문제.

$n$개의 수에 대해서, 최대 $k$번 다음과 같은 연산을 할 수 있다.

- 서로 다른 두 개의 수를 골라서, 하나는 1을 더하고, 하나는 1을 뺀다.

연산이 끝난 후, 배열 내의 모든 수의 GCD를 구한 값을 최대화해야 한다.

 

먼저, 모든 연산이 끝난 후 배열 내의 모든 수의 합은 절대 변하지 않음은 자명. 이 합을 $S$ 라고 하자. 

배열 내의 모든 수가 어떤 정수 $g$의 배수라면, $S$도 $g$의 배수일 것이다. 따라서, 가능한 $g$의 후보는 $S$의 약수들로 압축된다. 최대 합은 5천만이고, 5천만 이하의 수의 약수의 개수는 많아야 $\log(5e7)$의 몇제곱 개 정도임이 알려져 있다. (다른 말로, 어떤 수 $x$ 이하의 수 중 가장 약수가 많은 수도 많아야 $\log^a x$ 정도의 약수를 갖는다.) 이 값이 많아야 수천개 안으로 들어올 것이다.

 

이제, 각 후보에 대해서 적당한 시간 ($n^2$ 이면 25만을 최대 몇천번 돌아야 하니까 약간 위험하고, 경험상 그렇게 타이트한 시간 복잡도를 주지는 않을 것이라고 믿고 아마 $n \log n$일 것이라고 추측했다.) 에 가능한지의 여부를 판정하면 된다. 당연하게도, 각 수 자체는 어차피 의미가 없고 후보 $g$로 나눈 나머지만 의미가 있으므로, 먼저 $n$개의 수에 대하여 $g$로 나눈 나머지들을 저장한 배열 $A$를 만들자.

 

이제, $A$에 있는 수들 중 몇개는 -1을 여러 번 해서 0으로 만들 거고, 몇개는 +1을 해서 $g$로 만들어야 한다. 이때 최소 횟수의 연산을 써야 한다. (그래야 그 최소 횟수와 $k$를 비교해서 가능한지 여부를 알 수 있으니) 

 

어차피 +1 한번 당 -1이 따라올 것이므로, 우리는 나머지들의 합도 바꿀 수 없다. 이 "나머지들의 합" 을 $S'$ 라고 하자. 이 값은 원래 바꿀 수 없지만, 나머지 $x$를 $x-g$ 로 (즉, $g = 8$ 이 가능한지 판정하고 싶다면 3을 -5로) 보는 것은 문제가 없다. 이때, 하나를 음수로 바꿀 때마다 합이 $g$만큼 줄어들게 되므로, 적당히 $\frac{S'}{g}$ 개를 골라서 저 연산을 수행해 주면 된다. 이 과정에서 +의 개수 자체는 최소화되어야 하므로, 큰 거부터 저만큼 골라서 음수로 바꾸고, 양수들의 합을 더하면 해결. 말은 복잡하지만 코드는 비교적 어렵지 않다.

...더보기
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define ll long long
#define int ll
#define eps 1e-7
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
typedef pair <int, int> pii;

vector <int> arr;
int n, k;
vector <int> divisor;

bool chk(int x)
{
    int r = 0;
    vector <int> t;
    for (auto it:arr)
    {
        t.push_back(it%x);
        r += (it%x);
    }
    sort(all(t));
    int ss = arr.size();
    int u = r/x;
    int rr = 0;
    for (int i = 0; i<ss-u; i++)
        rr += t[i];
    return rr <= k;
}


int32_t main()
{
    usecppio
    cin >> n >> k;
    int sum = 0;
    for (int i = 0; i<n; i++)
    {
        int x;
        cin >> x;
        arr.push_back(x);
        sum += x;
    }
    for (int i = 1; i<=(int)(sqrt(sum)); i++)
    {
        if (sum%i==0)
        {
            divisor.push_back(i);
            divisor.push_back(sum/i);
        }
    }
    int ans = 1;
    for (auto it:divisor)
        if (chk(it))
            ans = max(ans, it);
    cout << ans;
}

F. Enclosed Points

이 문제는 라운드 중에는 풀지 못했다.

$n$개의 점이 주어질 때, 이 점의 어떤 Subset을 $T$라고 하자. 

이때, 각 $T$에 대해서, $f(T)$ 는 "$T$에 포함된 점들을 모두 포함하는 가장 작은 직사각형을 그릴 때, 이 직사각형이 앞서 제시된 $n$개의 점 중 몇 개를 포함하는지" 이다.

모든 부분집합 $T$에 대해서 $f(T)$의 합을 구하는 문제.

 

먼저, 각 부분집합에 대하여 포함되는 점의 개수를 세는 것은 너무 어려운 일이다. 또한 부분집합 자체가 $2^n$ 개 있기 때문에, 절대 시간 안에 들어오지도 않는다.

따라서, 각 점에 대하여, "직사각형을 그려서 이 점이 들어갈 수밖에 없는 부분집합의 개수" 를 세는 문제로 바꾸자. 이제, 각 점에 대해 $\log n$ 정도에 셀 수 있다면 문제를 풀 수 있다.

 

몇개 케이스를 종이에 그려서 확인해 보니 대략 그 점을 기준으로 왼쪽 아래 / 왼쪽 위 / 오른쪽 위 / 오른쪽 아래에 점이 몇 개 있는지 세면 어렵지 않게 포함배제의 원리를 이용해서 풀 수 있을 것 같았다. 그런데 이 점의 수를 어떻게 빨리 세지? 라운드 중에는 뭔가 적절한 자료구조가 있어서 이걸 셀 수 있을 것 같았는데 그걸 잘 몰랐다.

(세그먼트 트리로 세면 된다고 dlwocks가 알려줬다... 팬이예요!)


오랜만에 앳코더 치는데 꽤 재밌었다. 계속 뭔가를 해볼 수 있는 라운드는 그래도 좀 재밌는거 같은데, 코포에서 가끔 20분 정도 뭔가 해보고 남은 1시간 40분동안 거의 아무것도 못하는 라운드가 있는데 이런건 진짜 너무 힘들다 ㅠㅠ

'알고리즘 문제풀이 > AtCoder' 카테고리의 다른 글

Sumitomo Mitsui Trust Bank Programming Contest 2019  (0) 2019.12.02
AtCoder Beginner Contest 137  (0) 2019.08.11
AtCoder Beginner Contest 136  (2) 2019.08.06
  1. Lemonade255 2019.08.06 21:04 신고 고치기 댓글

    오 앳코더도 치셨네요 ㅎ

    • Gratus 2019.08.06 23:26 신고 고치기

      네 아마 세번째인가? 그럴거예요 ㅋㅋ
      문제 괜찮다고 하길래 앞으로 되면 해보려구요 :)



admin