0915

오늘은 Atcoder Grand Contest 27에 참가했다.

대회 링크: https://beta.atcoder.jp/contests/agc027

A. Candy Distribution Again

N명이 원하는 숫자 Ai가 주어진다. 그리고 내가 가진 숫자 X가 있고, 이 X를 N명한테 남김없이 나누어줄 때 정확히 Ai만큼 숫자를 가지게 되는 최대 사람 수를 구하는 문제이다. 정렬한 후 제일 작은 것부터 순서대로 주고 마지막에 남아돌 경우 -1 시켜주면 된다. 간단한 문제.

B. Garbage Collector

로봇이 N개의 지점에 주어진 쓰레기를 모두 주워서 버려야 한다. 이 때, 0번째 지점에서 쓰레기를 태우고, 쓰레기를 줍거나 버릴때는 항상 X만큼의 비용을 소모한다. 또, 로봇이 들고 있는 쓰레기의 숫자가 K인 경우 한칸 움직일 때마다 (K+1)^2만큼의 비용을 소모한다. 모든 쓰레기를 주워서 버리기 위해 필요한 최소 비용을 구하는 문제.

서브태스크 400이라도 따려고 했는데 전부 실패했다. 좀 그리디하게 접근했는데 그 풀이에 반례가 있었다. 증명하지 않고 짰기 때문에 WA 뜨면 틀린거겠지 하고 다른 풀이를 생각했으나 끝날 때까지 떠올리지 못했다. 내가 접근한 건 맨 처음 위치 -> 제일 가까운 k번째 까지 갔다가 돌아 옴을 반복하는 형태가 최소일거라고 생각한 거였으나 반례를 찾진 못했는데 반례가 있는 것 같다. 생각해보면 이것보다 다른 방법으로 접근하는게 더 값이 작아질 가능성이 있는 케이스를 떠올릴 수 있긴 하다. 명확한 케이스를 찾진 못했지만..

그래서 다른 방향으로, 총 K번 왔다갔다 하면서 쓰레기를 다 줍는다고 생각하고 접근하면 어떨까? 까지 떠올렸지만 여기서 각 경우에 줍는 서로 다른 방법을 모두 어떻게 검사해야할지가 떠오르지 않아서 결국 풀지 못했다. 에디토리얼을 보니 이 접근이 맞는 것 같고, 그래서 이 접근 방법으로 다시 풀어봐야 할 것 같다.

C. ABland Yard

A혹은 B의 라벨이 붙어 있는 그래프가 주어진다. 이 그래프에서, 임의의 정점에서 시작해서 방문한 정점 순서대로 문자열을 만들 수 있다. 주어진 그래프에서 A,B로 구성된 모든 문자열을 만들 수 있으면 Yes, 아니면 No를 출력하는 문제.

접근이 상당히 막막하게 느껴질 수 있는 문제고 상당히 아이디어성에 속하는 문제이고 재밌는 문제였다. 어떻게 접근할 지가 상당히 막막할 수 있는데, 좀 생각을 해보면 항상 A혹은 B로 가는 선택지가 있는 정점을 거쳐다녀야만 모든 종류의 문자열을 만들 수 있다. 즉, 두 가지 선택지를 모두 지니고 있는게 아닌 정점은 임의의 문자열을 만들 때 포함될 수 없는 정점이다(이러한 정점에서 멈췄을 때, 선택 불가능한 문자를 포함하는 문자열은 만드는게 불가능하므로). 따라서, 각 정점에서 A 정점과 연결된 개수 B 정점과 연결된 개수를 계산하고, 둘 중 하나가 0인 정점 및 그 정점과 연결된 간선은 그래프에서 제거한다. 이걸 계속 반복한 뒤 남아있는 정점 개수가 0보다 크면 이 정점들을 이용해서 모든 문자열을 만들 수 있고, 그게 아니면 불가능하다. 따라서 BFS를 이용한 위상 정렬과 유사한 접근법을 이용해서 O(N+M)의 시간 복잡도로 해결할 수 있다.