본문 바로가기

전체 글

2월 PS (2) 티스토리에 서식이 있는 걸 발견했다. 개꿀 2/5 이 글에 있는 문제 위주로 풀었다. BOJ 22306 트리의 색깔과 쿼리 2 트리의 색깔과 쿼리를 온라인으로 처리하는 문제이다. solved.ac 티어 더보기 20240205 기준 : Diamond IV (μ = D4 - 0.23, σ = 0.44) 알고리즘 분류 더보기 solved.ac : smaller_to_larger, hash_set, tree_set, graph_traversal 작성자 풀이 : smaller_to_larger, tree_set, graph_traversal 풀이 더보기 말 그대로 간선을 직접 끊을 것이다. 이를 위해 인접 리스트는 std::set으로 관리한다. 간선을 끊으면 2개의 컴포넌트로 나뉘어질 것인데, 이 중 크기가 더 .. 더보기
Codeforces Round 924 (Div.2) 여러모로 잊을 수가 없는 라운드가 되었다. 일단 점수판을 보면 알겠지만 C에서 말렸다. 풀이 시간은 정확히는 모르겠는데 생각까지 무조건 20분 안이었다. 근데 이 풀이에서 고려하지 않은 케이스가 있었다. 근데 구현 실수인줄 알고 진짜 시간을 내다버렸다. 그렇게 1시간만에 힘들게 C를 풀고 망했다고 마음속으로 외치며 D를 봤다. 그 뒤의 이야기는 풀이를 적으면서 설명하겠다. A 얘 보자마자 뇌가 멈췄다. 머릿속에선 홀짝성을 외치고 있는데 내 손은 이상한 관찰만 하고 있다. 근데 이 덕분에 judgement error 이슈를 피해갔다(?). 결국 6분째에 AC 더보기 #include using namespace std; #pragma GCC optimize("O3") #pragma GCC optimize(".. 더보기
BOJ 16901 - XOR MST (D4) 본인 풀이로 푼 사람이 없는 것 같아서 써 본다. 알고리즘 분류 Union Find, Trie(xor minimization/update), MST(idea) 풀이 일단 생각을 해보자. 일단 크루스칼 알고리즘 기준으로 생각해보면, 아직 하나도 병합되지 않은 정점이 처음 병합될 때, 당연히 가중치가 최소인 간선을 통해 병합될 것이다. 그럼 얘를 찾아주자. 가중치가 XOR이므로 자신을 제외한 정점 중 xor했을 때 최소인 정점과 연결해야 할 것이다. 이는 Trie를 이용하면 O(비트 개수)에 찾을 수 있다는 사실이 알려져 있다. 일단 이 과정을 모든 정점에 대해 한번 반복했다고 하자. 여기서 2가지 관찰을 할 수 있다. 1. 한 번 병합된 컴포넌트들을 다시 하나의 정점 그룹으로 생각하면, 각 정점 그룹에서도.. 더보기
2월 PS (1) 매주 일요일마다 푼 문제를 정리하려고 한다. 언제까지 갈 진 모르겠다. 2/1 : KOI 문제 하나가 끌려서 잡아서 풀었고, 계절학교 문제 출처 찾아다니다가 P2 1개, D3 1개를 날먹했다. KOI'23 블록 쌓기 solved.ac 티어 더보기 20240201 기준 : Platinum II (μ = P2 - 0.24, σ = 0.45) 알고리즘 분류 더보기 solved.ac : dp, prefix_sum 작성자 풀이 : dp, prefix_sum (dp최적화용) 풀이 더보기 제한을 보니 DP인데 DP 식을 세우기에 꽤 까다로워 보인다. 뭐든 간에 관찰을 해서 단순화시켜야 할 것 같다. 먼저 구간(L~R)에 대한 dp식을 세울 지 1~i에 대한 dp식을 세울 지 생각해 봤다. 현재 보고 있는 칸에 쌓을 .. 더보기
overflow https://www.acmicpc.net/problem/31286 31286번: 철도 2 $N = 6$, $U = [0, 1, 2, 3, 4]$, $V = [1, 2, 3, 4, 5]$, $W = [3, 1, 4, 1, 5]$인 경우를 생각해 보자. 그레이더는 다음 함수를 호출한다. travel([0, 1, 2, 3, 4], [1, 2, 3, 4, 5], [3, 1, 4, 1, 5]) 모든 가능한 $(x, y)$ 순서쌍에 대 www.acmicpc.net 이번 선발고사 4번 문제이다. O(N^2logN^2)까지 짜서 당시 37점을 먹었는데 그 코드에서 꽤 직관적인 관찰 하나로 필요한 mst 간선만 남기면 바로 100점이 나오는 문제였다. 풀이를 듣자마자 이걸 왜 못맞췄지 소리가 절로 나왔다. 그리고 그.. 더보기
BOJ 3654 - L퍼즐 (D4) 사용 알고리즘 Bipartite Matching 풀이 L을 가로 일자랑 세로 일자로 분리해서 생각해보자. 그럼 결국 검정색 하나를 기준으로 흰색 2개가 가로에 최대 1개, 세로에 최대 1개 붙을 수 있다. 이를 이용해 이분 그래프를 만들고 이분매칭을 해서 전체가 매칭되는지 확인하면 된다. BOJ는 hopcroft-karp로 냈는데 코드가 길어서 여기서는 일반 이분매칭 코드를 올린다. 더보기 #include using namespace std; #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define all(x) x.begin(), x.end() #define rll(x) x.rbegin(), x.rend() #define com.. 더보기
1월 23일, 24일 PS 원래 23~31일 해서 정리해서 올릴려고 했는데 25일부터 적는 걸 깜빡했다. 기억 안나서 이거라도 올린다 1 / 23 solved.ac에서 /olympiad *p -solved_by:$me 로 랜덤 돌림 USACO US Open 2015 Contest Gold : 팰린드롬 경로 3 더보기 가장 먼저 떠오르는 풀이는 \( dp[i][j][k][l] \)를 중간에서 시작해서 현재 \( (i,j) \)랑 \( (k,l) \)일 때 팰린드롬 경로 개수로 정의한 다음에 푸는 것이다. 하지만 메모리, 시간 모두 \( O(N^4) \) 으로 불가능해 보인다. 그런데 시간은 사실 가능하다. \( (i,j) \)에 있을 때 유효한 \( (k,l) \) pair가 \( O(N) \)개 밖에 없다는 사실을 관찰할 수 있다.. 더보기
Codeforces Round 917 (Div.2) 원래 짜증나서 안 쓸려 했는데 원래 망한 대회에서 배울 점이 생기므로 그냥 쓰겠다. A 뒤에 있을 모든 문제가 충격이 강해서 문제가 기억이 안난다. n개 곱 부호 판별하는 문제였는데 그냥 다 곱하면 오버플로나서 1틀했다. 더보기 using namespace std; #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #pragma optimize("unroll-loops") #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define all(x) x.begin(), x.end() #define rll(x) x.rbegin(), x.rend() #define comp(x) x.eras.. 더보기

티스토리툴바