전체 글 썸네일형 리스트형 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(N4) 으로 불가능해 보인다. 그런데 시간은 사실 가능하다. (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.. 더보기 BOJ 8452 - 그래프와 쿼리 (P1) 사용 알고리즘 BFS + Offline Query 풀이 일단 간선 삭제 -> 뒤집으면 간선 추가는 유명하다. 그러고 나서 안될 것 같은 naive한 풀이를 짜면 된다. 그냥 간선이 추가되서 완화되는 정점들을 일일히 탐색하면 된다. 이게 되는 이유를 생각해보자. 1에서 각 정점까지 가는 최단경로는 O(N)일 것이다. (정점이 N개이므로) 그러므로 최단경로가 완화되는 경우도 O(N)일 것이다. 그리고 그러한 정점이 N개 있으므로 전체에서 완화되는 횟수가 O(N^2)이다. 그리고 O(M)개의 간선은 완화될때마다 한번씩 보게 되고, 완화되는 횟수는 말했듯이 정점당 O(N)이므로 간선을 O(NM)번 보게 된다. 따라서 그냥 구현해주면 되며, O(N(N+M)+Q)에 풀린다. 더보기 using namespace st.. 더보기 Codeforces Round 915 (Div.2) 나쁘지 않은 결과이다. A (4분) 사실 풀이를 모른다. 그냥 사람들 푸는 속도 보고 예제 규칙보고 맞췄다. 더보기 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.erase(unique(all(x)), x.end()) #define MOD 1000000007 #define debug.. 더보기 코포특) 버추얼 돌릴때만 퍼포먼스가 겁나 잘나온다. 실제 퍼포는 1850 찍고 라운드 하나 던져가지고 1630까지 내려와서 버추얼이 퍼플 먼저 가게 생겼다. 더보기 BOJ 18798 - OR과 쿼리 (D5) 사용 알고리즘 풀이 1 : Fenwick Tree + Segment Tree (binary search) + Offline Query + fastIO (O(30NlogN)) 풀이 2 : Fenwick Tree + Segment Tree (bitwise AND) (O(30N + NlogN)) 풀이 1 이 풀이의 기본 아이디어는 KOI'23 고기 파티 문제 풀이를 기반으로 한다. 모든 수들은 1번 쿼리에 의해서 어떤 시점에서 K가 되었다가 다시 K가 아니게 된다. OR 연산이 단조성을 띄므로 이 K가 되는 구간은 연속하게 된다. 그래서 모든 수에 대해서 이 시점을 기록한 후, 이를 나중에 쭉 처리하는 아이디어를 이용한다. 1번 쿼리에 순서대로 번호를 붙이자. 이제 i=1~n에 대하여 Ai가 언제 K가 되는.. 더보기 이전 1 ··· 3 4 5 6 7 8 9 ··· 13 다음 목록 더보기
