Codeforces Round 857 (Div. 1)
Dashboard - Codeforces Round 857 (Div. 1) - Codeforces
codeforces.com
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
끝
끝