AtCoder Beginner Contest 189 (올솔)

A - Slot

문제에서 하라는 대로 하면 됩니다. if문으로 C1 = C2 = C3일 때 Won, 그렇지 않으면 Lost를 출력합니다.

 

B - Alcoholic

이것도 문제에서 하라는 대로 $v \times \frac{p}{100} > x$이 되는 시점을 출력합니다. 단, 부동 소수점 때문에 발생하는 실수 오차에 주의해야 합니다. 실수 오차를 없애기 위해 $v \times p > x \times 100$이 되는 시점을 출력하면 정수계산만으로 풀 수 있습니다.

 

C - Mandarin Orange

$N \leq 10000$이니까 $O(N^2)$에 가능합니다. $i$번째 오렌지부터 시작해서 $j$번째 오렌지까지 먹을 때 $x$의 최댓값은 $A_i, A_{i+1}, ..., A_j$ 중 최솟값입니다. 따라서 $i$번째 오렌지부터 시작할 때, $j$를 $i$부터 $N$까지 늘려주며 $x$를 갱신하고 $(j-i+1)\times x$답과 비교하여 답을 갱신해주면 됩니다.

 

D - Logical Expression

오른쪽에서부터 보면서 OR이 나오면, OR 오른쪽이 True인 경우와 OR 왼쪽이 False인 경우로 나눕니다. OR 오른쪽이 True이면 그 왼쪽은 어떤 값이 되더라도 OR 연산까지 했을 때 True가 나오니까, OR이 $i$번째에 나왔다면 $2^i$가지의 경우가 추가됩니다. OR 오른쪽이 False가 된다면 OR 왼쪽이 True여야 하므로 다시 OR이 나올 때까지 True만 있게 됩니다.

 

이 관찰을 잘 정리해보면, 1에다가 OR이 $i$번째에 나올 때마다 답에 $2^i$를 더해주면 된다는 걸 발견할 수 있습니다.

 

E - Rotate and Flip

 

1번 연산 후에는 $(x, y) \rightarrow (y, -x)$가 됩니다.

2번 연산 후에는 $(x, y) \rightarrow (-y, x)$가 됩니다.

3번 연산 후에는 $(x, y) \rightarrow (2p - x, y)$가 됩니다.

4번 연산 후에는 $(x, y) \rightarrow (x, 2p - y)$가 됩니다.

 

$1$번부터 $i$번까지 연산을 적용한 후에, 모든 점들의 좌표가 $(x, y) \rightarrow (ax + by + c, dx + ey + f)$가 됩니다. 이때 $a, b, c, d, e, f$를 위의 성질을 이용해 각 연산마다 계산해주면, 모든 정점에 대해 연산을 적용하지 않아도 됩니다.

 

$K$개의 질의를 받았을 때, 이 $K$를 $A$에 대한 비내림차순으로 정렬하고 $i$번 연산까지 마친 후 $A$가 $i$인 질의의 $B$의 현재 위치를 현재의 $a, b, c, d, e, f$를 적용해 찾아주면 됩니다.

 

구현이 조금 짜증납니다.

 

F - Sugoroku2

 

먼저 불가능한 경우를 확인해줍니다. $A_1, A_2, .. , A_K$에서 $m$개의 연속한 수가 존재한다면 지나갈 수 없습니다. 이 경우 $-1$을 출력해줍니다.

 

나머지 경우는 전부 가능합니다. $0$번에서 출발했을 때 기댓값을 $p$라고 하겠습니다. $n$번보다 큰 곳에서 출발했을 때 기댓값은 $0$입니다. $i$번에서 출발했을 때 기댓값은 ($i+1$ ~  $i+m$번에서의 기댓값의 평균 + $1$)입니다. 만약 $i$가 $A_1, A_2, ..., A_k$ 중 하나라면, 기댓값은 $p$입니다. 이를 이용해 $n-1$번의 기댓값을 구합니다. $n-1$번의 기댓값을 구하면 $n-2$번에서 출발했을 때 기댓값도 구할 수 있습니다. 마찬가지로 $n-3, n-4, ...$번의 기댓값을 구할 수 있습니다. 이걸 계속하면 선이 됩니다

 

각 위치에서의 기댓값은 $a_i + b_ip$로 나타납니다. 0번에서의 기댓값도 $a_0 + b_0p$로 나타납니다. 그런데 이건 $p$입니다. 따라서 $p = a_0 + b_0p$라는 일차방정식이 나오고, $p = \frac{a_0}{1 - b_0}$으로 구할 수 있습니다. $b_0 = 1$인 경우는 없습니다. 불가능한 경우의 조건 때문입니다. 따라서 이게 답이 됩니다.

 

구현하는 방법은 다양합니다.