kdh9949

문제를 다 읽은 후 잠시 생각을 해 본 결과 1, 2번은 일단 전혀 모르겠었다. 생각나는 대로 적당히 긁은 뒤 그나마 하면 점수가 나올 것 같았던 3번을 잡았다. 3. Tasks Author (데이터 만들기)Single source shortest path 문제와 vertex coloring 문제를 푸는 코드에 대해 어느 것은 시간초과를 내고(cnt 변수를 100만 이상으로 증가시키고) 어느 것은 통과시키는 데이터를 만드는 문제다. 총 8가지의 subtask가 다음과 같이 나뉘어 있다.(SSSP : 최단경로 / Mystery : vertex coloring)subtask 1, 3 : n = 101이고 간선 없는 데이터 넣으면 된다. 손으로도 20초면 만든다.subtask 2: BellmanFord 코드와..

문제 난이도가 1->2->3 순서인것 같아서 (사실 1은 유명한 문제라 대충 알고 있었다) 그 순서대로 풀었다. 1. Dispatching큰 set에 작은 set을 합치는 그 유명한 테크닉을 쓰는 가장 대표적인 문제라고 주변에서 워낙 많이 들었었다. 그래서인지는 몰라도 문제를 직접 읽어 본 적은 없었지만 읽자마자 풀이가 바로 떠올랐고, 짜서 어려움 없이 맞았다.매니저가 정해지면 그 매니저의 서브트리에 있는 노드들 중 월급이 작은 것부터 최대한 많이 고르는 것이 당연히 이득이다. 따라서 각 서브트리별로 월급 순으로 적절히 정렬된 자료구조를 잘 들고 다닐 수 있으면 될 텐데, 각 노드별로 set을 들고 다니면서 합쳐 주면 편하게 처리할 수 있다.한 번 고려 대상에서 제외된 노드가 나중에 다시 들어올 일은 없..

시간을 두고 생각해 보았지만 아무 생각이 안 나서 (이러면 안 되는데.. ㅠㅠ) 풀이를 보려고 JOI 사이트에 들어갔는데... 풀이 pdf가 일본어 + 글씨가 그림 형태로 저장되어 있어서 읽을 수가 없었다. 다행히도 풀이 예시 코드가 같이 올라와 있어서 그것을 읽고 나름대로 풀이를 재구성해 볼 수 있었다.모든 쿼리가 수행된 이후 땅의 모양을 보면 여러 갈래로 잘린 대각선들이 마구 놓여 있는 형태가 될 텐데, 임의의 쿼리가 자르고 지나간 "선의 모양"은 그 이후에 수행된 쿼리에만 영향을 받는다는 관찰을 할 수 있다. 여기서 쿼리를 거꾸로 처리하면 편하다는 생각을 할 수 있다. 한편, 각 쿼리는 최종적으로 봤을 때 자신이 자르고 지나간 선 위쪽의 땅의 값을 특정 값만큼 더해주는 역할을 하므로 각 선이 최종 ..

1. 스탬프렐리-2 (11986)편의상 J를 1, O를 2, I를 3이라 하자.pdp[i][j] : 1~i번째 상점까지 봤을 때 1~j번 스탬프까지 받은 경우의 수,sdp[i][j] : n~i번째 상점까지 봤을 때 3~j번 스탬프까지 받은 경우의 수로 각각 정의하자. 각각의 점화식은 O(1) 점화식으로 매우 간단히 구해진다.k번째 상점 바로 뒤에 스탬프 m을 가진 상점을 끼워 넣을 때 추가되는 경우의 수는 pdp[k][m-1] * sdp[k+1][m+1]이다. 이 중 최댓값을 mx라 하자. 그러면 답은 (끼워 넣은 상점에서 스탬프를 안 받는 경우의 수) + (받는 경우의 수) = pdp[n][3] + mx로 간단히 구해진다. 시간복잡도는 자명히 O(N). 2. POI (5462)각 참가자를 (받은 점수,..

JOI Spring Camp는 IOI 일본 국가대표 선발을 목적으로 진행하는 Contest입니다. 4일 동안 매일 3문제 정도로 구성된 Contest를 진행해 합산 점수로 국가대표를 선발하는 듯 합니다. 문제 퀄리티가 매우 높고, 적절히 쉬운 문제부터 아주 어려운 문제까지 난이도도 골고루 분포하고 있습니다. http://www.ioi-jp.org/camp/(Year)/(Year)-sp-tasks/index.html 위와 같은 형식의 url에 접속하면 (Year) 해에 치뤄진 대회에 관한 정보가 정리되어 있습니다. (2007년부터 가능)(Google 번역 창에 url을 치면 홈페이지를 번역해 보여주니 참고하세요!!) 2007년부터 2011년까지는 기본적인 정보만 제공합니다. 각 Day별로 대회 시간 / O..

대회 링크 문제를 일일이 설명하기에는 제 필력이 딸립니다 ㅠㅠ 풀이(또는 생각)만 덜렁 적혀있더라도 이해해주세요... A. Plus and Square Root (AC) 레벨 \(i\)에서 \(i+1\)로 넘어갈 때에 변수가 \((i(i+1))^2\)의 값을 가지고 가면 됩니다.간단한 수학 문제였네요... 이런 걸 풀 때는 "느낌"으로 푸는 거라고 누가 그랬습니다 (?) 소스 B. Complete The Graph (못품) 비용이 0인 엣지를 다 끊어놓고 Dijkstra를 돌리나...? 일단 Dijkstra를 돌리고 0인 엣지가 포함된 것의 여부에 따라 어떻게 잘 처리를 하나...? 여러 생각을 해 보았는데 정말 아무 생각이 안 들어서 일단 넘겼습니다.그리고 대회 끝날 때까지 다시 보지 않았습니다 ㅎㅎ ..