보드게임컵

보드게임컵

A - 노 땡스!

단순 구현

00:01 AC

 

B - 할리갈리

단순 구현

00:03 AC

 

C - 크레이지 타임

단순 구현

00:09 AC

 

D - Yacht Dice

단순 구현

00:19 AC

 

N - 수 나누기 게임

Sieve of Eratosthenes 비슷하게 돌리면 된다.

00:23 AC

 

G - 모든 곳을 안전하게

모든 경우에 대하여 실제로 옮겨보면 된다.

00:35 WA

일부 조건을 빠뜨려서 불가능한 이동을 하였다.

00:39 AC

 

E - 벚꽃 내리는 시대에 결투를

다음과 같은 점화식을 세울 수 있다.

dp[i][j] = i번째 공격에서 남은 라이프가 j일 때 남은 오라의 최댓값, 불가능하다면 -1

01:05 WA

01:10 WA

dp 업데이트 과정에서 방법 배열을 제대로 업데이트하지 않았다.

경험이 부족해서 그런지 잘못된 가정을 하였다.

01:12 AC

 

K - 100% Orange Juice!

로직이 참 더럽다.

실제 전투 시뮬레이션을 무한히 반복한다면 승리 확률은 이론적 확률에 수렴할 것이다.

하지만 이를 이용한 풀이는 주어진 시간 제한 내에 작동하지 않았다.

 

별 수 없이 dp를 해야 하는데 다음과 같은 점화식을 세울 수 있다.

dp[k][i][j] = k번째 턴에서 선공과 후공의 체력이 각각 i와 j만큼 남았을 때 선공이 승리할 확률

이때 k가 홀수라면 선공의 턴이고 그렇지 않다면 후공의 턴이다.

 

여기서 딜레마가 발생한다.

최대 턴 수를 낮게 잡으면 오차가 커져 WA를 받고 높게 잡으면 실행 시간이 길어져 TLE를 받는다.

WA는 어찌할 방법이 없으므로 최대 턴 수를 적당히 높게 잡되 적절한 최적화를 동반하여 실행 시간을 줄여야 한다.

예를 들어 승리 확률이 매우 낮은 case는 고려하지 않는 방법이 있다.

고려하지 않는 case가 많아질수록 오차 또한 커지게 되므로 주의해야 한다.

 

이 사이에서 균형을 찾다가 결국에는 장렬히 전사하였다.

01:55 TLE    01:56 WA     02:00 WA     02:02 TLE

02:04 TLE    02:16 TLE    02:22 TLE    02:27 TLE

 

다음과 같이 점화식을 변형할 수 있다.

dp[k][i][j] = 현재 (k == 0 ? 선공 : 후공)의 턴이고 선공과 후공의 체력이 각각 i와 j만큼 남았을 때 선공이 승리할 확률

하지만 이와 같이 정의하면 두 플레이어 모두 회피에 성공하는 경우 사이클이 발생하게 된다.

 

사이클을 방지하기 위하여 점화식을 다음과 같이 변형할 수 있다.

기본적으로 선공과 후공의 체력이 각각 i와 j만큼 남은 상황이다.

dp[0][i][j] = 현재 선공의 턴이고 선공이 승리할 확률

dp[1][i][j] = 현재 후공의 턴이고 후공이 공격에 성공한 경우 선공이 승리할 확률

cnt[i][j] = 현재 후공의 턴이고 후공이 공격에 성공하는 경우의 수

 

업데이트 과정은 다소 복잡하기에 생략한다.

03:08 AC

 

처음부터 이 풀이도 고려하고 있었지만 다음과 같은 이유로 시도하지 않았다.

• 앞서 소개한 풀이가 무지성으로 구현하기 쉬웠다.
• 조금만 최적화하면 AC를 받을 수 있다는 희망이 보였다(그리고 절망으로 바뀌었다).

아무튼 이렇게 든든하게 말아먹었다.

 

H - 테라포밍 마스

생산력은 최대한 빨리 늘리는 것이 이득이고 TR은 최대한 늦게 늘리는 것이 이득이다.

결론만 말하자면 이분 탐색이 가능하다.

턴 수 T가 정해졌을 때 해당 턴 수 내에서 게임을 끝낼 수 있는지 확인하면 된다.

 

생산력은 늘릴 수 있다면 무조건 늘리자.

TR은 (T - Z + 1)번째 턴부터 매 턴마다 늘리면 된다.

TR을 늘릴 수 없다면 턴 수 T로 게임을 끝낼 수 없는 것이다.

 

하지만 예제 입력을 보면 생산력을 늘리는 것이 항상 이득은 아니다.

이를 해결하기 위하여 생산력을 늘릴 때마다 stack에 늘린 시점을 기록해두자.

TR을 늘릴 수 없다면 적절히 rollback하면 된다.

03:45 AC

 

stack을 사용하지 않는 방법도 있다.

현재 생산력으로 남은 턴 수 내에 TR을 모두 늘릴 수 있다면 더 이상 생산력을 늘리지 않아도 된다.

이 조건을 검사해주면 불필요하게 생산력을 늘리지 않게 되므로 stack이 필요하지 않게 된다.

 

수식을 잘 정리하면 이분 탐색 없이 해결할 수도 있다.

생산력을 증가시키면서 해당 시점에서 필요한 최소 턴 수를 구하면 된다.

 

M - 더블 아웃 (not solved)

dp를 잘 하면 되는데 구현이 많이 더럽다.

 

L - 보드게임컵 파티! (not solved)

문제를 다음과 같이 두 가지 과정으로 분할할 수 있다.

• 새로운 매칭이 생겼는지 확인하기
• 매칭된 플레이어 찾기

먼저 새로운 매칭이 생겼는지 확인해보자.

이는 Segment Tree with Lazy Propagation으로 해결할 수 있다.

k번 노드의 초깃값은 k로 초기화하고 다음 연산을 수행하면 된다.

• i번 플레이어가 들어오면 구간 [a_i, b_i]를 1만큼 감소시킨다.
• 이때 값이 0인 노드 중 가장 오른쪽 노드의 번호를 x라고 하자.
• x가 양의 정수라면 x명의 플레이어가 매칭된 것이다.

sqrt decomposition 풀이도 가능하다고 한다.

 

매칭이 생겼다면 매칭된 플레이어를 찾아보자.

이는 Segment Tree로 해결할 수 있다.

각 노드는 해당 노드의 담당 구간을 선호하는 플레이어의 목록을 관리하도록 하자.

이제 다음 연산을 수행하면 된다.

• i번 플레이어가 들어오면 구간 [a_i, b_i]를 담당하는 모든 노드에 i를 삽입한다.
• x명의 플레이어가 매칭되었다면 담당 구간이 x를 포함하는 모든 노드에 대하여 해당 노드의 모든 값을 가져온다.
• 이때 가져온 값의 개수는 정확히 x개가 된다.

마찬가지로 sqrt decomposition 풀이 또한 가능하다.

 

F - 도미니언 (not solved)

먼저 행동 카드의 특성을 살펴보자.

• Act 1 0 or Act 0 1 : 사용하면 손해를 본다.
• Act 1 1 : 무의미한 카드이다.
• Act A B (A > 0 and B > 0) : 언제나 이득이 된다.
• Act A 0 or Act 0 B : 상황에 맞게 잘 사용해야 한다.

따라서 A < 2 and B < 2인 행동 카드는 무시해도 된다.

그리고 A > 0 and B > 0인 행동 카드는 모두 사용하고 시작하면 된다.

Act A B 카드를 사용하면 행동 기회가 A번 증가하고 B장의 카드를 뽑게 된다.

하지만 카드를 사용하는 과정에서 행동 기회가 소모되며 카드 또한 소모하게 된다.

따라서 행동 기회가 (A - 1)번 증가하고 (B - 1)장의 카드를 뽑는다고 생각해도 무방하다.

 

일단은 구매 가능한 카드가 없다고 가정하자.

그리고 편의를 위하여 Act A 0 카드와 Act 0 B 카드를 각각 A 카드와 B 카드라고 하자.

남은 카드는 A 카드와 B 카드뿐이므로 이들만 적절하게 사용하면 된다.

행동 기회가 남아 있다면 B 카드를 사용하고 그렇지 않다면 A 카드를 사용하면 된다.

여러 장이 있다면 A 또는 B가 가장 큰 것을 사용하면 된다.

 

실제로는 A 카드도 행동 기회가 남아 있어야 사용할 수 있다.

하지만 위와 같이 구현하여도 딱히 문제가 발생하지 않는다.

초기에 A > 0 and B > 0인 카드가 존재하지 않는 경우는 예외 처리가 필요하다.

이 경우에는 단 한 장의 카드만 사용할 수 있기 때문에 위의 전략을 사용할 수 없다.

적절히 예외 처리 해주자.

 

여기까지 마쳤다면 구매 가능한 카드가 없을 때 뽑을 수 있는 최대 카드 수를 구할 수 있다.

다음과 같은 배열 E를 정의하자.

E[i] = 추가 행동 기회가 i번 주어질 때 뽑을 수 있는 최대 카드 수

앞서 구한 값은 E[0]과 동일하다.

 

배열 E의 값을 계속해서 구해보자.

구하는 방법은 간단한데 행동 기회를 1만큼 늘려주고 위의 과정을 반복하면 된다.

B 카드가 소진될 때까지 행동 기회를 늘려주면서 배열 E의 값을 구해주자.

 

B 카드가 소진되었다고 모든 작업이 끝난 것은 아니다.

여기서 추가적인 행동 기회가 (x - 1)번 주어진다면 기존에 사용한 Act x 0 카드가 무의미해진다.

이를 해결하기 위하여 A 카드를 사용할 때마다 stack에 A의 값을 기록해두자.

추가적인 행동 기회가 쌓이면 적절히 rollback하면 된다.

행동 카드를 덜 사용하게 되므로 뽑을 수 있는 카드 수가 증가한다.

 

이제 카드를 구매할 시간이 다가왔다.

앞에서와 마찬가지로 A < 2 and B < 2인 행동 카드는 무시해도 된다.

승점 카드 처리는 간단하므로 생략한다.

행동 카드 처리는 조금 복잡한 case work를 요구한다.

 

if B 카드인 경우 then

    // 이는 다시 4가지 case로 분류할 수 있다.

    if 행동 기회가 남아 있는 경우 then

        (B - 1)장의 카드를 뽑는다.

    elif 초기에 A > 0 and B > 0 카드가 존재하였고 A 카드가 남아 있는 경우 then

        // 이 경우 A 카드를 사용한 후에 구매한 B 카드를 사용하면 된다.

        (B - 2)장의 카드를 뽑는다.

    elif 마지막으로 사용한 B 카드보다 구매한 B 카드가 더 큰 경우 then

        // 이 경우 마지막으로 사용한 B 카드 대신 구매한 B 카드를 사용하면 된다.

        (B - last)장의 카드를 뽑는다.

    else

        카드를 사용하지 않는다.

elif B > 0 or 초기에 A > 0 and B > 0 카드가 존재한 경우 then

    // 앞서 구한 E 배열을 적절히 활용하면 된다.

    (A - 1)번의 행동 기회를 얻고 (B - 1)장의 카드를 뽑는다.

else

    카드를 사용하지 않는다.

 

출제자님 말씀으로는 아이디어나 구현 방식에 따라서 예외 처리 난이도가 급격히 변화한다고 한다.

계속 WA를 받아서 코너 케이스 찾기도 너무 어려웠다.

앞으로 도미니언 안 합니다.

 

I - KPvK 엔드게임 (not solved)

정해는 복잡한 dp와 구현을 요구한다.

endgame tablebase를 적절히 압축해서 때려 박으면 날먹이 가능하다.

 

J - 브루마블 (not solved)

Pass

 

끝

끝