GCPC 2020

문제

https://www.acmicpc.net/category/detail/2427

GCPC 2020

22/05/24 연습

총 13문제로 많은 편이다.

24일 뭔가 할거리가 많아서 연습 중에도 왔다갔다 + 과제도 했는데 집중하지 못했던 것 같아서 같이 연습하던 팀원들에게 많이 미안하다..

 

A. Adolescent Architecture

문제

순식간에 풀려서 무슨 문제인이 알지 못했다.

 

B. Bookshelf Building

문제

책장에 책을 넣게 된다. 가로 선반 하나를 추가하여 모든 책을 넣어야 하는데, 책을 돌리거나 책 위에 책을 쌓을수는 없다.

선반을 쓸 필요가 없다면 -1, 써야한다면 선반 높이, 넣는게 불가능하다면 impossible을 출력하라

 

풀이

max_h를 구한 후 선반 높이를 max_h로 가정하고 H-max_h보다 큰 모든 책을 아래칸에 넣는다.

넣어진 책들의 가로 길이가 sum_w라면 (W-sum_w)와 W 두개의 너비칸에 남은 책의 너비를 모두 넣을 수 있어야 한다.

W-sum_w에 최대한 많은 책을 넣었을 때 남은 책들 너비 합이 W를 넘지 않으면 max_h를 출력한다.

만약 모든 책의 너비 합이 W보다 작거나 같으면 -1, 위의 계산 과정 중에 불가능한 경우가 있다면 impossible을 출력하면 된다.

 

C. Confined Catching

문제

interaction문제이다.

작년 UCPC에 나왔던 문제와 비슷한데 차이점은 사방면에 벽이 있다는것과, 점이 멈출 수 있다는 것이다.

경찰이 도둑을 잡을 수 있게 이동시키면 된다.

 

풀이

두 경찰(?)을 (1,1)로 이동시킨 후, 다음의 과정을 반복한다.

도둑(?)과 경찰 간 w / h차이 중 큰 쪽을 줄이는 방향으로 진행한다.

단, w차이=h차이인 경우 한 경찰은 horizontal, 한 경찰은 vertical하게 이동하게 한다.

 

D. Decorative Dominoes

문제

인접한 서로다른 도미노에 대해 해당 칸들의 값이 같은 경우 쌍으로 연결할 수 있다.

연결이 가능하다면 연결된 쌍의 도미노 번호들을 출력하고 불가능하다면 impossible을 출력하라.

 

풀이

도미노의 눈 개수는 fake다. 모두 눈 개수가 같다고 가정하고 풀 수 있다.

이분매칭을 사용하고, outlier가 생기면 impossible을 출력한다. 매칭되면 쌍들을 출력한다.

 

E. Exhausting Errands

문제

좌우로 왔다갔다 하면서 택배를 배송한다. 택배 출발지를 지나면서 택배를 들고 도착지를 지나면서 택배를 내려놓는다.

최소한의 이동 거리를 출력하라

 

풀이

아직 생각해보지 못했다.

 

F. Flip Flow

문제

누군가 아주 빠르게 풀어서 어떤 문제인지 모른다 ㅠ

 

G. Gravity Grid

문제

입체 4목과 비슷한데 k목 게임이다.

 

풀이

Horizontal, Vertical, Diagonal (두가지 방향) 총 4가지에 대해서 union find를 사용해서 연속된 같은색 점 개수가 k이상이면 바로 멈추고 누구의 승리인지 출력해준다.

(현재 맞왜틀중)

 

H. Hectic Harbour

문제

양 끝에서 두개의 기계가 작동한다.

매 턴 마다 각 기계들은 좌 우로 한칸 움직이거나 해당 자리에서 가만있거나 해당 자리에서 일을 할 수 있다.

기계는 서로 교차할 수 없다.

모든 일이 끝날 때까지 걸리는 최소 시간(턴 수)를 구하라

 

풀이

스케쥴링 문제인 것 같은데 잘 모르겠다.

 

 

I. Impressive Integers

문제

주어진 N에 대해서 한 변 길이 A인 정삼각형 x개, 한 변 길이 B인 정삼각형 N-x개를 사용하여 한 변 길이 C인 정삼각형을 만들 수 있다면 A, B삼각형들을 plot하고, 불가능하다면 impossible 출력

 

풀이

삼각형 하나는 4^alpha로 분리될 수 있다.

4^k개의 삼각형 A와 N-4^k개의 삼각형 B에 대해서 (0<=k<log_4 {k})

삼각형 B의 개수가 홀수개(2n+1개)인 경우가 존재하면 삼각형을 구성할 수 있다.

삼각형 A의 한 변 길이는 n, B의 한변 길이는 2^k로 두고 아래와 같이 배치하면 된다.

J. Jeopardised Journey

문제

기하+BCC

점들에 대해 중간에 장애물(산)이 없는 경우 두 점은 연결될 수 있다.

늑대는 가장 마지막 번호 점에 있다. 해당점이 포함되지 않는 BCC의 개수를 출력하라.

 

풀이

구하면 된다. ㅠㅠ

 

K. Knightly Knowledge

문제

기념비와 교회가 있다.

기념비가 horizontal or vertical하게 같은 줄에 존재하면 해당 줄(직선)은 ley line이 되고 ley line 위의 church는 mighty church가 된다.

단 하나의 기념비를 더 설치하여 최대한 많은 normal church가 mighty church가 되도록 할 때, 바뀐 church의 수와 기념비의 위치를 출력하라

 

풀이

map 등을 사용해서 각 기념비의 x, y축마다 기념비 개수를 업데이트해둔다.

church를 받을 때마다 x, y축 중 하나의 기념비 개수가 2이상이면 넘어가고 그렇지 않다면 기념비 개수가 1개인 곳에 축별로 개수를 업데이트해둔다.

((x축에 변경가능한 교회 수) + (y축에 변경가능한 교회 수) - ((x,y)에 위치한 교회 수)) 중 가장 큰 값을 출력한다.

 

L. Lexicographical Lecturing

문제

길이가 같은 문자열들이 사전식으로 주어진다.

부분 구간에서도 똑같이 사전식으로 배열했을 때 배열 순서가 같은 최소 구간을 찾아라

 

풀이

투포인터로 어떻게든 구할 수 있겠다 했는데 아직 확실하지 않은 것 같다.

 

M. Mixtape Management

문제

Linux에서 숫자이름파일을 정렬할 때 (값 > 길이) 우선순위로 정렬한다.

Windows에서 숫자이름파일을 정렬하 때 (길이 > 값) 우선순위로 정렬한다.

Linux에서 오름차순 정렬된 파일을 Windows로 보냈을 때 기존 위치가 주어지면 각 파일의 이름(번호)를 구하여라.

 

풀이

배열 s에 값을 받았다고 가정하자.

s[i]길이만큼의 문자열을 출력할 건데,

i = 1일 때, s[1]길이만큼 1을 출력한다.

 

s[i-1] < s[i]라면 i-1에서 출력한 문자열에 남은 길이만큼 1을 붙인다.

그렇지 않다면 s[i]길이만큼 i-1에서 출력한 값을 가져오고, 마지막 자리값을 1 늘려준다.