Google Code Jam: Round 1A 2020

작년의 코드잼에서는 Round 1A를 놓치고, 1B를 늦게 참여해서 결국 1C에서 779등으로 Round 2 진출에 성공했었다.

올해는 지난 1년간의 발전이 있었던 만큼, 첫 Round 1 대회에서 진출을 기대해보았다.

Round 1A 링크이다.

---

1. Pattern Matching

Question

Wildcard character인 *가 포함된 문자열들이 입력으로 들어온다.

입력으로 들어온 모든 패턴들을 동시에 만족시키는 문자열을 찾아 출력하면 된다.

 

Solution

예제 입력에 주어진 패턴들이 모두 *로 시작하고 알파벳으로 끝나는 형식(e.g. *abc)이길래, asterisk 기준으로 문자열을 분할했을 때 가장 앞과 뒤에 남는 'prefix'와 'suffix'에 우선 집중하기로 했다.

 

Suffix 만 생각해보자. Suffix가 다른 두 패턴이 같은 문자열에 매칭되려면, suffix들이 전부 같은 문자열의 끝부분이어야 한다. 이는 suffix들을 길이순으로 정렬해, 모든 suffix가 제일 긴 suffix의 끝부분에 존재하는 것을 확인하는 것으로 구현 가능하다.

Prefix 또한 마찬가지이다. 대신 모든 prefix가 제일 긴 prefix의 앞부분에 존재함을 확인하면 된다.

패턴을 만족시키는 문자열이 존재한다면, 제일 긴 prefix를 prefix로 가지고, 제일 긴 suffix를 suffix로 가질 것이다.

 

이렇게 패턴을 모두 만족시키는 문자열이 존재하기 위한 prefix와 suffix 조건을 확인하였다. 그렇다면 이제 asterisk 사이에 sandwich되어있는 중간 부분 패턴들을 만족시키기만 하면 된다. 조금 생각해 본다면, 이러한 중간 부분들은 모두 다 asterisk로 둘러쌓여있기에 그들의 좌우에 어떤 문자열이 추가로 붙는지에 대한 관심이 1도 없음을 알 수 있다. 따라서 suffix와 prefix가 아닌 중간부의 문자열들은 그냥 전부 다 concatenate하면 된다. 즉, 모든 패턴의 중간 부분을 전부 다 좌우로 붙이면 된다. 문제에서 제한하는 문자열의 길이가 $10^4$이므로 이는 충분하다.

---

2. Pascal Walk

Question

파스칼의 삼각형이 있다. Pascal walk(파스칼 산책)란, 파스칼 삼각형의 가장 꼭대기에서 출발하는 이동 경로로, 인접한 칸으로만 이동할 수 있으며 같은 칸을 중복해서 방문할 수 없다.

정수 $n$이 입력으로 들어올 때, 거쳐간 칸의 숫자의 총합이 $n$이 되는 Pascal walk를 출력하라. 단, Pascal walk의 칸 수는 500이하여야 한다.

 

Answer

파스칼 삼각형에서 가로줄의 총합은 2의 거듭제곱이 됨에 착안하였다.

모든 자연수는 2의 거듭제곱의 합으로 나타낼 수 있다. 따라서 목표 숫자 $n$을 만들기 위해 2의 거듭제곱들을 적절히 주워담는 생각을 해볼 수 있는데, 문제상황에서 Pascal walk는 연속된 칸들의 합이므로, 떨어져 있는 두 줄을 동시에 선택하기 위해서는 그 사이의 값들도 밟을 수 밖에 없다.

 

그래서 이런 발상을 했다:

 

입력으로 들어오는 $n$값의 최댓값은 10억이므로, log를 취해보면 31번째 줄보다 아래에 있는 줄을 선택할 일은 없음을 알 수 있다.

그래서 31번째 줄부터 1번째 줄까지 올라가며, greedy하게 필요한 가로줄들을 선택한다.

단, 선택되는 첫번째 줄의 경우, 삼각형의 꼭대기로부터 그 줄까지 연결이 되어야 하므로, 삼각형의 좌우 양쪽 끝 1들을 밟으며 그 줄까지 내려와야 한다. 따라서 $k$번째 줄을 선택하고자 한다면 $2^ {(k - 1)} + (k - 1)$의 값이 추가가 된다. 이 값이 $n$보다 작거나 같아지는 줄이 나올때까지 $k$값을 줄여간다.

이 이후로 선택되는 가로줄들의 경우, 이미 그보다 아래에 있는 줄까지 경로를 이어놓은 상황이기 때문에 각각 선택 시 $2^{(k - 1)} - 1$의 값만 추가가 된다. 계속해서 첫번째 줄까지 올라가며 greedy하게 가로줄들을 선택한다.

 

이러한 방식으로 가로줄들과 그 줄들 사이를 잇는 1들을 선택했다면, 총합이 $n$과 같거나 조금 부족할 것이다. 이 조금 부족한 양은 제일 큰 경우에도 30을 넘지 않는다(엄밀하게 증명은 하지 않았지만 대충 확인은 해 보았다). 이 부족한 양은 Pascal walk의 제일 끝에 1들을 필요한 만큼 덧붙이는 것으로 해결이 가능하다.

 

결론적으로, 총합이 $n$이 되기 위해 필요한 가로줄들과, 그 가로줄들 사이를 잇기 위해 밟아야 하는 1의 개수를 모두 고려하여 경로를 짰다. 이제 삼각형의 꼭대기에서 출발을 하여, 좌측 혹은 우측 끝으로 1만 밟으며 내려가다가, 선택된 가로줄이 등장할 때마다 그 가로줄을 타고 반대편 끝으로 건너간 후 계속해서 1만 밟으며 내려가는 것을 반복하면 된다.

---

3. Square Dance

설명하기 귀찮아서 문제는 생략.

구현만 하면 첫 서브태스크를 긁을 수 있고 최적화를 해야 두번째 서브태스크를 통과할 수 있는데, 왠지 내가 모르는 기법을 써야 할 것 같은 예감이 들어서 구현만 하고 제출하였다.

 

끝나고 analysis를 읽어보니 한시간동엔 고민했으면 충분히 풀었을 것 같기도 하다. 괜히 포기했나..?

---

총평

QF 라운드보다 난이도가 훨씬 올라간 것이 체감된다.

현재 랭크가 확정되지는 않았지만, 현재 시각 622등으로 나오는 것을 봐서는 Round 2에 진출할 것 같다.

요즘 할 일이 너무 많아서 스트레스인데, 한번에 통과해서 다행이다.

UPD) 최종 594등으로 통과하였다.

 

다음은 Round 2이다. 작년에는 첫 문제의 첫 서브태스크밖에 못 풀고 광탈했었다...

올해는 꼭 1000등 안에 들도록 하겠다.

Better get that T-shirt ready, Google!