준연구소

안녕하세요. 

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

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

문제는 세 문제였습니다. 

ㅁ 1번 (Robot Programming Strategy)

Greedy로 Test set 1 / 2 모두 해결 가능합니다.

나는 나를를 제외한 모든 Robot을 이겨야 합니다. (이유: 첫번째 tournament에서 나는 모든 Robot과 겨룰수 있으므로)

현재 위치를 p라고 합시다. (0부터 시작, 예를들어 Robot 1이 "RSP"이고 p=1이면 'S'를 나타냄. p=5이면 5%3(3=len("RSP") = 2이기 때문에 'P'를 나타냄)

p위치의 나를 제외한 모든 robot의 값은 다음과 같은 경우로 나뉩니다.

1) 하나의 값만 존재. 예를들어 모든 robot의 값이 'P'인 경우 나는 'S'를 내면 이깁니다. 즉, 내가 이기는 경우는 항상 있기때문에 내가 이기게 되고 현재까지의 값을 출력해 주면 됩니다.

2) 두개의 값이 존재. 예를들어 모든 robot의 값이 'R','P'인 경우 나는 'P'를 내면 되고 'R'인 robot은 지기 때문에 제외 하고 계속 진행하면 됩니다. 즉, 두개의 값중에서 이기는 경우를 나는 내면 되고, 지는 Robot을 제외한 채로 계속 진행하면 됩니다.

3) 세개의 값이 존재. 예를들어 모든 robot의 값이 'R','P','S'인 경우 나는 어떤값을 내더라도 나를 이기는 robot은 존재하기 때문에 나는 지게 됩니다. 즉, IMPOSSIBLE을 출력하면 됩니다.

Robot중에서 string길이가 가장 긴 길이만큼 실행해도 이기는 경우가 없을 경우 IMPOSSIBLE을 출력하면 됩니다.

ㅁ 2번 (Power Arrangers)

Interactive Problem입니다.

총 5개의 문자(A,B,C,D,E) 이고 5개의 문자를 나열하는 모든 경우중에 빠진 1가지만 찾는 문제입니다.

5개의 문자를 나열하는 경우의 수는 5!=120이고 1가지가 빠졌기 때문에 119가지가 존재합니다.

119*5개문자 = 595이기 때문에 문제에서 허용하는 F (475 / 150) 이내에 답을 찾을수 없다.

문제의 핵심은 첫번째 빠진 문자를 찾은후 두번째 문자를 찾을때에는 첫번째 문자중에 빠지지 않은 경우는 제외하면 search횟수를 많이 줄일수 있다. 예를들어서, 정답이 ABCDE인 경우 첫번째 119개 string중에 첫번째 문자의 갯수는 A=23, B~E=24가 된다. 두번째 문자 B를 찾을 경우 첫번째 문자가 B~E인 string은 제외 시키면 search횟수를 많이 줄일수 있다. 이런 방식을 할 경우 search 횟수는 첫번째 문자는 119번(5!-1), 두번째 문자는 23번(4!-1), 세번째 문자는 5번(3!-1), 네번째 문자는 1번(2!-1), 다섯번째 문자는 0번(네개의 문자를 알면 마지막 문자는 알수있음). 총 148번에 해결가능하기 때문에 Test Set 1 / 2 모두 해결가능하다

ㅁ 3번 Test Set 1 (Bacterial Tactics)

winning opening moves의 갯수를 구하는 문제입니다. 즉, Becca 가 이기는 첫번째 moves의 갯수를 구하면 됩니다.

전체 탐색으로 풀었습니다. 모든 opening move(2*(R+C)) 에 대해서 Becca가 이기는지 확인해 봅니다.

Becca가 이기는지 확인하는 방법도 전체 탐색으로 진행합니다. 즉, 현재 empty인 공간에 Bacteria를 설치합니다.(Horizontal / Vertical) 현재 선택 가능한 방법의 수는 (R+C) * 2 (2: Horizontal + Vertical)가 됩니다.

따라서, 시간복잡도는 O(2*(R+C) * (2*(R+C))!) = O(16*16!) 입니다. big O 시간 복잡도는 크지만 실제 시간복잡도는 크지 않은것 같습니다. (한번 play할때 선택되는 cell이 많고, radioactive material가 있어서 경우의 수가 줄어드는것 같습니다)

부족한글 읽어 주셔서 감사드립니다.

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

안녕하세요.

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