코포 일기 : Codeforces Round #721 (Div. 2)

http://codeforces.com/contest/1527

Dashboard - Codeforces Round #721 (Div. 2) - Codeforces

 

최근들어 시간 제한이 있는 대회 환경과 시간 제한 없이 그냥 푸는 환경의 갭을 절실히 느끼게 되는 일이 있었다.

무엇보다도 대회 경험이 너무 부족하다고 느껴서 앞으로 최근 안 하던 코드포스를 꾸준히 하려고 마음먹었다. 또한 코포가 끝날 때마다 일기처럼 간략하게 경험을 기록해두면 좋을 것 같아서 글을 쓴다.

 

대회 결과

A와 B1을 빠르게 풀어 놓고 C에서 한참을 고민하다 결국 풀지 못하고 2솔로 마무리지었다. 오랜만에 해서 그런지 영 실망스러운 결과였다.

 

A : And Then There Were K

N이 주어졌을 때, N&(N-1)&(N-2)&...&K = 0을 만족하는 K의 최댓값을 구하는 문제다. 작은 범위에서 비트 변환한 값들을 나열해 보면 구해야하는 K가 무엇인지 쉽게 알 수 있었다. 결국엔 N보다 작은 메르센 수의 최댓값을 구하는 문제다.

 

B1 : Palindrome Game (easy version)

생각해보면 입력에 주어지는 1은 결과에 아무 영향이 없다는 것을 알 수 있으며, 결국 0의 갯수에 따라 승패가 갈리는 문제다. 생각하는 데 그리 오래 걸리지는 않았다.

 

C : Sequence Pair Weight

모든 부분에서 어떤 값의 총 합을 구하는 문제는 일단 작은 단위별로 등장 횟수를 세어 볼 수 있는지 확인해봐야 한다는 교훈을 얻었다. 생각해보면 (1~N)범위 수열에서 모든 부분수열을 한 번씩 다 따질 때 s, e가 포함된 부분수열의 등장횟수는 s * (N-e+1)이다. 즉, 어떤 인덱스 s1,s2,s3,s4... 과 e를 한 번씩 짝지어 줄 때 총 등장 횟수는 (s1+s2+s3+s4+...) * (N-e+1)이며, 등장할때마다 가중치는 1 추가된다. 이전에 나왔던 값이 나올 때마다 이전 값들의 인덱스들의 합과 (N-e+1)을 곱한 수만큼 결과에 더해 주면 그 값에 해당하는 가중치는 모두 고려한 셈인 것이다. 각각 값들에 대응하는 인덱스 합을 저장하기 위해 map을 사용하여 구현하면 생각보다 간단하게 O(NlogN)에 풀리는 문제였다.