AtCoder ABC 359

작성일 | In ,

서론

지난주 토요일 ABC 358을 망치고 첫 atcoder였습니다. 이번주 월요일 연습때 폼이 나쁘지 않아 걱정반 기대반으로 시작했습니다.

Contest

A - Count Takahash[+, 1:01]

사용 알고리즘

  • 구현(Implementation)
  • 문자열(String)

문제 상황

$N$개의 문자열이 주어지고 이 중 Takahashi의 개수를 세는 문제입니다. 대회 후 이 글을 작성 중에 알았는데, 모든 문자열은 Takahashi 혹은 Aoki입니다.

풀이

항상 그렇듯 빠르게 해석하고 구현하는 것이 관건입니다. count함수를 사용하여 Takahashi의 개수를 세었습니다.

1
2
3
4
5
6
7
8
void solve(){
    int i,j,k;
    ll n;
    cin>>n;
    vector<string>str(n);
    for(i=0;i<n;i++)cin>>str[i];
    cout<<count(str.begin(), str.end(),"Takahashi");
}

B - Couples[+, 3:55]

사용 알고리즘

  • 구현(Implementation)

문제 상황

$1$부터 $N$까지 각각 두 개 씩 총 $2N$개의 정수가 주어지고, 이 중 같은 정수 사이에 다른 수가 정확히 한 개 있는 정수의 개수를 구하는 문제입니다.

풀이

들어오는 수의 위치 두개를 저장해 $2$가 차이나는 지 확인하면 됩니다. 처음에 $N$개의 정수만 입력받아 로컬에서 RTE가 나와 이를 찾아 수정하느라 3분정도 소요되었습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void solve(){
    int i,j,k;
    ll n;
    cin>>n;
    vector<vector<ll>>arr(n+1);
    for(i=0;i<n*2;i++){
        cin>>j;
        arr[j].pb(i);
    }
    ll cnt=0;
    for(i=1;i<=n;i++){
        if(arr[i][0]+2==arr[i][1])cnt++;
    }
    cout<<cnt;
}

C - Tile Distance 2[+1, 12:43]

사용 알고리즘

  • 구현(Implementation)
  • 많은 조건 분기(Case-Work)

문제 상황

아래와 같은 그림에서 출발점과 도착점이 블럭 내부에 주어질 때 최소로 블록을 바꾸어 도착점까지 이동하는 문제입니다.

풀이

범위가 $2\times 10^{16}$이라 직접하는 것은 안됩니다.

가로와 세로 중 어디가 더 긴 지 확인하고, 일단 대각선으로 이동하여, 가로가 크다면 마지막에 두 칸 씩, 세로가 크다면 한 칸 씩 이동하는 것이 최적이라는 것을 알 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void solve(){
    int i,j,k;
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    ll dx=abs(c-a),dy=abs(d-b);
    if(dy>=dx){
        cout<<dy;
    }
    else{
        ll ans=dy;
        dx-=dy;
        if(a<c){
            if((a+b)%2==1){
                ans+=(dx+1)/2;
            }
            else{
                ans+=dx/2;
            }
        }
        else{
            if((a+b)%2==0){
                ans+=(dx+1)/2;
            }
            else{
                ans+=dx/2;
            }
        }
        cout<<ans;
    }
}

+ 대회 후 changhw(now_cow)의 코드를 봤는데 깔끔하게 잘 짜서 첨부합니다

1
2
3
4
5
6
7
8
9
int main() {
    fastio;
    ll sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;
    if((sx + sy) % 2 == 0) sx++;
    if((tx + ty) % 2 == 0) tx++;
    cout << abs(sy - ty) + max(0LL, (abs(sx - tx) - abs(sy - ty) + 1)/2);
    return 0;
}

D - Avoid K Palindrome[+, 22:08]

사용 알고리즘

  • DP(Dynamic Programming)
  • 비트마스크(Bitmask)

문제 상황

길이 $N$의 A, B, ?로만 이루어진 문자열과 $K$가 주어지고 ?에 A 혹은 B를 넣을 때, 길이 $K$의 substring이 palindrome이 되지 않도록 하는 문자열의 개수를 구하는 문제입니다.

풀이

$K$의 범위가 $10$이하이고, $N$이 $1000$이하이므로, $N\times 2^K$ DP로 풀 수 있습니다.

i번째 문자까지 고려하고, 마지막 $K$개의 문자를 A를 0, B를 1이라 생각할 때의 비트마스크를 j라고 할 때 조건을 만족하는 경우의 수를 DP[i][j]로 놓고 구할 수 있습니다.

첫 $K-1$개의 문자에 대해서는 조건을 항상 만족하므로 별도의 처리 없이 진행하고, 이후에는 j의 비트마스크가 팰린드롬이 아닐 때만 DP[i][j]를 갱신합니다. 만약 팰린드롬이라면 0을 넣어줍니다. (i,j)에서 갈 수 있는 상태가 (i+1,x)라고 하면 x는 j의 첫 비트를 지우고, 비트를 하나씩 시프트 시키고, 마지막 비트만 0 혹은 1로 설정해주면 됩니다. 즉, $N\times 2^K$가지의 상태에 대해 각각 $2$개 씩 전파해주면 됩니다.

미리 팰린드롬을 모두 구해둔다면, $O(N\times 2^K)$로 풀 수 있습니다. 매번 구한다면 $O(NK\times 2^K)$도 시간 내에 들어갈 것 같습니다. 아래 코드에서는 $K$대신 m을 사용하였습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
void solve(){
    int i,j,k;
    ll n,m;
    cin>>n>>m;
    string str;
    cin>>str;
    vector<vector<ll>> dp(n+1,vector<ll>(1<<m,0));
    vector<bool> isok(1<<m,true);
    for(i=0;i<(1<<m);i++){
        vector<int> cnt(m,0);
        for(j=0;j<m;j++){
            if(i&(1<<j)){
                cnt[j]++;
            }
        }
        vector<int> cnt2=cnt;
        reverse(all(cnt2));
        if(cnt==cnt2)isok[i]=false;
    }
    dp[0][0]=1;
    for(i=1;i<=m-1;i++){
        for(j=0;j<(1<<m);j++){
            if(str[i-1]!='B'){
                ll nex=(j<<1)&((1<<m)-1);
                dp[i][nex]+=dp[i-1][j];
                dp[i][nex]%=mod;
            }
            if(str[i-1]!='A'){
                ll nex=(j<<1)&((1<<m)-1)|1;
                dp[i][nex]+=dp[i-1][j];
                dp[i][nex]%=mod;
            }
        }
    }
    for(i=m;i<=n;i++){
        for(j=0;j<(1<<m);j++){
            if(str[i-1]!='B'){
                ll nex=(j<<1)&((1<<m)-1);
                if(isok[nex]) {
                    dp[i][nex] += dp[i - 1][j];
                    dp[i][nex] %= mod;
                }
            }
            if(str[i-1]!='A'){
                ll nex=(j<<1)&((1<<m)-1)|1;
                if(isok[nex]) {
                    dp[i][nex] += dp[i - 1][j];
                    dp[i][nex] %= mod;
                }
            }
        }
    }
    ll ans=0;
    for(i=0;i<(1<<m);i++){
        ans+=dp[n][i];
        ans%=mod;
    }
    cout<<ans<<'\n';
}

E - Water Tank[+, 33:17]

사용 알고리즘

  • 스택(Stack)

문제 상황

$N+1$개의 수조가 순서대로 붙어 있고, $i$번과 $i+1$번 사이의 벽의 높이 $H_i$가 주어집니다. 각 수조의 밑면적은 같고, $1$초에 한 번씩 $0$번 수조에 높이 $1$의 물을 채웁니다. 물은 벽을 넘어가면 다음 수조로 흘러 들어갑니다. $1$번 부터 $N$번까지의 각 수조에 물이 언제 처음 넘어 들어가는 지 구하는 문제입니다.

풀이

언제 물이 처음으로 넘어가는 지를 예제를 보며 관찰하다 보면 다음 사실을 알 수 있습니다.

  • 뒤쪽 벽이 앞쪽 벽보다 더 높다면, 앞쪽 수조도 앞쪽 벽의 높이와 상관없이 뒤쪽 벽의 높이 만큼 물이 차야 넘어갈 수 있다.
  • 앞쪽 벽이 뒤쪽 벽보다 더 높다면, 앞쪽 수조를 가득 채운 후 뒤쪽 벽의 높이만큼 물이 차야 넘어갈 수 있다. 즉, 앞쪽 벽이 더 높고, 뒤쪽 수조에 물이 들어가게 되면, 이후 넘어오는 물은 뒤쪽 수조로 넘어가게 된다.

이를 통해 물이 걸리는 벽들의 높이는 감소함을 알 수 있습니다. LIS 구할 때와 마찬가지로 스택에 높이가 감소하도록 유지시키며, 넣어주면 됩니다. 각각의 벽에 대해 순차적으로 다음을 해줍니다.

  • 만약 스택이 비었거나, top의 높이가 현재 벽보다 높다면, top의 인덱스(비어있다면 0)과 현재 벽의 인덱스의 차이 만큼의 길이를 현재 벽의 높이만큼의 물로 채워야 하므로, 직전부터 현재 벽까지 채우는데 걸리는 시간을 계산해줍니다. 이후 현재 벽의 높이와 인덱스, 채우는데 걸리는 시간을 넣어줍니다.
  • 그렇지 않다면 top을 pop하고 반복합니다.

이를 반복하면 $i$번 벽까지 채우는데 걸리는 시간이 마지막에 저장되어 있을 것이므로, 여기에 $+1$해 출력하면 됩니다.

스택에 원소가 들어갈 때, 나갈 때 보여지고, top만 참조하므로 $O(N)$에 풀 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void solve(){
    int i,j,k;
    ll n,m;
    cin>>n;
    vector<ll> arr(n);
    for(auto &x:arr)cin>>x;
    stack<tlll> st;
    for(i=0;i<n;i++){
        while(st.size()){
            auto [h,idx,sum]=st.top();
            if(h>arr[i]){
                st.push({arr[i],i,sum+arr[i]*(i-idx)});
                break;
            }
            else{
                st.pop();
            }
        }
        if(st.empty()){
            st.push({arr[i],i,arr[i]*(i+1)});
        }
        cout<<get<2>(st.top())+1<<" ";
    }
}

F - Tree Degree Optimization[+, 40:36]

사용 알고리즘

  • 정렬(Sort)
  • 그리디(Greedy)
  • 우선순위 큐(Priority Queue)

문제 상황

$N$개의 양의 정수 $A_1,A_2,\cdots,A_N$이 주어지고, $N$개의 정점을 가진 트리를 만들어야 합니다. $i$번 정점의 차수가 $d_i$라고 할 때, $\sum_{i=1}^{N}d_i^2A_i$의 값을 최소로 하도록 트리를 구성하는 문제입니다.

풀이

만약 차수가 모두 정해져 있다고 합시다. 이 때 $\sum_{i=1}^{N}d_i^2A_i$의 값을 최소로 하려면, 재배열 부등식에 의해 $d_i$와 $A_i$는 서로 정렬해 역순으로 매칭시켜야 합니다. 즉, 이는 결국 $A_i$가 작은 것이 최대한 많은 정점에 연결되어 있어야 하며, $A_i$가 큰 것끼리 연결될 필요가 없으므로, $A_i$를 오름차순으로 정렬하여 하나의 트리에 연결해나가는 것이 최적임을 의미합니다.

그렇다면 주어진 $A_i$를 오름차순으로 정렬하고, 해당 순서대로 $1$, $2$, $\cdots$, $N$번 정점으로 재배열 합니다. 이 상황에서 $i$번 정점을 삽입한다고 가정하면, $i$번 정점이 $j$번 정점과 연결된다고 가정할 때, $d_j$가 $1$ 증가하고, $d_i$가 1이 됩니다. 즉, 값은 $((d_j+1)^2-d_j^2)\cdot A_j+A_i=(2d_j+1)\cdot A_j+A_i$만큼 증가합니다.

즉, $(2d_j+1)\cdot A_j$가 가장 작은 정점에 그리디하게 연결해 주는 것이 최적임을 추측할 수 있습니다. 만약 다른 정점에 연결된다면, 더 큰 값을 가져가게 될 것입니다. 이 경우가 이후에 더 이득을 볼 수 있는 지 검사하면 $2d_j+1$은 증가함수이므로 점점 추가되는 값이 커지므로 그럴 수 없습니다.

만약 $(2d_j+1)\cdot A_j=(2d_k+1)\cdot A_k$인 경우가 있고, 이 경우가 최소라고 하더라도 어떤 걸 선택하든 다음 선택에서 다른 것을 선택할 것이므로, 신경쓰지 않아도 됩니다.

이를 우선순위 큐를 사용하여 구현하면 됩니다. 우선순위 큐에는 추가되는 값과 현재 차수를 저장하고, 가장 작은 값을 가진 정점을 빼서 연결해주면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void solve(){
    int i,j,k;
    ll n,m;
    cin>>n;
    vector<ll> arr(n);
    for(auto &x:arr)cin>>x;
    sort(all(arr));
    priority_queue<pll,vector<pll>,greater<pll>> pq;
    ll ans=0;
    pq.push({arr[0],0});
    for(i=1;i<n;i++){
        auto [val,cnt]=pq.top();
        pq.pop();
        ll ai=val/((cnt+1)*(cnt+1)-cnt*cnt);
        ans+=val+arr[i];
        ll nex=ai*((cnt+2)*(cnt+2)-(cnt+1)*(cnt+1));
        pq.push({nex,cnt+1});
        pq.push({arr[i]*3,1});
    }
    cout<<ans<<'\n';
}

G - Sum of Tree Distance[-]

TODO

총평

개인적 평가

F까지는 빠르게 밀었지만, G 풀이를 20분 정도만에 생각하고 구현했지만, 예제가 나오지 않아 디버깅 하는 과정에서 시간이 종료되었습니다. 이후 찾아보니까 ETT+트리압축 혹은 Small to Large를 사용하면 풀 수 있는 문제였습니다. 저는 전자로 생각하고 풀었는데 트리압축이라는 개념을 처음 보았는데, 이런 문제를 풀어봤다면 더욱 빠르게 풀 수 있었을 것 같다는 아쉬움이 듭니다. 최근에 회사를 나와서 백수로 살고 있어서 시간이 많은데, 이 많은 시간을 효율적으로 투자해서 정진해야 할 것 같습니다.

다음주 토요일에는 현대모비스 알고리즘 대회 1차, 종료후 팀연습이 예정되어 있어 ARC를 풀지 못할 것 같지만, 일요일 ABC를 참여해보도록 하겠습니다.

해당 라운드 평가

C번을 제외하고는 마음에 드는 셋이였습니다. D번이나 여러 문제에서 예외처리를 해주지 않도록 제한 조건을 주어서 좋았습니다. 평소 ABC보다 약간 쉬운 느낌이 들었습니다.