9/12 ~ 9/18 PS (+ 앳코더 민트)

잘해지고 싶다

 

 

BOJ 24618 - Robot Instructions (P4)

 N <= 40이므로 mitm을 생각해볼 수 있다. hash map을 사용하여 한쪽의 가능한 \(2^{20}\)가지의 결과들을 모두 저장해두고, 반대편에서 찾아주면 된다. 여담이지만 mitm은 투표를 어느 티어로 할 지 모르겠다.. 

 

 

BOJ 13359 - Fleecing the Raffle (P5)

 식정리 해둔 이면지가 버려진 관계로 계산을 모두 생략하고... \(k\)개의 이름표를 넣는다고 할 때, \(k=\lfloor \frac{n}{p - 1}\rfloor\)일 때 최적이다. 이제 단순히 확률 계산을 해주면 된다.

 

 

BOJ 25563 - AND, OR, XOR (D5)

 and의 경우, \(A_i \& k = k\)를 만족하는 \(A_i\)만 볼 수 있다. 여기에 \(k\)를 XOR해주고, sos dp를 돌려주자. 이제, 각 수들에 대해 \(cnt_i \times dp_{not\_i}\)들의 합이 된다. or도 비슷하다. \(A_i | k = k\)를 만족하는 수들만 봐주면 된다.

 

 

BOJ 11872 - 님 게임 나누기 (P3)

 그런디 수는, 1, 2, 4, 3 / 5, 6, 8, 7 / 9, 10, 12, 11 .... 이런 규칙이 있다.

 

 

BOJ 11695 - 표 게임 (P4)

 어떤 행에서 게임을 하는 것은, 이 행의 합에서 님 게임을 하는 것과 동치이다.

 

 

BOJ 16436 - 얼룩말 아트 (P3)

 직사각형은 쉽게 떠올릴 수 있었지만, 다이아몬드에 대한 아이디어가 떠오르지 않아 검색을 했다. 2차원 imos법이라는 글이 나왔고, 이를 통해 풀 수 있었다. 풀이는 저 글로 대체하겠다

 

 

BOJ 15420 - Blowing Candles (P3)

 각 점에서 어떤 직선에 대해 Rotating Calipers를 돌려주면 된다. 이런 문제를 처음 풀어보았는데, 신기했다.

 

 

 평일에 코포 할 시간이 없는 관계로 앳코더만 주구장창 해야겠다. 빨리 블루 찍어야지

역시 점수가 잘 안 오른다

 주말에 코포+앳코더 둘 다 참가해도 재밌긴 할 것 같다 ㅋㅋ