Google Code Jam 2020 Qualification Round Solution
안녕하십니까. 구글 코드잼 예선이 끝났습니다.
예선 문제에 대하여 맞은것은 한번더 점검하고 틀린것은 왜 틀린건지 알아보기 위하여 리뷰 합니다.
위의 행렬을 보면 대각선의 값은 1,1,1,1로 trace = 4. 모든 행렬이 1,2,3,4가 고루 분포되어 있습니다. 따라서 4 0 0을 리턴합니다.
스케줄링하면 다음과 같으며 출력값은 주어진 순서에 맞춰야 하기 때문에 JCCJJ가 됩니다.
예선 문제에 대하여 맞은것은 한번더 점검하고 틀린것은 왜 틀린건지 알아보기 위하여 리뷰 합니다.
등수
맨 마지막 문제의 large 데이터를 틀려서 588 등을 하였습니다.
안타깝긴 합니다.
대다수의 사람이 30점만 넘기고 그만했으리라 생각하면 실제 라운드에서는 등수가 더 낮지 않을까 생각 합니다.
Vestigium
아래와 같은 N-by-N 행렬에 대하여 모든 행, 렬을 기준으로 반복되지 않는 숫자로 이루어진 행렬을 "Latin Square"이라고 합니다. 여기서 Mi,i로 나타낼 수 있는 대각선의 원소들의 합을 "trace"라고 합니다. 주어진 문제에서는 trace와 행, 렬을 기준으로 반복된 숫자가 있는 행, 렬의 갯수를 리턴하면 됩니다.
1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1 |
2 2 2 2 2 3 2 3 2 2 2 3 2 2 2 2
위의 행렬을 보면 대각선은 2,3,2,2로 trace = 9. 4개의 행 4개의 열 모두가 2,3으로만 반복되고 있습니다. 따라서 9 4 4를 리턴 합니다.
풀이
대각 합을 구하는 for문 하나, 행, 렬의 반복 유무를 구하는 for문 두개를 통하여 간단하게 풀 수 있는 문제 입니다.Nesting Depth
간단한 괄호 문제 입니다.
숫자의 배열이 있을때 숫자가 커질수록 괄호를 통하여 여닫는 문제 입니다. 0은 괄호를 가지지 않습니다. 각 숫자는 숫자의 크기 만큼 괄호로 감싸져야 합니다.
예제는 다음과 같습니다.
111000 → (111)000
21012 →((2)1)0(1(2))
21012 →((2)1)0(1(2))
풀이
string을 iteration 하면서 현재의 숫자가 이전의 숫자보다 클시에는 괄호를 하나 생성,작아지면 반대로 괄호를 닫으면 되는 문제입니다.Parenting Partnering Returns
C,J의 이니셜을 가지는 부부가 있고 집안일을 서로 스케줄링 해야한다고 합니다. 각 일에 대하여 시작 시간과 끝 시간이 주어지고 한사람이 하는 일이 겹치지 않게 스케줄링 하면 됩니다. 두일을 연달아 할때 두 일의 끝시간과 시작시간은 겹쳐도 됩니다. 또한 출력 값은 처음 입력받은 업무의 순서대로 각 업무를 누가 할지 결정을 하면 됩니다. 스케줄링은 여러 방식이 있을텐데 맞기만 하면 어떤 출력값이라도 맞다고 해줍니다.
예를 들어서 아래와 같은 일에 대하여는 한사람이 두개 다 하든 둘이 번갈아 하든 어떻게 하든 겹치지 않습니다. 저는 단순히 CC라고 출력하였습니다.
0 720 720 1440
다음과 같은 예시를 간단하게 그리면 다음과 같습니다.
99 150 1 100 100 301 2 5 150 250겹치는 부분들은 한사람이 동시에 할 수 없기 때문에 서로 번갈아서 일을 진행해야 합니다.
스케줄링하면 다음과 같으며 출력값은 주어진 순서에 맞춰야 하기 때문에 JCCJJ가 됩니다.
풀이
C,J의 시간에 따른 일을 지닌 배열을 2개 생성하고 각각의 일에 대하여 C가 일이 겹치지 않으면 C에게 일을 주고 일이 겹치면 J에게 할당하는 방식으로 풀었습니다.
ESAb ATAd
일반적인 알고리즘 문제는 고정된 입력에 대하여는 고정된 출력을 리턴 합니다. 그렇기 때문에 문제 창에 코드를 제출하면 테스트를 진행 할 수 있습니다. 하지만 이 문제는 일반적인 문제가 아닙니다. 우리나라의 스무고개 처럼 몇번 질의 응답을 하면서 1,11,21,31... 의 질의 이후에는 랜덤한 요소를 통해서 문제의 답이 변형이 생기기 때문에 일반적인 입출력으로는 테스트를 할수가 없습니다. 따라서 구글에서 제공하는 파이썬 프로그램을 통해서 테스트를 해야합니다. 예시 테스트 프로그램이 파이썬밖으로만 제공되기 때문에 직접 번거롭게 변환하지 않는 이상 파이썬으로 풀이를 해야합니다.
0001101111과 같은 bit 수가 있을때 각 질의에서 특정 자리수를 물어보면 프로그램은 해당 자리수의 숫자를 출력해 줍니다. 간단하게 생각해보면 모든 자리수만큼 물어보면 답을 알 수 있습니다. 하지만 주어진 문제에서는 1,11,21,31의 질의때마다 1/4의 확률로 다음 연산이 일어 납니다.
- 0이 1이되고 1이 0이되는 flip
- 숫자가 앞뒤로 변경
- 두개가 다 발생
- 아무것도 일어나지 않음
풀이
이문제는 풀이 보다도 Interactive Problem을 어떻게 테스트 하는지 자체를 이해하는게 가장 큰 어려움입니다. 다른 여러 코딩 대회중에서 이러한 방식은 여기에서 처음보는듯 합니다. 문제 링크에 보시면 Download local testing tool와 Interactive Problems section 부분에 있는 interactive_runner script라의 코드를 통해서 내가 짤 코드와 예제 테스팅 코드가 runner 스크립트를 통해서 서로 상호작용 할 수 있도록 파이썬 코드를 작동 시켜야 합니다.
test 1만 푼다고 하면 매우 쉽습니다. 문제 사이즈는 1-11의 간격도 10이기 때문에 처음 입력값은 버리고 이후 10개의 입력을 그대로 리턴하면 풀립니다.
이후 큰 사이즈의 문제를 풀기 위해서는 각 10번의 턴 동안마다 새롭게 하나를 받아온 후 이 연산 후에 4가지 경우중 어떤 케이스가 걸렸는지를 직접 검사해야 합니다. 숫자가 앞뒤로 바뀌는 2번의 케이스가 있기 때문에 10번의 턴 동안마다 맨앞 부터 5개, 맨뒤부터 5개 씩 받아오면 쉽게 풀 수 있습니다.
10번째 이전에서 가져온 데이터들 중에서 앞에서 i번째, 뒤에서 i번째가
test 1만 푼다고 하면 매우 쉽습니다. 문제 사이즈는 1-11의 간격도 10이기 때문에 처음 입력값은 버리고 이후 10개의 입력을 그대로 리턴하면 풀립니다.
이후 큰 사이즈의 문제를 풀기 위해서는 각 10번의 턴 동안마다 새롭게 하나를 받아온 후 이 연산 후에 4가지 경우중 어떤 케이스가 걸렸는지를 직접 검사해야 합니다. 숫자가 앞뒤로 바뀌는 2번의 케이스가 있기 때문에 10번의 턴 동안마다 맨앞 부터 5개, 맨뒤부터 5개 씩 받아오면 쉽게 풀 수 있습니다.
10번째 이전에서 가져온 데이터들 중에서 앞에서 i번째, 뒤에서 i번째가
- 서로 같은 경우, 이 데이터는 바뀐 후에 flip이 되었는지 확인이 가능합니다. 서로 같기 때문에 자리가 바뀌어도 바뀌는건 없기 때문입니다.
- 서로 다른 경우, 이 데이터는 자리의 위치가 변경되었는지 확인이 가능합니다. 이도 위와 동일하게 생각하시면 됩니다.
위 두가지 경우에 대하여 각각 케이스가 걸리면 해당 연산을 모든 데이터에 진행하면 됩니다.
Indicium
이 문제는 1번 문제의 변형 입니다. 행렬의 크기 n과 trace의 값 k가 주어졌을때 해당 조건을 만족할 수 있는 Latin Square를 구하고 불가능하면 불가능하다고 출력하는 것 입니다.
예를 들어 3 6의 인풋이 있을 경우 아래의 두 케이스는 trace = 6을 만족하며 모든 행, 렬이 중복되지 않습니다.
2 1 3 3 1 2
3 2 1 1 2 3
1 3 2 2 3 1
저는 해당 문제에 대하여 모든 경우를 구하는 코드를 작성하였고 그 결과 1번은 맞았지만 Large 케이스에서는 당연히 틀렸습니다. 해당 솔루션은 아직 보지 않았으므로 추후에 여기부터 다시 작성..
예를 들어 3 6의 인풋이 있을 경우 아래의 두 케이스는 trace = 6을 만족하며 모든 행, 렬이 중복되지 않습니다.
2 1 3 3 1 2
3 2 1 1 2 3
1 3 2 2 3 1
저는 해당 문제에 대하여 모든 경우를 구하는 코드를 작성하였고 그 결과 1번은 맞았지만 Large 케이스에서는 당연히 틀렸습니다. 해당 솔루션은 아직 보지 않았으므로 추후에 여기부터 다시 작성..
댓글
댓글 쓰기