Codeforces Round 857 (Div. 1)

Dashboard - Codeforces Round 857 (Div. 1) - Codeforces

A - The Very Beautiful Blanket

cnt는 분명 N * M일 것 같았다.

A[i][j] = 1LL << ((4 * i + j) % 60);

00:04 WA

 

무슨 생각으로 저런 말도 안 되는 답을 떠올린 것인지 나도 잘 모르겠다.

아무튼 모든 2 x 2 submatrix의 xor 값이 0이 되도록 만들 방법이 있을 것 같았다.

A[i][j] = 200 * i + j;

00:10 WA

 

200 * i의 하위 비트로 인하여 문제가 발생한다.

구체적으로 다음과 같은 submatrix에서 조건을 만족하지 못한다.

    5        6

205    206

                    407    408

                    607    608

200 대신 256을 사용하면 문제를 해결할 수 있다.

A[i][j] = 256 * i + j;

00:14 AC

 

B - Buying gifts

편의를 위하여 모든 a의 값은 서로 다르다고 가정한다.

다음과 같은 관찰이 필요하다.

• a > m1인 모든 (a, b) pair에 대하여 m2 >= b를 만족한다.

따라서 a가 큰 순으로 정렬한 후 그리디하게 계산하면 된다.

00:20 WA

00:24 WA

 

다음과 같은 추가적인 관찰이 필요하다.

• a > m1인 모든 (a, b) pair에 대하여 max(b)를 m3라고 하자.
• a < m1인 각각의 (a, b) pair에 대하여 m2를 max(m3, b)로 만들 수 있다.

모든 m1에 대하여 m1에 가장 가까운 b를 구하면 되는데 이는 multiset으로 해결할 수 있다.

또한 위의 가정과 달리 a의 값이 중복될 수 있는데 이때는 b가 작은 순으로 정렬하면 된다.

00:36 AC

 

오랜만에 system test에서 터졌다.

반례는 다음과 같다.

2

10 100

10 100

정답은 90인데 내 코드에서는 10이 나온다.

 

초깃값을 잘못 설정한 것이 문제가 되었다.

이러한 데이터가 pretest에 없었다는 점이 신기하다.

하지만 내가 잘 짰으면 애초에 터질 일이 없었다.

결론은 내 잘못이니 다음에 더 잘해야겠다.

 

C - Music Festival

dp로 해결할 수 있다.

우선 필요 없는 값부터 제거하자.

max(A[i][1 .. (j - 1)]) >= A[i][j]를 만족한다면 A[i][j]는 더 이상 고려하지 않아도 된다.

 

현재까지 들은 트랙의 coolness의 최댓값을 maxc라고 하자.

i번 앨범을 듣고난 후 maxc는 max(maxc, A[i].back())로 변화한다.

따라서 A[i].back()이 작은 앨범부터 보면서 업데이트해주면 된다.

 

다음과 같은 점화식을 세울 수 있다.

dp[i] = maxc가 i일 때 impression의 최댓값

현재 트랙의 coolness를 j라고 할 때 max(dp[0 .. (j - 1)])을 구해야 하는데 이는 map으로 해결할 수 있다.

01:06 AC

 

D - The way home

최단 경로 문제이므로 dijkstra로 해결할 수 있다.

우선 정점의 수를 N^2개로 늘려야 하는데 구체적으로는 다음과 같이 정의할 수 있다.

도시 번호는 0부터 시작한다고 가정한다.

u = x * N + y = (x, y) = (도시 번호, 지금까지 방문한 도시 중 w가 가장 큰 도시 번호)

 

비용은 (공연 횟수, 남은 동전의 수)로 정의한다.

공연 횟수가 적고 남은 동전이 많을수록 최단 경로이다.

동전이 부족하다면 y번 도시에서 충분한 수의 공연을 추가적으로 개최하였다고 가정하면 된다.

01:45 TLE

 

dijkstra 구현 시 가장 많이 하는 실수는 pq에 (정점 번호, 거리) 순으로 넣는 것이다.

반드시 (거리, 정점 번호) 순으로 넣어야 한다.

01:52 AC

 

1시간이 남았지만 나머지 문제들은 가망이 없어 보여서 그냥 볼링 치러 갔다.

 

E - Gasoline prices (not solved)

Pass

 

F - Another n-dimensional chocolate bar (not solved)

Pass

 

G - A task for substrings (not solved)

Pass

 

끝

끝