준연구소

안녕하세요.

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 참여자 여러분, 모두 화이팅 하세요!

안녕하세요.

Round 1A 2019 후기 간단히 올려 봅니다.

추가 설명이 필요하시면 답변 부탁드립니다~

문제는 세 문제였고, 2번은 Interactive problem이었습니다.

1번은 Test Set 1은 완전 탐색으로 풀었는데, Test Set 2는 constructive method를 못 찾아서 틀렸습니다.

2번은 저한테는 익숙하지 않은 Interactive problem이라서 3번부터 풀었는데.. 2번은 1시 30분 동안 WA(Wrong Anser) / TLE(Time Limit Expire)만 받다가 못 풀었습니다^^;;

3번은 string처리 / TRIE로 풀었습니다. (Test Set 1 / 2)

Round 2로 진출했고, Round 2 기출 문제를 열심히 풀어볼 계획입니다.

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