hibye1217의 ALOHA & SHARC 탐방기 hibye1217의 ALOHA & SHARC 탐방기

1. [18116] 로봇 조립 (Gold IV) 더보기 의도한 태그: Union-Find (Easy) 'I a b'의 쿼리는 그냥 union으로 처리하면 됩니다. 'Q c'도 find가 쓰이는 것 같은데, 부품의 개수까지 알아내야 합니다. 부품의 개수 = 집합의 크기 이고, 집합의 크기는 모두 1인 상태로 시작해서 union을 할 때마다 합쳐지는 두 집합의 크기의 합을 새로 저장해주면 됩니다. const int N = 1000000; int par[1000020], siz[1000020]; int fnd(int a){ if (par[a] == a){ return a; } return par[a] = fnd(par[a]); } void uni(int a, int b){ int pa = fnd(a), pb ..

1. [22971] 증가하는 부분 수열의 개수 (Silver II) 더보기 의도한 태그: Longest Increasing Subsequence \( D_{i} = A_{i} \)로 끝나는 LIS의 개수를 정의하면, 점화식은 아래와 같이 적어볼 수 있습니다. \( j > n; for (int i = 1; i > arr[i]; } for (int i = 1; i = arr[i]){ continue; } dp[i] += dp[j]; dp[i] %= mod; } } ..

1. [13549] 숨바꼭질 3 (Gold V) 더보기 의도한 태그: Dijkstra (Easy) 정점은 그냥 좌표고, 간선은 문제에서 충분히 자세히 알려주고 있습니다. 탐색 범위를 넉넉하게 잡는 걸 추천합니다. 저는 자세한 생각하기 귀찮아서 목적지에 2를 곱한 \( 200\,000 \)으로 잡았습니다. const ll INF = 0x3f3f3f3f3f3f3f3f; ll dis[200020]; ll djk(int st, int ed){ memset(dis, 0x3f, sizeof(dis)); dis[st] = 0; priority_stack pq; pq.push({0, st}); while (!pq.empty()){ int now = pq.top().sc; ll dst = pq.top().fr; pq.p..

1. [19699] 소-난다! (Silver II) 더보기 의도한 태그: Backtracking (Easy) 소들을 선택하는 경우의 수는 \( {}_{N}C_{M} \)가지가 됩니다. 제한이 \( 1 \le M \le N \le 9 \)니, 조합의 식에서 분모를 아예 무시해도 \( 9! = 362 880 \)이라는, 충분히 작은 값이 나옵니다. 그러니, 이 경우들을 다 돌려보면 됩니다. const int N = 9000; bool pr[9020]; int n, m; int arr[10]; vector ans; void btk(int idx, int cnt, int sum){ if (idx > n){ if (cnt == m){ if (pr[sum]){ ans.push_back(sum); } } return..

1. [2217] 로프 (Silver IV) 더보기 의도한 태그: Greedy (Easy) 만약 로프를 \( c \)개 쓸 거라면, 자명하게 가장 강한 \( c \)개의 로프를 써야 합니다. 그리고, 그 때 들 수 있는 중량은 \( c \times \min(A_{1}, A_{2}, \ldots, A_{c}) \)가 됩니다. 만약 로프의 강도가 (큰 게 먼저 오도록) 정렬되어있다면, 답은 \( c \times A_{c} \)가 됩니다. 그러니, \( c \)를 \( 1 \)부터 \( N \)까지 다 돌려주면서 답을 찾으면 됩니다. 2. [2630] 색종이 만들기 (Silver II) 더보기 의도한 태그: Divide and Conquer (Easy) 현재 크기의 색종이를 보면서, 한 가지 색깔로만 칠해졌다..