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

1. [2183] 테니스 시합 (Bronze II) 더보기 입력은 하나의 완전한 시합입니다. 그러니 입력의 끝 = 시합의 끝이 되고, 시합의 마지막 경기를 이긴 사람이 최종 승자가 될 때 시합이 끝나기 때문에 결국 마지막 경기를 이긴 사람 = 입력의 마지막 글자가 답이 됩니다. void Main(){ int n; string s; cin >> n >> s; int sl = s.size(); cout

1. [19321] Longest Increasing Subsequence (Gold IV) 더보기 예제가 너무 친절합니다. \( f_{i} \)가 큰 값부터, 같다면 앞의 칸부터 시작해서 \( N \)부터 1까지 채워주면 됩니다. 이러면 동일한 레벨 or 낮은 레벨에서의 값은 무시하면서 진행되니 잘 되는 걸 볼 수 있습니다. int arr[100020]; int ans[100020]; void Main(){ int n; cin >> n; priority_queue pq; for (int i = 1; i > arr[i]; pq.push({ arr[i], -i }); } for (int i = n; i >= 1; i--){ int val = pq.top().fr, idx = -pq.top().sc; pq...

1. [14370] 전화번호 수수께끼 (Large) (Gold III) 더보기 숫자를 나타내는 영어단어들을 보면, 자주 나오지 않는 글자들이 있는 걸 볼 수 있습니다. 이를 사용해서 특정 숫자의 개수를 빠르게 판별할 수 있지 않을까요? 네, 됩니다. 심지어, 이 방식으로 10개의 숫자를 모두 정할 수 있습니다. 아래는 각 숫자의 개수를 찾기 위해 사용한 표이며, 이 순서대로 볼드체 처리한 글자를 사용해서 개수를 세주면 됩니다. 0 E O R Z 2 O T W 4 F O R U 6 I S X 8 E G H I T 3 EE H R T 5 E F I V 7 EE N S V 1 E N O 9 E I NN 답이 없는 경우는 문제에서 제외해줬으니 위 방식대로 개수를 신나게 구해주면 됩니다. int cnt[130],..

+ 일부 문제에 대해 my3님의 기하 템플릿이 적용되었습니다. 미리 감사의 말씀을 드리고 시작하겠습니다. 1. [11758] CCW (Gold V) 더보기 문제에서 하라는대로 CCW를 구현해주면 됩니다. int ccw(pl2 a, pl2 b, pl2 c){ ll x = a.fr*b.sc + b.fr*c.sc + c.fr*a.sc; ll y = a.fr*c.sc + c.fr*b.sc + b.fr*a.sc; ll res = x-y; if (res > 0){ return 1; } if (res > a.fr >> a.sc >> b.fr >> b.sc >> c.fr >> c.sc; cout

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. [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 ..

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 \)번 종류의 사탕이 있는지..

1. [2228] 구간 나누기 (Gold IV) 더보기 너무 당연하게도 DP 문제입니다. \( DP_{i,j} := \) 첫 \( i \)개의 수에서 \( j \)개의 구간으로 만들 수 있는 최댓값 이라고 정의해봅시다. \( DP_{i,j} \)의 점화식은 아래 2가지 경우로 나눠서 구할 수 있습니다. A. \( A_{i} \)를 구간에 포함시키지 않기 이 경우, \( i-1 \)개의 수에서 \( j \)개의 구간을 사용하므로 답은 \( DP_{i-1, j} \)가 됩니다. B. \( A_{k~i} \) 구간을 선택하기 이 경우, \( [1, k-1) \) 구간에서 \( j-1 \)개의 구간을 더 사용해야 하므로 \( DP_{k-2, j-1} + \sum_{l=k}^{i} A_{l} \)가 답이 됩니다...