kdh9949

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번은 레이저 광선이 지나가는 경로에 거울..

시험 날 왠지 모르게 졸렸다. 그게 약간 영향을 미친 것 같기도 하다....시험장에 들어가 컴퓨터를 만져 보는데 엄청 느렸다. 삼성전자 인재개발원이 그리워지는 대회 환경이었다 ㅠㅠ문제 3개를 딱 펴 본 뒤 처음 든 생각은 "아무것도 모르겠다" 였다. 1번은 2차원 그리드에서 특정 직사각형 내의 점들의 연결 컴포넌트 수를 구하는 쿼리 문제였는데 매우 어려워 보였고, 2번은 그래프를 돌면서 특정 작업을 하는데 그러면서 가장 짧은 시간 안에 이익을 많이 내는 사이클의 효율을 구하는 문제였는데 역시 매우 어려워 보였다(...) 3번은 interactive하게 게임을 진행하면서 상대가 N개의 아이템에 매겨 놓은 값을 구하는 문제였는데 이것도 아무것도 모르겠었다 ㅜㅜ 일단 그나마 잡으면 점수가 나오긴 할 것 같았던..

문제를 다 읽은 후 잠시 생각을 해 본 결과 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..