전체 글 (78) 썸네일형 리스트형 NYPC 예선 후기 세줄요약1. 머리나쁘고2. 게을러서3. 조짐 이번 NYPC 예선은 내가 공부를 엄청 게을리 하고 있다는 증거를 잔뜩 남겨두고 떠났다. 전체적으로 맞는 풀이인데 구현을 못하거나/반례가 있는 줄 알고 해결하지 못한 문제들이 너무 많았다. 해결하지 못한 문제는 16번 쉴드 생성기, 19번 종이접기, 21번 금 줄 게임, 22번 보라색 영역이다. 점수를 계산해보면 2,135점으로 본선 가기는 그른듯. 다음은 내가 해결한 문제들에 대한 간단한 해설과 소스코드이다. 3. 아이템 구매간단한 일차방정식을 해결하는 문제이다. Naive하게 코딩할 경우 시간복잡도는 선형으로 나온다. 확장 유클리드 알고리즘을 이용해서 로그 시간복잡도로 해결할 수 있을 것 같다는 느낌이 들긴 하는데 그렇게 코딩할 이유는 없으니까 ^^7 12.. [BOJ] 10840 구간 성분 진짜 어이없게 풀었다. 처음에는 해싱인지 모르고 $O(n^3)$에 최적화 생각했는데롤링 해시 구현하기 귀찮아서 그냥 알파벳에 숫자 하나씩 할당해 놓고 다 더한다음에 일치하면 okay라고 판별했다.int 범위 내에서 하니까 충돌나길래 long long 범위까지 늘렸더니 어셉됐다 ㅋㅋㅋㅋㅋㅋ결과적으로는 $O(n^2 lg n) 풀이임. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include #include #include #include #include using namespace std; typedef long long ll; ll prime[]={1553543355441,683.. [BOJ] 2472 체인점 굉장한 학생 문제랑 다익스트라의 짬뽕이다. 덕분에 코드가 장난아니게 길다.각 정점이 최대 5개의 간선을 가지니 다익스트라의 $O(ElgV)$ 시간복잡도가 $O(VlgV)$로 바뀐다. 그러면 주어진 세 정점에 대해서 다익스트라를 한번씩 돌려볼 수 있고, 모든 정점에 대해 주어진 세 정점으로부터 각 정점으로부터의 거리 $dist_i$가 나오게 된다. 거리의 범위는 크지만 대소관계만을 비교하면 되므로 등위를 정렬을 통해 다시 매겨주자. 그러면 굉장한 학생 문제처럼 모든 정점에 대해 체인점을 세울수 있음/없음을 판별할 수 있다. 그 이후 들어오는 쿼리는 $O(1)$에 처리 가능하다. 수행 시간은 다익스트라, 정렬, RMQ 등이 다 섞여서 결과적으로 $O(NlgN)$이다. 개인적으로 문제 자체도 굉장한 학생 문제.. [CF] Codeforces Round #464 (Div. 2) 이번 CF는 총 A~F의 6개 문제로 이루어져 있었다. ABCD 50분만에 다풀고 E 하려다가 도저히 못하겠어서 반쯤 던져놓고 있었는데 끝나기 2분 전에 B 해킹이 들어와서 11초 남기고 B번 마지막 서브미션해서 맞았다. 덕분에 점수도 개판되고 레이팅도 100오를거 50밖에 안올랐다. 그래도 D번을 10분만에 풀어내서 점수에 아아주 큰 타격은 안간듯. D번이 이렇게 쉬울 줄 알았으면 DABC 순서로 풀걸 그랬다. 다음은 내가 푼 문제에 대한 솔루션들.A. Love Triangle time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output As you could know .. [BOJ] 1504 특정한 최단 경로 문제: https://www.acmicpc.net/problem/1504 그냥 다익스트라 몇번 돌리면 된다. 어차피 두 정점을 반드시 지나야 하는 것이라면 시작점->1번->2번->종점 아니면 시작점->2번->1번->종점 2가지 방법 안에서 반드시 최단경로는 나오게 되어 있다. 난이도는 1.75/5. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include #include #include #include #define INF (100000000) using namespace std; int n;vector lis[805]; vecto.. [BOJ] 1916 최소비용 구하기 문제: https://www.acmicpc.net/problem/1916 그냥 다익스트라 그 자체이다. 풀이를 설명할 필요가 있을까? 난이도는 1.5/5 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include #include #include #define INF (2100000000) using namespace std; int main(){ int n,m,st,en; scanf("%d %d",&n,&m); priority_queue Q; vector lis(n+1,vector()); vector dist(n+1,INF); for(int i=0;idist[here]) continue; for(.. [BOJ] 13306 트리 문제: https://www.acmicpc.net/problem/13306 2016 KOI 중등부 3번 문제인 트리이다. 고등부 3번과 굉장히 비슷한 문제이기는 한데, 듣기로는 고등부 3번은 HLD라는 알고리즘을 써야 한다고 알고 있는데 이 문제는 상대적으로 깔끔하게 발상의 전환을 통해 문제를 해결할 수 있다. 실제로 대회장에 갔을 때도 모든 풀이는 다 생각해 놨는데 자료구조 구현을 못해서 실패했다. 웬만하면 풀이를 보기 전에 생각을 더 해봤으면 하는 좋은 문제. 내 해법은 Union-Find Tree로 알려져 있는 자료구조 (Disjoint Set)을 구현해서 문제를 역순으로 풀어 나가는 것이다. 어떤 정점과 그 정점의 부모 정점을 제거하면 그 두 트리는 분리되게 된다. 두 정점 사이에 경로가 존재하려.. [BOJ] 11052 붕어빵 판매하기 문제: https://www.acmicpc.net/problem/11052 너무 쉬워서 자세한 설명은 생략한다. 난이도는 그냥 1/5 123456789101112131415161718192021222324252627282930313233343536#include #include #include #define INF (987654321) using namespace std; int n;int cost[1005];int cache[1005][1005]; int dp(int b, int c){ if(b==0) return 0; if(c>n) return -INF; int &ret=cache[b][c]; if(ret!=-1) return ret; int ma=0; for(int i=c;i 이전 1 ··· 5 6 7 8 9 10 다음
