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

1. [18857] 집 떠나와 열차 타고 (Diamond V) 더보기 BCC를 기준으로 생각해봅시다. 그래프가 선인장이기 때문에, BCC는 '간선 1개'이거나 '사이클 1바퀴'밖에 없습니다. 그러므로, \( 1 \Rightarrow N \)의 경로와 닿는 모든 BCC를 들고 온 뒤, 두 경우에 맞게 처리해주면 됩니다. 간선 1개: 그 간선을 자르면 됩니다. 사이클 1바퀴: 경로에 속한 가장 짧은 간선과 경로에 속하지 않은 가장 짧은 간선을 자르면 됩니다. 각 BCC별로 저 값을 구해둔 뒤, 최솟값을 찾아주면 됩니다. int n, m; vector adj[402020]; int ord=0, ind[402020]; stack stk; int cnt = 0, num[429020]; int dfs(int now..

1. [1535] 안녕 (Silver II) 더보기 \( DP_{i, j} := \) \( i \)번째 사람까지 인사 여부를 결정했을 때, 체력을 최대 \( j \)만큼 써서 얻을 수 있는 최대 행복 이라고 정의합시다. 그럼 \( DP_{i, j} \)는 2가지 경우에 의해 결정됩니다. \( i \)번 사람에게 인사를 한다: \( DP_{i-1, j-L_{i}} + J__{i} \)만큼의 기쁨을 느낍니다. \( i \)번 사람에게 인사를 하지 않는다: \( DP_{i-1, j} \)만큼의 기쁨을 느낍니다. 문제의 답은 \( DP_{N, 99} \)가 됩니다. * 100의 체력을 쓰면 죽기 때문에 최대 체력은 99여야 합니다. 시간복잡도는 \( O(100N) \)입니다. pi2 arr[22]; int dp..

A. [10870] 피보나치 수 5 (Bronze II) 더보기 피보나치 수는 아래와 같이 구할 수 있습니다. \[ F_{x} = \begin{cases} 0 & \text{if } x = 0 \\ 1 & \text{if }x = 1 \\ F_{x-1} + F_{x-2} & \text{otherwise} \end{cases} \] 이를 그대로 재귀함수로 옮겨주면 됩니다. int f(int x){ if (x

1. [9659] 돌 게임 5 (Silver II) 더보기 1개를 가져가든, 3개를 가져가든 남은 돌의 홀짝성은 "항상" 바뀌게 됩니다. 패배 조건 (0개가 남은 상태)은 짝수이므로, 홀수라면 상근이가 이기고, 아니면 창영이가 이깁니다. void Main(){ ll x; cin >> x; if (x&1){ cout n; if (n%7 == 0 || n%7 == 2){ cout n; if (n%5 == 0 || n%5 == 2){ cout n; int res = 0; while (n--){ int x; cin >> x; res ^= x; } if (res == 0){ cout t; while (t--){ int n, m; cin >> n >> m; while (m--){ int v, w; cin >> v ..

A. [11053] 가장 긴 증가하는 부분 수열 (Silver II) 더보기 \( DP_{i} := \) \( i \)번째 원소로 끝나는 LIS 로 정의하면, \( DP_{i} = \max_{A_{j} \lt A_{i}} DP_{j} + 1 \)로 점화식을 세울 수 있습니다. 초기값은 \( DP_{i} = 1 \)이고, 문제의 답은 \( \max_{1 \le i \le N} DP_{i} \)입니다. int arr[1020], dp[1020]; void Main(){ int n; cin >> n; for (int i = 1; i > arr[i]; } for (int i = 1; i n; for (int i = 1; i > arr[i]; } sort(arr+1, arr+n+1); int q; cin >> q..

A. [2438] 별 찍기 - 1 (Bronze III) 더보기 반복문 예제로 항상 나오는 '별 찍기'에 왔습니다. \( i \)번째 줄에는 별을 \( i \)개 찍어주면 됩니다. void Main(){ int n; scanf("%d", &n); for (int i = 1; i

1. [20295] 사탕 배달 (Platinum III) 더보기 사탕의 종류가 5개밖에 없으니, Bitmask와 Sparse Table을 사용해서 \( v \)의 \( 2^{j} \)번째 조상과 그 경로에 있는 캔디의 종류들을 저장할 수 있습니다. 이제 쿼리를 처리해봅시다. 현재 내가 있는 정점이 \( v \)이고 친구가 있는 정점이 \( w \)이며, 친구는 \( k \)번 종류의 사탕을 원한다고 합니다. 최단경로로 이동해야 하므로, \( l = LCA(v, w) \)라고 할 때 \( v \rightarrow l \rightarrow w \)의 경로로 이동해야 합니다. 즉, \( v \rightarrow l \) 또는 \( w \rightarrow l \)의 경로에 \( k \)번 종류의 사탕이 있는지..

A. [1931] 회의실 배정 (Silver II) 더보기 가장 빨리 끝나는 회의를 진행하면 됩니다. 이러면 선택의 폭이 더 넓기 때문에, 최적해가 잘 구해집니다. 주의할 점은, 가장 빨리 끝나는 회의가 여러개라면, '시작 시간이 가장 빠른 회의'를 선택해야 합니다. 이는 [12, 12], [10, 12] 같은 경우를 잘 처리하기 위한 추가 작업입니다. (만약 저 순서대로 저장되었다면 [12, 12]를 선택 → 12시 이후의 회의가 없음 → 종료 → 출력 = 1이 됩니다.) 시간복잡도는 \( O(N \log N) \)입니다. pl2 arr[100020]; void Main(){ int n; cin >> n; for (int i = 1; i > arr[i].fr >> arr[i].sc; } sort(arr..