문제 링크 https://www.acmicpc.net/problem/15921 힌트에 괜히 쓸데없는 말을 집어넣어서 평균과 기댓값을 구하도록 유도하는데 굳이 그럴 필요 없다. 기댓값 $E(X) = \sum\nolimits_{i}p_ix_i$이고 어떤 수 x가 수열에 등장할 확률 $P(x) = \dfrac{\text{x의 등장 횟수}}{\text{전체 수열의 길이}}$ 이다. x의 등장 횟수를 $c$라 하고 전체 수열의 길이를 $n$이라 하면 $P(x) = \dfrac{c}{n}$ 이고 이때 $px = \dfrac{cx}{n}$인데, 이는 $\dfrac{x}{n}$ 을 $c$번 더한 것과 같다. 결국 기댓값 $E(X) = \sum\nolimits_{i}\frac{x_i}{n}$이므로 평균과 다를 바 없기 ..
문제 링크 https://www.acmicpc.net/problem/15920 단순 구현? 시뮬레이션? 문제다. state를 정의하자 state == 0 일때 마네킹 5개가 날아가고 state == 1 일때 마네킹 1개가 날아가고 state == 2 일때 마네킹 6개가 모두 날아가는 걸로 하자. P가 나올때마다 state의 상태를 0 ~ 1 사이에서 반전시키는데, W가 한 번 나온 상황에서 P가 나온다면 state를 2로 고정시키자. W가 2번 나왔을 때 답을 출력하고 종료하자. 정답 코드 질문, 피드백 환영합니다.
문제 링크https://www.acmicpc.net/problem/15917 어떤 수 a가 2의 거듭제곱꼴인지 판별하면 된다.쿼리의 수 Q가 $1 \leq Q \leq 1,000,000$이므로 단순히 a의 비트를 순회하며 1이 하나인지 확인해도 $O(32Q)$이므로 충분하다.좀 더 효율적으로 하고싶다면 $a\ \&\ (a - 1)$이 0인지 확인하자.모든 양수 a에 대해 a가 2의 거듭제곱꼴이라면 위의 값이 0이 나온다. 글을 쓰면서 문제를 다시 확인했는데 힌트 부분에 이미 답이 나와있었다... 닉값하는 문제;; 정답 코드 질문, 피드백 환영합니다.
문제 링크https://www.acmicpc.net/problem/15916 평면 위의 점들을 이은 그래프와 한 직선 $y = kx$가 주어졌을 때 $(0, 0)$이외의 점에서 한 번이라도 직선과 그래프가 만나는지를 확인하면 된다. CCW를 이용해 선분의 교차를 확인하자. 우선 직선과 선분의 교차 여부를 판단하기는 어려우니, 선분과 선분의 교차 여부를 확인하기 위해 $y = kx$를 선분으로 만든다. 평면 위 점들의 y좌표가 $0 \leq y \leq 2^{30}$ 이므로 직선 위의 점 중 $y' > 2^{30}$ 를 만족하는 적당한 점$(x',\ y')$와 $(0, 0)$을 이어 선분으로 만들면 된다. $x' = \dfrac{2^{31}}{k}$ $y' = kx'$ 정도가 좋겠다.수학적 나눗셈이 아닌 ..