BAPC 2021

문제

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

BAPC 2021

22/05/09 연습

코포GYM에 없기에 BOJ에서 진행하였다.

 

다들 컨디션이 안좋았는지 맞을법한 문제를 많이 억까당했다.

총 12문제.

내가 푼 것  A D I (B, F 왜틀린거지!)

 

A. Arm Coordination

문제

원에 대해 좌표와 반지름이 주어진다. 최소외접사각형의 네 꼭짓점을 구하여라.

 

풀이

최소면적은 정사각형이다. 해당 좌표 기준 x, y에 대해 $\pm$ r하면된다.

 

B. BnPC

문제

현재 스탯이 A일 때, 목표 스탯 B를 찍어야 된다. 모든 스탯에 대해서 최소 B이상 찍어야되며, 딱 B에 맞게 찍으면 0점, 1점이라도 높으면 해당하는 스탯만큼 점수를 획득한다. 얻을 수 있는 최대 점수를 구하라.

 

풀이

상당히 지저분하게 짰다. 근데 틀렸다.

얻을 수 있는 점수 ( = 현재 B인 스탯들 * 그 개수 + 해당 스탯의 가지 수 )가 (가장 많은 스탯의 가지 수) 보다 클 때 까지, 그리고 스탯이 남아있을 때까지 점수를 얻고 남은 스탯으론 (가장 많은 스탯의 가지 수)씩 더해준다.

코너케이스가 죽어라 많이 나왔었고, 결국 틀렸다. :MAD:

 

C. Cangaroo

문제

n x m (n<=100, m<=10)인 그리드 위를 2x2 판으로 가린다. 단, 이 판은 절반 이상이 아래 판 또는 바닥에 받혀져야된다.

 

풀이

한 줄 당 최대 55개정도의 가지수로 판을 배치할 수 있다.

50 * (55 * 55) dp로 구할 수 있는데 구현이 귀찮아서 하지 않았다.

 

D. Decelerating Jump

문제

바닥판에 점수가 주어져있다.

첫 판에서 시작해서 끝 판에 도착하는데 이전에 k칸을 건너뛰어 점프했으면, 그 다음은 k이하로 점프할 수 있다. (즉, 내림차순 거리 점프)

얻을 수 있는 최대 점수를 구하여라

 

풀이

쉬운 n^2 dp이다.

 

E. Evolutionary Excerpt

문제

랜덤하게 AGCT로 이뤄진 두 문자열이 주어진다. (길이 1e6)

최소 1/2n이상의 LCS를 구하라.

 

풀이

아직 생각해보지 않았다.

 

F. Fair Play

문제

사람을 두 명 씩 묶어서 각각 왼쪽값의 합과 오른쪽 값의 합들이 모두 같게 만들 수 있는지 여부 확인

 

풀이

좌 우측값에 대해 (전체 합 / (n/2))을 구하고 map을 사용해서 사람 i에 대해 매칭되는 사람 j가 있는지 확인

 

G. Gyrating Glyphs

문제

interactive한 문제. (a1 op1 a2) op2 a3 .... mod 1e9+7 인 식이 있을 때 a1...an에 대한 값을 넣어보면서,

op1~op(n-1)이 어떤 연산자인지 알아내야한다.

 

풀이

111...000...을 넣어보며 log n에 첫 *를 구할 수 있다.

나머지는.. 잘 모르겠다.

 

H. Hamiltooonian Hike

문제

그래프가 주어지고, 최대 3개의 노드를 건너뛰어 움직일 수 있다. hamiltonian하게 이동할 수 있는지 구하여라.

 

풀이

트리처럼 생각하면 될 것 같았다. 리프까지 갔다가 돌아오는게 가능하며 형제 노드 가는게 가능하기 때문.

구체적이지는 않다.

 

I. Implementation Irregularities

문제

풀이에 사용되는 시간 A, 내가 푼 시각 B가 주어진다. 이에 맞게 풀기 위해서는 최소 몇 개의 컴퓨터가 필요한가?

 

풀이

사용되는 컴퓨터의 개수가 M일 때 모든 문제에 대해 푼 시각 오름차순으로 정렬했을 때 A 누적값 < B * M이면 된다.

이 M은 파라메트릭 서치로 구해진다.

 

J. Jail or Joyride

문제

경찰과 소년범이 있다. 경찰은 소년을 쫓아가는 최단 경로로 지나가고, 소년은 경찰을 피해 최대한 먼 곳에 가는것을 반복한다. 단, 경찰이 바로 직전에 지나간 간선은 소년이 지나갈 수 없다. 소년이 경찰에게 잡히면 끝

 

풀이

제대로 생각해보지 않았다.

 

K. Kinking Cables

문제

n x m 필드가 주어지고 정확이 길이가 L인 케이블을 팽팽하게 연결하려고 한다. 물론 길이가 길 수 있으므로 핀을 몇개 박아서 선을 꼬는데 이때 꼬인 선끼리 교차하면 안되며, 핀 간 거리는 최소 1이다.

 

풀이

최대한 좌우로 선을 연결해두고

(x,y)에서 (n,m)으로 한 점을 거쳐 연결하는 점들을 만든다.

 

L. Lopsided Lineup

문제

a, b사람이 팀을 이뤘을 때 얻을 수 있는 점수판이 주어진다. 사람들을 잘 배분해서 두 팀으로 나눴을 때 얻을 수 있는 팀 간 점수차의 최대값을 구하자.

 

풀이

식을 잘 정리하면 가로줄(혹은 세로줄)의 최대값을 구하는 것이다.