ICPC 2020 Asia Yokohama Regional

코포에 없어서 https://qoj.ac/contest/791 여기에서 했다.

8솔 중위권 낫 배드

 

A. Three-Axis Views (G5)

 

열자마자 보인 문제.

주어진 입력을 적당히 yz, zx, xy라고 하자.

만일 xy[i][j] = 0이라면, 전체 구조에서 xy[i][j][k]인 모든 지점들에 블록이 없어야 한다.

마찬가지로 zx[i][j] = 0, yz[i][j] = 0에 대해서 없어야 함을 표시해주자.

이제 xy[i][j] = 1이라면, 전체 구조 xy[i][j][k] 중에서 블록이 있을 수 있는 지점이 있어야 한다.

마찬가지로 zx[i][j] = 1, yz[i][j] = 1에 대해서 있을 수 있는지 확인해보면 된다.

있어야 하는 지점에 있을 수 없다면 불가능하다.

 

입력을 처음에 대충 xy, yz, zx 받았는데 알고보니 좀 제대로 받아야 해서 시간이 걸렸다.

 

B. Secretes of Legendary Treasure (G3)

 

처음의 접근은 다음과 같다.

빈칸이 아닌 숫자들을 우선 정렬해두자.

예를 들어, 예제#2를 (3, b[3]), (5, a[2]), (8, b[5]), (12, b[7]), (13, a[6])라고 할 수 있다.

이후에 저 순서대로 그 앞에 숫자들을 앞에서부터 채워두는 것이다.

예를 들어 맨 처음에 b[1], b[2]를 채우고, 이후 a[1], 그 후 b[4], ... 의 순서대로 채우는 것이다.

 

이럴 때 반례가 생길 수 있음을 발견하는데 꽤 오래걸렸다.

어떤 반례가 있냐면 (2, b[1]), (4, b[3]), (7, a[4]),...이런식으로 있다면, b[2]에 1을 넣어버린다.

따라서 저 순서대로 넣되, 이전의 숫자들 보다 무조건 크도록만 해주면 된다.

 

E. Jewelry Size (P2)

 

내각의 합이 360도가 되도록 이분탐색만 해주면 된다.

단, 하나의 변이 매우 길어서 하나가 둔각삼각형처럼 되는 경우도 고려해주면 된다.

 

J. Formica Sokobanica (G1)

 

돌을 밀어내면 되는 문제

DFS로 처리해주면 된다.

rock[i]를 i번 지점에 rock이 있는지 없는지를 의미하는지 생각하자.

1) rock[i] = 0이라면 당연히 이 지점에 도달하는 것이 가능하다. (단, 도달 가능한 경우에만)

2) rock[i] = 1이지만, 인접한 점들 중 parent를 제외하고 rock[j] = 0인 j가 존재하면 i에 도달이 가능하다.

 

이때 따로 처리해야하는 지점이 있다.

만일 rock[i] = 1인데 비어있는 j가 오직 하나만 존재한다면 반드시 j로 rock을 밀어내야 한다.

따라서 dfs로 j에 들어갈 때 rock[j] = 1 처리를 해주어야 한다.

 

G. To be Connected, or not to be, that is the Question (P1)

 

왼쪽과 오른쪽에 있는 component들을 생각해보자.

이때 각 component간에는 간선이 반드시 존재하므로, 양쪽에는 좌우를 이어주는 component - 1개의 점이 있다.

즉, 항상 반대쪽에 component - 1개의 노드가 존재하여야 한다.

N >= (component 개수) - 1 + max(Left, Right)가 성립하는 최소의 숫자를 구하면 된다.

 

component 개수는 왼쪽과 오른쪽을 따로 구해서 더해주면 된다.

한쪽의 component를 모든 숫자에 대해서 구하는 과정은 정렬해두고 순서대로 진행하면 된다.

DSU를 숫자가 작은 노드들부터 시작하여 merge를 하면 component의 개수를 모두 구할 수 있다.

 

K. Suffixes may Contain Prefixes (D3)

 

처음에는 무조건 답이 적당한 구간이 반복되는 것으로 생각했다.

예를들어 ababc의 경우에는 ab/ab/ab 처럼 ab가 반복되는 식으로 나타나게 된다.

하지만 aabaacaabaa의 경우에는 aabaac/ ... /aabaac/aabaa/a가 답이 되는 식으로 마지막에 변화가 생긴다.

이것도 또다시 여러 가정을 내릴 수 있지만, 너무 비효율적이라서 폐기했다.

 

'a'를 더하는게 그냥 'c'를 더하는 것보다 이득인 것을 확인했고, dp를 떠올리게 되었다.

dp는 그냥 dp[i][j] : (bullet의 i번자리까지 왔을 때 target의 j번자리까지 적혀있을 때의 최댓값)이라 정의하면 된다.

예를 들어 예제 2에서 dp[3][3]은 무조건 'aab'이고 4가 되는 것이다.

그렇다면 dp[i][j] 뒤에 그대로 j + 1번째 자리가 오면 fail[j] - 1, fail[fail[j] - 1]] - 1, ...의 개수의 총합 만큼 dp값에 더해진다.

만일 오지 않는다면 dp[i][fail[j - 1]]에서 또 처리를 시작해주면 된다.

 

H. LCM of GCDs (D5)

 

struct를 이용한 segtree.

각 구간에 대해 K = 0, 1, 2에 대한 값을 zero, one, two라 하자.

c.zero = gcd(a.zero, b.zero); 

c.one = lcm(gcd(a.zero, b.one), gcd(b.zero, a.one)); 

c.two = lcm(gcd(a.one, b.one), lcm(gcd(a.zero, b.two), gcd(a.two, b.zero)));

를 이용하여 양쪽 구간을 합칠 수 있다.

 

I. High-Tect Detective (D4)

 

우선 in과 out이 모두 기록된 것은 어차피 모두 결정났으니 지워버렸다고 가정하자.

그 다음 I 0은 free-in, I 1과 같이 숫자가 있는 것은 name-in이라고 하자.

그렇다면, O 0는 free-in과 name-in에 모두 대응이 가능하지만, O 1은 free-in에만 대응이 가능하다.

 

dp[i][x] = (i번 자리까지 대응시켰고, 현재 남은 name-in의 개수가 x개)라고 하자. 

그렇다면, i번 자리까지의 free-in + name-in의 개수가 정해져 있으므로 free-in의 개수도 tot - x개로 결정이 난다.

만일 O 1을 만난다면 free-in과 대응되므로 dp[i + 1][x] += dp[i][x] * (tot - x)를 해주면 되고,

만일 O 0을 만난다면 dp[i + 1][x] += dp[i][x] * (tot - x)과 함께 dp[i + 1][x - 1] += dp[i][x] * x를 해주면 된다.

현재 I 0, O 0 들끼리 대응되었을 때 어떤 숫자가 대응되는지 고려를 안했으니 마지막에 개수를 세서 P!을 곱해준다.

 

ㅡㅡㅡㅡㅡㅡㅡ

C, D 풀이는 대충 이해했는데 구현은 하기 싫다.

F는 그냥 싫다.

 

C. Short Coding (P3)

 

버추얼 중에는 이걸 사람이 어떻게 품?이라는 생각을 했다.

물론 나머지 문제 중에서는 이 문제가 제일 많이 풀리기는 했다. 

그런데 P3? 말이 안되네

 

진짜 말도 안되는 관찰이 하나 숨어있다.

미로를 무조건 푸는 아주 유명한 방식에 왼손을 벽에 대고 하염없이 앞으로 가는 것이 있다.

즉, LEFT - IFOPEN5 - RIGHT - GOTO2 - FORWARD라는 해결법이 존재한다.

따라서 답은 항상 5 이하이다.

사실 미로 문제에서 위의 방법은 아주 유명한 풀이라서 생각해낼 법도 했다.

 

그러면 4줄 이하의 프로그램에서 각 줄당 올 수 있는 command의 종류가 11종. 

따라서 11^4종의 프로그램에 대해서 모두 simulation 돌려보면 된다.

state의 종류는 [N][M][DIR][LINE]으로 N, M이 매우 작기에 1600종이 끝

 

D. Colorful Rectangle (D1)

 

답이 되는 rectangle은 다음 두 종류 중 하나이다.

1) 두 색이 각각의 꼭짓점에 존재한다.

2) 세 색이 모두 어떤 변 위에 존재하고, 하나는 꼭짓점에 존재한다.

이는 꽤나 직관적이고 얻기 쉬운 관찰이다.

 

1) 중에서 perimeter가 가장 작은 값을 구하려면...

count[x][y] = ((x, y)보다 왼쪽 아래에 존재하는 초록색 점의 개수)라고 하자.

WLOG count[rx][ry] < count[bx][by]이고 (rx <= bx, ry <= by)인 빨간점과 파란점을 찾으면 된다.

파란 점의 기준에서 보았을 때 위의 조건을 만족시키는 rx + ry가 제일 큰 빨간점을 구하면 된다.

count로 정렬해두고 무식하게는 이차원 세그로 해도 되고 x값이 작은 것부터 스위핑을 해도 된다.

 

2) 중에서 perimeter가 가장 작은 값을 구하려면...

WLOG 걸고 제일 왼쪽 아래에 빨간 점, 윗변에 파란 점, 오른변에 초록점이 있다고 생각하자.

일단 x값으로 모두 정렬.

y값과 관련된 세그트리를 관리해주는데, 값이 s라고 한다면

a) red.y <= s인 빨간점들에 대해 -r.x -r.y의 최솟값

b) blue.y >= s인 푸른 점들에 대해 b.y의 최솟값

c) red.x <= blue.x, red.y <= s <= blue.y인 쌍에 대해 blue.y - red.y + -red.x의 최솟값

a, b는 그냥 각각 빨간점, 파란 점이 들어갈 때 lazy하게 처리해주면 그만.

x값으로 정렬해 두었기에 파란 점을 삽입할 때 c 또한 어렵지 않게 처리할 수 있다.

 

F. Solar Car (Not rated)

 

이 문제가 대회 당시에는 제일 할만한 문제라고 생각했었다.

근데 아님