제 1회 임스의 메이플컵

xiaowuc1을 이겼다.

또한 이 시점에서 1등이 확정지어졌다. (사실상)

물론 이건 D의 지문이 외국인이 알아듣기 상당히 어렵게 되어있을 것이기 때문이란걸 알고 있다. ㅋㅋㅋ

보면 알겠지만, D, E, G를 모두 틀리고 5분 내로 고쳐서 AC를 받아낸 것을 알 수 있다.

D, E, G를 각각 한 번씩 틀린 이유는

D : D에 배치되어 있으니 쉬울 것이라고 예상하여 아주 간단한 최적화를 안함

E : 문제 답 출력에서 (X != Y)라는 조건이 있는데 귀찮아서 1이 최적이면 1, 1을 그냥 출력하게 만듦

G : 문제 입력을 보면 u, v 어쩌구 저쩌구가 되어 있는데 저게 당연히 (u, v)는 되지만 (v, u)는 안된다는 내용일거라 착각

 

A. 임스의 메이플컵

 

for문을 쓰면 된다.

 

B. 에르다 노바와 오리진 스킬

 

사실 1분컷 할만한 문제지만 실수하면 20분 패널티를 먹기에 상당히 심혈을 기울여서 여러 번 읽었다.

아무튼 일단 A, B를 정렬하자.

그 다음에 앞에서부터 각각 100초, 360초 간격이 넘는 것만 고려해서 횟수를 더해주면 된다.

90초 스킬 면역이란 조건이 재사용 대기시간 때문에 그닥 의미는 없다.

 

C. 규칙적인 보스돌이

 

K = 13에 집중하자.

즉, 어떤 캐릭터가 잡을 수 있는 보스의 조합은 많아야 2^13개이다.

따라서 각 캐릭터에 대해 2^13가지 케이스를 모두 해보아서 각각 얻을 수 있는 최대 메소를 구하자.

그 후 제일 메소를 많이 버는 M개의 캐릭을 고르면 된다.

 

D. 라라와 용맥 변환

 

만일 i번 위치에 체력이 H인 몬스터가 있을 때 용맥을 부른다면 i + H까지 그 용맥은 부를 수 없다.

따라서 대충 {해, 강, 바람} = {A, B, C}인 숫자 쌍 세 개를 잘 관리하면 될 것 같다는 생각을 할 수 있다.

예를 들어 i >= A이고 i번 위치가 해 용맥이면, {A, B, C}를 {A + H, B, C}로 바꿔버리는 것이다.

물론 i번 위치가 강, 바람 용맥이더라도 1번 스킬을 써서 바꿀 수 있다.

 

dp[i][{A, B, C}] = i번 위치에서 {A, B, C}이기 위한 최소 스킬 횟수

위의 정의를 따르면 dp[i + 1][{A + H, B, C}] = min(dp[i + 1][{A + H, B, C}], dp[i][{A, B, C}] + (현재 용맥이 해 인지))

아무리 dp[i]에 map을 가져다 썼더라도 {A, B, C}의 경우의 수가 너무 많다는 생각을 할 수 있다.

 

우선 생각해보면 A < i라면 {A, B, C}를 {i, B, C}라고 여겨도 다를게 없음을 알 수 있다.

또한 만약에 A > i, B > i, C > i라면 이 쌍은 곧 사라진다는 것을 알 수 있다.

따라서 무조건 하나는 i여야 하고, i가 i + H로 날라가면, i + 1을 담당할 숫자가 필요하기에 다른 것도 적당히 작다.

이 모든 것을 고려해보면 A, B, C가 몇 개 없으니 무식한 dp를 해봐도 된다.

 

E. 엘나스의 용사

 

우선 포탈이 무조건 1층과 x층에 놓여야 한다는 것은 금세 알 수 있다.

precalc[i][j] = { 포탈이 i층에 있을 때, 용사의 시작 레벨이 j라면 k일 동안 필요한 이동시간 }

위의 200 * 200개의 값을 미리 모두 계산해보자.

 

우선 각 층을 레벨 순으로 정렬하자. 즉 {Level[i], i}로 정렬할 수 있다.

현재 내가 적당히 x층에서 파밍해야한다고 생각하자. 

'다음 층'은 x + 1층이 아니라 아까 {Level[i], i}로 정렬했을 때 바로 뒤에 있는 층이라고 하자.

그러면 다음 층의 레벨에 도달할 때까지, 혹은 k일이 될 때까지, 혹은 200렙이 될때까지 그 층에 머물러야 한다.

따라서 min(200, k + (시작 레벨), 다음 층의 레벨) - (현재 레벨)의 시간만큼 x층에 머물러야 한다.

이러면 모든 층을 한 번 씩 순회하여 하나의 precalc를 O(M)으로 계산할 수 있다.

 

이제는 쉽다!

포탈이 y층에 존재한다면 총 이동시간은 precalc[y][h[i]]의 합이다.

모든 값들 중에서 최소값인 곳에 마법석을 설치하면 된다. 

O(200N + 200 * 200 * M)이라서 쪼금 시간이 빡빡할 수 있다고 생각했는데, 잘 통과했다.

 

F. 한 대

 

우선 기본적인 아이디어는 다음과 같다.

-> 현재 공격력 atk에 대해서 제일 크게 공격력을 향상시켜주는 a, b를 고르자.

위의 아이디어를 보면 ax + b를 최대화시켜야 하니 CHT가 바로 떠올랐다.

CHT에서 고른 최적의 (a, b) 쌍을 앞으로 (A, B)라고 하자.

 

만일 A * atk + B <= atk라면, 스킬을 몇 번 쓰더라도 atk가 늘지 않기 때문에 불가능하다. (-1)

만일 A = 1이라면, 이분탐색으로 A != 1이 될 때까지 이 스킬을 몇 번 써야하는지 구하면 된다.

만일 A > 1이라면, 대충 지수적인 무언가의 힘으로 이 스킬이 많이 안 쓰일 것이라고 믿으면 된다.

 

G. 헤카톤

 

열심히 무언가를 고민 -> 플로우가 되네 -> N = 100이네 -> AC