Google Code Jam Qualification Round 후기

A번 : 7점

B번 : 5 + 11점

C번 : 7 + 12점

D번 : 1 + 9 + 16점

E번 : 7 + 25점

 

총 27시간동안 진행됐으며 30점이 넘으면 1 Round 진출

C번의 첫번째 테스트 케이스까지 맞으면 된다.

 

A번

k는 시키는대로 간단하게 더한다.

r과 c는 set으로 원소의 갯수를 새고 그게 N개인지 세면 된다.

(이 문제는 E번과 이어진다.)

T = int(input())

for case in range(1, T + 1):
    N = int(input())
    M = [list(map(int,input().split())) for _ in range(N)]
    
    k = sum(M[i][i] for i in range(N))
    r = sum(len(set(M[i])) != N for i in range(N))
    M = [*zip(*M)]
    c = sum(len(set(M[i])) != N for i in range(N))
    
    print("Case #"+str(case)+":", k, r, c)

 

B번

깊이가 커지면 그 차이만큼만 '('를 추가한다.

깊이가 작아지면 그 차이만큼만 ')'를 추가한다.

처음과 끝은 깊이가 0이다.

T = int(input())

for case in range(1, T + 1):
    ans = ""
    depth = 0
    S = list(map(int, input()))
    for cur in S:
        if cur > depth:
            ans += '(' * (cur - depth)
        elif cur < depth:
            ans += ')' * (depth - cur)
        ans += str(cur)
        depth = cur
    ans += ')' * depth
    print("Case #"+str(case)+":", ans)

 

C번

스케줄 문제라서 강의실 배정이나 회의실 배정과 같은 BOJ 문제들과 유사해 보일 수 있는데

그 문제들은 '최대 갯수를 선택'하는 문제고 이 문제는 무조건 다 선택해야한다. 좀 다르다.

 

먼저 C와 J를 -1로 선언하고

각 구간마다 (시작시간, true, 인덱스), (끝시간, false, 인덱스)를 배열에 넣고 정렬한다.

가장 시간이 빠른 순으로 보면서

true면 인덱스를 C 또는 J에 할당

false면 해당 인덱스가 할당된 C 또는 J를 -1로 초기화 

true인데 둘다 할당상태면 impossible -> 이 경우는 구간 3개가 겹치는 경우다.

조금 비슷하게 해결한 문제는 겹치는 선분 문제

T = int(input())

for case in range(1, T + 1):
    N = int(input())
    LR = []
    ans = [''] * N
    for i in range(N):
        a, b = map(int,input().split())
        LR.append((a, 1, i))
        LR.append((b, 0, i))
    C = J = -1

    LR.sort()

    is_impossible = False

    for x, t, i in LR:
        if t:
            if C < 0:
                C = i
                ans[i] = 'C'
            elif J < 0:
                J = i
                ans[i] = 'J'
            else: is_impossible = True; break
        else:
            if C == i: C = -1
            elif J == i: J = -1
    if is_impossible: ans = "IMPOSSIBLE"
    else: ans = ''.join(ans)

    print("Case #"+str(case) + ":", ans)

 

D번

interactive problem이다. 이 문제 풀이가 꽤 흥미롭다.

 

1. query : P를 print하면 P번째 bit를 알려준다.

2. effects : 하지만 1st, 11th, 21st, 31st... etc. query마다 먼저 전체 bits를 다음 4가지 중에서 하나를 수행한다.

• 보수(complement)
• 역순(reverse)
• 둘다 함
• 둘다 안함

3. 전체 B bits를 파악해서 출력하면 답이다.

 

일단 비트를 채워나갈 때 P번째와 그와 대칭인 (B-P+1)번째 비트를 같이 파악하자.

그럼 10번째에는 앞 5비트와 뒤 5비트를 파악했을것이다.

 

11번째 query를 수행하면 effects가 일어날 것이다. 이때

P번째와 그와 대칭인 (B-P+1)번째 비트가 같은 P를 index1

P번째와 그와 대칭인 (B-P+1)번째 비트가 다른 P를 index2 라고 하자.

대칭으로 (0, 0)일 때 보수는 (1, 1) / 역순은 (0, 0) / 보수+역순은 (1, 1) / 둘다 안하면 (0, 0)이다.

대칭으로 (1, 0)일 때 보수는 (0, 1) / 역순은 (0, 1) / 보수+역순은 (1, 0) / 둘다 안하면 (1, 0)이다.

 

flag1 = (index1의 숫자가 변경된 여부)

flag2 = (index2의 숫자가 변경된 여부) 라고 해보자.

 

	complement	reverse	complement + reverse	nothing happens
flag1	True	False	True	False
flag2	True	True	False	False

 

따라서 flag1, flag2를 파악하면 4가지 effects 중 하나가 결정된다.

 

2번의 query를 effects를 파악하는데 사용하고 8번의 query를 모르는 bit를 파악하는데 사용하면

150번의 query로 100bit까지 파악하는데 충분하다.

T, B = map(int, input().split())
ans = [-1] * B

def get_bit(kth):
    print(kth, flush=True)
    a = int(input())
    return a

def complement():
    global ans, B
    for i in range(B):
        if ans[i] < 0: continue
        ans[i] ^= 1

def reverse():
    global ans
    ans = ans[::-1]

def effects(flag1, flag2):
    if flag1 and flag2: complement()
    elif flag1: complement(); reverse()
    elif flag2: reverse()
    else: pass

for case in range(1, T + 1):
    ans = [-1] * B
    index1 = -1  # same bits
    index2 = -1  # different bits
    cur = 0

    while True:
        query = 4
        flag1 = flag2 = False

        if index1 >= 0 and index2 >= 0:
            a = get_bit(index1 + 1)
            b = get_bit(index2 + 1)
            if a != ans[index1]: flag1 = True
            if b != ans[index2]: flag2 = True
        elif index1 >= 0:
            a = get_bit(index1 + 1)
            _ = get_bit(index1 + 1)
            if a != ans[index1]: flag1 = True
        elif index2 >= 0:
            a = get_bit(index2 + 1)
            _ = get_bit(index2 + 1)
            if a != ans[index2]: flag2 = True
        else:
            query += 1

        effects(flag1, flag2)

        for _ in range(query):
            a = get_bit(cur + 1)
            b = get_bit(B - cur)
            ans[cur] = a
            ans[B - cur - 1] = b
            if a == b: index1 = cur
            if a != b: index2 = cur
            cur += 1

        if cur >= B // 2: break

    print(''.join(map(str, ans)), flush=True)
    ok = input()

    if ok == 'Y':
        continue
    else:
        exit()

 

E번 - fail

(Test case 1) N = 5일 때

채울 수 있는 경우의 수를 다 나열해보자 얼마 안된다.

N = 2 / 3 / 4 / 5일 때마다 잘 채우고 빡구현하면 된다.

 

(Test case 2) N = 50일 때

모르겠다! 맞춘 사람은 총 399명이다.

풀이를 보니 네트워크 플로우를 쓴다고 한다.

 

 

 

참고

구글 코드잼 언어 버전을 잘 확인해야한다.

C++은 C++14고 파이썬은 3.5다.