13개의 댓글이 있습니다.
-
-
Kureyo -
인덱스 트리가 싫다면 다음과 같은 방법을 해보셔도 괜찮습니다. 닌자의 수가 10만이나 되면 너무 많기 때문에, 대략적으로 월급 소득에 따라 그룹핑을 해봅니다.
상위 1/3에 들면 고소득자, 그 다음은 중산층, 그다음은 저소득자 이런 식으로요. 그리고 고소득자들의 리스트, 중산층의 리스트, 저소득자의 리스트를 따로 관리합니다.
이제 각 S_i에 대해 고소득자, 중산층, 저소득자의 숫자를 계산해둡니다. 그리고 S_i의 원소들의 임금의 총합이 높을때, 고소득자가 존재한다면 고소득자 리스트를 훑어보면서 i의 후손인지 파악합니다. (dfs 방문 번호를 이용하면 O(1)시간에 알수 있습니다.) 그래서 고소득자 중에서 가장 임금이 큰 사람을 찾아 지웁니다.
11년 전 link
-
-
-
Kureyo -
3개의 그룹 대신 G개의 그룹으로 나누었다고 생각해봅시다. 그러면 각 S_i에 대해서 G개의 그룹카운트를 합치는 시간이 필요하므로 O(NG)의 시간이 듭니다. 그리고 각 리스트를 최대 N번 탐색할수 있으므로 이때 드는 시간은 O(N*N/G)시간입니다.(리스트의 길이는 N/G이므로)
f = NG + NN/G 를 최소화 하기 위해 G에 대해 미분해보면
df/dG = N - N^2/G^2 = 0 , G^2 = N.
즉, G=sqrt(N)일때입니다. 이때의 시간복잡도는 O(N^1.5)이 되므로
약간 빠듯할수는 있지만 충분히 답이 나올수 있을것입니다.
11년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
장홍준
링크 : http://www.ioi-jp.org/apio2012/tasks.html
(원하시는 언어를 골라서 보시면 됩니다.)
닌자 사이의 관계들은 트리의 형태로 표현되므로 동적계획법으로
D[i][2] : i번째 닌자를 배치할 때와 않았을 때의 고객 만족도의 최댓값
로 테이블을 정의하여 문제를 풀었는데요.
i번째 닌자를 배치하지 않을 경우에는 그냥 자식들을 훑어주면서 값을 갱신할 수 있는데
i번째 닌자를 배치할 경우에는 자신의 자식들 중 배치할 수 있는 최대 닌자 수를 구하는 데에 힙을 사용하여 병합하면서 해결했는데요...
그냥 단순히 저렇게 하면 트리의 형태에 따라 많이 느리므로 병합하는 과정에서 최적화시켜주고 여러가지 불필요한 처리들은 하지 않게 하니까 모든 데이터들이 0.5초 정도 안에 나옵니다ㅠ
이 문제를 어떻게 해결하면 더 빨리 풀 수 있을까요?
11년 전