GCJ2022 Round1B 문제 개요 & 해법 노트

경기 페이지

https://codingcompetitions.withgoogle.com/codejam/round/000000000087711b

결실

Pancake Deque

https://codingcompetitions.withgoogle.com/codejam/round/000000000087711b/0000000000acd59d

문제 개요

긴 N개의 얇은 부침개 맛열

N 사람마다 하나씩 주는 팬케이크.

전달할 수 있는 얇은 부침개는 deque의 요령으로 열의 왼쪽 또는 열의 오른쪽

만 있다.

i위는 다음과 같은 조건을 만족할 때만 식사비를 지불한다.

i개인에게 줄 얇은 부침개의 맛을 d

로 설정한다.

첫째, 둘째...,첫 번째 사람에게 줄 얇은 전병의 맛은 모두 d 이하

얇은 부침개 순서대로 식비를 지불하는 인원을 최대화

해법

"지금까지 준 팬케이크의 맛 최대치"를 최소화하면
매번 왼쪽과 오른쪽의 얇은 부침개를 골라 맛이 적으면 좋겠다.
예를 들어 N=7 중 각 팬케이크의 맛도1 4 1 4 2 1 3가 있을 때는 아래 순서대로 팬케이크가 줄어든다.
O(N)

1 4 1 4 2 1 3
1 4 1 4 2 1
1 4 1 4 2
  4 1 4 2
  4 1 4
  4 1
    1
    

Controlled Inflation

https://codingcompetitions.withgoogle.com/codejam/round/000000000087711b/0000000000accfdb

문제 개요

N 개인 각 P개 아이템

화물마다 적당한 기압이 있다

우선 공기 압력은 0

버튼을 누르면 공기 압력을 +1,-1

공기 압력이 상품의 압력에 부합되면 해당 상품에 공기를 주입할 수 있다

첫째, 둘째,...,N위 순

각자 P개의 아이템을 들고 공기를 넣는 순서에 공을 들여 버튼을 누르는 횟수를 최소화

해법

i위는 공기를 넣고 싶은 물건을 기압 순서대로 정렬X[i][1], X[i][2], ..., X[i][P]했다.dp[i][j]: i번째 개인 충전 후 충전 압력이 X[i][j](마지막 충전은 j번째 아이템)일 때 버튼을 누르는 최소 횟수
(i,j)로부터의 전환은 (i+1,1),(i+1,2)...(i+1, P) 의 P 채널이 있습니다.
(i,j)→(i+1,k)의 변화에서 공기압력의 변화로서 다음과 같은 두 가지만 고려하면 된다.

X[i][j] → X[i + 1][1] → X[i + 1][P] → X[i + 1][k]

X[i][j] → X[i + 1][P] → X[i + 1][1] → X[i + 1][k]

dp[N][*]의 최소치는 응답이었다.
O(NP^2)
실제로 공식 해설에 따르면 i개인은 공기를 다 마시고 X[i][1] orX[i][P]만 생각하면 되기 때문에 계산량이 O(NP)로 떨어진다.

ASeDatAb

https://codingcompetitions.withgoogle.com/codejam/round/000000000087711b/0000000000acd29b

문제 개요

상호작용 문제

심판은 8비트의 값을 자유롭게 결정하기 시작한다 X

이 값은 비밀로 운동선수의 종목에서 볼 수 없다

한 번의 조회에서도 판정에 8비트의 값 V

를 보낼 수 있다.

다음 절차로 X 대신 popucount(X) 반환

순환 이동이 좋아하는 횟수 V

X

를 (X 또는 V)로 교체

300회 이하 조회 중 X=0(즉popcount(X)=0)

해법

Test Set1 만 풀었습니다.
Test Set1의 제한 사항:

심판은 첫 번째 X

를 무작위로 확정한다.

심판 순환 이동 V(조회마다 독립적으로) 무작위 횟수

X를 0으로 만들려면 popucount(V) = popucount(X)가 필요합니다.
랜덤으로 이런 V를 만들어 심판에게 보내며 총 조회 횟수는 300회 이내로 제한한다.(잘 모름)