[알고리즘 연습] 2021년도 10월 넷째주 학습 (D번 문제 풀이)

AtCoder Beginner Contest 223 (D번 문제): topological sort 응용

AtCoder Beginner Contest 223 (F번 문제): segment tree 응용

 

AtCoder 를 풀다가 공부해두고 싶은 문제가 생겨서 정리해두었다.

 

1. AtCoder Beginner Contest 223 (D번 문제)

https://atcoder.jp/contests/abc223/tasks/abc223_d

풀이

Indegree 를 활용하는 일반적인 topological sort 코드에 heap push, heap pop 을 추가하기만 하면 된다!

 

코드

출처: https://atcoder.jp/contests/abc223/submissions/26656807

from heapq import heappush, heappop
 
N, M = map(int, input().split())
 
graph = defaultdict(list)
indegree = defaultdict(int)
for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    indegree[b] += 1
 
result = []
q = []
for key in range(1, N+1):
    if indegree[key] == 0:
        heappush(q, key)
 
while q:
    cur = heappop(q)
    result.append(cur)
 
    for item in graph[cur]:
        indegree[item] -= 1
        if indegree[item] == 0:
            heappush(q, item)
 
if len(result) == N:
    print(*result, sep=" ")
else:
    print(-1)

 

2. AtCoder Beginner Contest 223 (F번 문제)

풀이

본 문제는 segment tree 를 이용하는 문제인데, 해설을 정확하게 이해하지 못하였다. 백준의 문자열과 쿼리 시리즈를 공부하고 나서 풀어보면 좋을 듯하다. (거의 동일한 형태의 문제들이다)

 

코드

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
pair<int, int> op(pair<int, int> a,pair<int, int> b){
    return make_pair(min(a.first, a.second + b.first), a.second + b.second);
}
pair<int, int> e(){
    return make_pair(0, 0);
}
int main(){
    int n, q; cin >> n >> q;
    string s; cin >> s;
    vector<pair<int, int>> v(n);
    for(int i = 0; i < n; i++){
        if(s[i] == '(') v[i] = make_pair(0, 1);
        else v[i] = make_pair(-1, -1);
    }
    segtree<pair<int, int>, op, e> seg(v);
    for(int i = 0; i < q; i++){
        int t, l, r; cin >> t >> l >> r; l--; r--;
        if(t == 1){
            swap(v[l], v[r]);
            seg.set(l, v[l]);
            seg.set(r, v[r]);
        }
        else{
            if(seg.prod(l, r + 1) == make_pair(0, 0)) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
    }
}

알고리즘 대회_2021_10_Week4.pptx

0.42MB