전체 글 썸네일형 리스트형 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가 되는.. 더보기 abc329 오랜만에 타임어택을 했다. E 구현할 때 문자열 인덱스 구하는게 너무 헷갈렸다. 아니었으면 E를 1번만에 맞고 F까지 쭉 갔을텐데 아쉽다. 특히 E같은 문제는 나올때마다 실수하는게 너무 많아서 아마 특훈을 해야할 것 같다. 근데 E 풀이가 정해가 아니다 A 문자들을 격리시켜주면(?) 된다 더보기 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.rbe.. 더보기 BOJ 18830 - 하이퍼 수열과 하이퍼 쿼리 (D5) PS를 진짜 제대로 하겠다는 마음가짐으로 역겨운 것도 다 풀기로 했다. 하이퍼 시리즈는 유명하다... 차원이 말도 안되게 큰 문제들이다. 얘는 이 문제를 11차원으로 늘린 문제이다. 그럼 그냥 11차원 prefix sum을 박으면 되느냐? 아쉽게도 아니다. prefix sum table을 채우는 원리는 포함-배제 원리이다. 이는 중복하여 더하고 빼는 구간들을 처리하는 것이다. 그래서 11차원 prefix sum을 채우려고 식을 세워보면 무려 2^11(=2048)개의 값을 더하고 빼는 형태가 나온다. 그래서 table을 채우는데에는 총 O(2^11 * nmopqrstuvw)가 나와 전체 서브태스크를 풀 수 없다. (아마 섭태3까지는 풀릴 것 같다.) 다행히도 얘를 O(11 * nmopqrstuvw)에 채울.. 더보기 abc328 오늘 ABC는 F까지 웰노운 덮밥이다. 한줄요약하면 D - 이거, E - 이거 비슷하게, F - 이거 D랑 F는 실제로 복붙했다. A 문제도 기억안난다. 더보기 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.. 더보기 abc327 블루 안녕~ 전에 코포랑 앳코더 좀 잘쳤다고 최근에 친 셋은 다 싫어하는 스타일의 문제로만 구성되어 있다. 덕분에 코포는 다시 1700대로 갔고 앳코더는 그래도 별로 안 떨어졌다. 최근에 기본기 부족이라는 걸 깨달았다. 왜냐면 뉴비 때 코드 복붙밖에 안했으니까 A 뭐 어떻게 하든 상관없다. 더보기 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.r.. 더보기 이전 1 2 3 4 5 6 ··· 9 다음
