AtCoder Beginner Contest 249

https://atcoder.jp/contests/abc249/tasks

 

대체 이건 언제 있었던 Contest인가

 

A. Jogging

 

그대로 구현

 

B. Perfect String

 

그대로 구현

 

C. Just K

 

비트마스킹하여 S의 모든 subset에 대해서 구현

 

D. Index Trio

 

전형적인 n/1 + n/2 + ... = nlgn을 사용하는 문제

모든 n이하의 자연수 i에 대하여, i의 배수의 j에 대해 cnt[i]*cnt[j]를 더해주면 된다.

https://atcoder.jp/contests/abc249/submissions/31366475

 

E. RLE

 

dp[i][j] : S의 길이가 i이고 T의 길이가 j인 경우의 수

naive한 dp를 해보면 알겠지만, 뒤에 a가 1개오든, 2개오든... 9개오든 T의 길이는 동일하다.

-> 따라서 a가 1개 오는 것에 경우의 수를 더해두고 a가 10개 오는 것에 빼둠으로써 dp를 prefix sum처럼 계산 가능

https://atcoder.jp/contests/abc249/submissions/31382433

 

F. Ignore operations

 

사실 t = 2인게 주어진 순간, 이전의 모든 operation은 모두 받았다고 가정할 수 있다.

따라서 최악의  k - (내 이후의 t = 2인 operation 개수)개의 t = 1인 operation을 제외하여주면 된다.

https://atcoder.jp/contests/abc249/submissions/31382894

뭔가 구현이 중점이 되는 문제 set이였다.

 

G. XOR cards

 

https://koosaga.com/132 -> 웰논이라고 누가 그랬었다. 추가로 'XOR 포커'의 풀이도 참고해라.

get_min( vector a, int b)는 b에 a의 원소들을 적당히 xor하여 만들 수 있는 최솟값이다. (위의 링크 참고)

이제 답이 특정 비트를 가질 수 있는지 확인해주면서 가면된다.

-> 특정비트를 가진 카드들에 (1ll << (i + 31))을 더해주면 이 카드들이 무조건 홀수 개 존재하도록 강요된다.

https://atcoder.jp/contests/abc249/submissions/31391181