kdh9949

paint, messy, ailen 문제를 풀었다. 일단 messy가 interactive고 뭔가 별로 안 어려워 보여서 먼저 시작했다.제한을 보면 N=128인데 입력, 조사 쿼리가 각각 896=7*128=NlogN이라 딱 봐도 뭔가 반씩 나눠서 잘 하면 되겠다는 생각이 들었고, 일단 처음에 "1000...00", "01000...00" 같이 1개만 1인 문자열을 처음 반 개만 만들어서 넣어 보면 처음 반이 어디로 mapping되는지 알 수 있다는 것에서 시작하여, 그 다음에 분할을 어떻게 할 지 생각하다가 일단 보고자 하는 구간 [s, e]의 모든 수가 어디로 가는지 안다면 나머지 부분에 다 1을 채워 넣으면 된다는 것을 생각하고, 이를 이용해 간단한 분할 정복 풀이를 짜서 맞았다. 풀이가 빠르게 생각..

molecules, railroad, shortcut 문제를 풀었다. 사실 세 문제 다 예전에 본 적이 있는 문제였긴 하다.가장 먼저 molecules를 풀었다. 탐지 범위가 분자들간의 무게 차이의 최댓값 이상이라는 조건 때문에 주어진 수들을 정렬한 뒤 임의의 [s, e] 구간의 합만 고려해도 충분하다는 사실을 알 수 있다. 각 구간의 길이에 대해 이분탐색으로 간단히 조건을 만족하는 구간이 있는지 판별할 수 있다.그 다음에는 railroad와 shortcut을 각각 봤는데, 둘 다 일단은 아무 생각이 들지 않았다. railroad는 34점 풀이까지는 간단히 생각할 수 있었어서 일단 보류한 뒤 shortcut에 대해 고민을 좀 한 결과, 케이스를 적절히 나누고 전처리를 몇 가지 하여 모든 지름길을 놓는 경..

역대 POI 문제 중 ploughing, subway, railway 문제를 한 셋으로 풀었다.처음 문제 세 개를 훑어 본 후 ploughing과 subway는 일단 제쳐 둔 뒤 railway 문제에 대해 뭔가 쉬운 그리디가 떠올랐고, 1시간 좀 안 되게 열심히 노력한 결과 그게 틀렸다는 것을 알 수 있었다... 습관이 참 무섭다.그냥 18점 naive 풀이를 긁은 후 ploughing으로 넘어와서 다시 생각을 해 봤는데 O((HW)^2) 말고는 아직 잘 모르겠었다. subway도 마찬가지로 "리프 쌍들을 적절히 잘 고르면 된다"라는 것에서 더 넘어가지를 못 했다.railway 문제에 대해 다시 고민해 본 결과 풀이에 접근할 수 있었다. 기차가 들어오는 순서가 정해지면 각 기차가 몇 번째 기차까지 들어온..

Day 2 set에서 내가 예전에 풀었던 적이 있는 router를 빼고 kangaroo가 들어갔다.kangaroo를 보고, 문제가 뭔가 쉬울 것 같아서 먼저 잡았다. 너무 급하게 달려들었는지 생각이 잘 정리가 되지 않았고, 51점 풀이 같은 것을 생각한 뒤 일단 넘어갔다.match는 처음 봤을 때는 아무런 생각이 들지 않았다. 뭔가 Greedy한 가정을 하나 세워야 할 것 같은데 그것이 뭔지 잘 보이지 않아서 일단 또 넘어갔다.popeala는 문제를 읽자마자 "dp 최적화 문제"라는 생각이 바로 들었고, O(NT^2) Naive dp를 세워 일단 코딩을 했다. 그 다음에 좀 더 생각을 해 본 결과, i번 나눈 dp값에서 (i+1)번 나눈 dp값을 구할 때 더해지는 cost값을 N개의 구간으로 나누면 각각..

문제를 한 번 훑어 본 결과 1번이 뭔가 쉬워 보였고, 2번은 예전에 풀었던 다른 문제와 굉장히 비슷해 보였다. 그래서 그 두 개를 먼저 풀기로 했다.1번은 최대 8개의 다른 색의 점 중 일정 구간의 점들을 택하는데, 어떤 k종류 이상의 색의 점을 모두 같은 개수씩 가져가는 구간 중 가장 긴 구간의 길이를 구하는 문제이다. 8개 중 k개 이상의 색을 고르는 경우를 모두 해 보면서(약 2^8가지 경우가 있다) 각 경우에 대해 map을 이용하면 선택한 색들이 모두 같은 갯수만큼 들어간 구간들을 O(NlogN) 시간에 구할 수 있는데, 마지막 부분에서 약간 애매하게 TLE가 난다. 새로운 풀이를 잠시 생각해 보았으나 더 좋은 풀이가 생각이 나지 않아 2번으로 넘어갔다.2번은 레이저 광선이 지나가는 경로에 거울..

문제를 다 읽은 후 잠시 생각을 해 본 결과 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)각 참가자를 (받은 점수,..