Google Code jam Round 1B 2019 후기

안녕하세요.

Round 1B 2019 후기 간단히 올려 봅니다. 추가 설명이 필요하시면 답변 부탁드립니다~

Round 2로 진출한 상황이어서 시험 종료 후에 풀어봤습니다.

문제는 세 문제였습니다.

ㅁ 1번 Test Set1 (Manhattan Crepe Cart)
 각각의 사람에 대해서 지나가는 위치를 +1증가 시키면 됩니다. 시간 복잡도는 O(P*Q*Q)이고, P=500, Q=10이라서 
 제한 시간안에 실행이 가능합니다.

ㅁ 1번 Test Set2
 Q=100000이기 때문에 위의 방법으로는 TLE(Time Limit Expire)가 발생하기 때문에 더 좋은 방법이 필요합니다.
 X좌표와 Y좌표를 따로 생각해도 된다는 게 문제의 핵심입니다.
 현재 좌표가 (x1,y1)일 경우, 북쪽 방향은 Y [y1+1].. Y [Q]까지 1을 더하고 남쪽 방향은 Y [y1-1].. Y [0]까지 1을 더하고
 동쪽 방향은 X[x1+1]..X[Q]까지 1을 더하고 서쪽 방향은 X [x1-1].. X [0]까지 1을 더하면 됩니다.(DP로 O(1)으로 연산 가능)
 
 X배열에서 최소인 x좌표(같을 경우 작은값)와 Y배열에서 최소인 y좌표(같을 경우 작은 값)가 답이 됩니다.
 시간 복잡도는 O(Q) 입니다.
  
2번은 제가 어려워 하는 Interactive problem이었습니다.
ㅁ 2번 Test Set1 (Draupnir)
 D0, D1, D2, D3, D4, D5를 질문하면 풀 수 있습니다.
 D1-D0=R1, D2-D1=R2, D3-D2=R3, D4-D3=R4, D5-D4=R5, D0=R6를 구할 수 있습니다.ㅁ

 2번 Test Set2
 Ri 최댓값이 100(7bit)인 점과(property-1), 2^63으로 modular 한다는 점을(property-2) 이용해야 합니다.
 property-1: y = Ri * 2^i + Rj * 2^j 에서 abs(i-j)>=7인 경우 y, i, j값을 이용해서 Ri, Rj를 구할 수 있습니다.
 property-2: y = Ri * 2^i + Rj * 2^j 에서 i>=63일 경우 (Ri * 2^i) % 2^63은 0이 됩니다.
 y = R1*2^x1 + R2*2^x2 + R3*2^x3 + R4*2^x4 + R5*2^x5 + R6*2^x6 일 경우,
 property-2를 통해서 R1*2^x1=R2*2^x2=R3*2^x3=0이고(x1,x2,x3>=63), x4/x5/x6의 차이가 7 이상인 Day를 질문하면
 R4/R5/R6를 구할 수 있습니다. 이런다음에 x1, x2, x3의 차이가 7 이상인 또 다른 Day를 질문하면 R1/R2/R3를 구할 수 있습니다.(R4/R5/R6는 이미 알고 있음)

ㅁ 3번 Test Set1 (Fair Fight)
 모든 L,R(1 ≤ L ≤ R ≤ N)에 대해서 C, D에서 최댓값을 찾은 후에 각각의 최댓값의 차이가 K이하인 경우를 count 하면 된다
 시간 복잡도는 O(N^3)이고 N=100이기 때문에 시간 내에 수행 가능 하다

Round 1C 후기를 기대해 주세요.

Code jam 참여자 여러분, 모두 화이팅 하세요!