IPSC 2018 후기

디스크립션에 이상한 대칭키 암호같은 설명이 나와서 당황스러웠다. 심지어 예제가 틀려 있어서, 문제를 잘못 이해한 줄 알고 그냥 넘겼다.

나무(그래프 트리가 아니고 진짜 나무다)들이 주어지는데, 이 나무들을 손으로 직접 교배시켜서 원하는 나무를 만들어야 한다.

교배시켜도 어떻게 되는지 딱히 설명이 없어서 대충 easy를 잡고 아무렇게나 했는데 OK가 나왔고, hard를 봤는데 나무가 너무 많길래 던졌다.

F1 0:24 OK.

git 주소가 주어지는데, 이 때 파일 트리의 checksum을 알아내야 한다.

아무 생각 없이 git clone을 했더니 컴퓨터 용량이 다 차서 실패했다… 뭐 이런 문제가 있나 하면서 팀원들에게 넘겼다. 나중에 Diuven이 git에서 파일 이름들만 어떻게 잘 받아서 G1을 맞았고, G2는 파일 이름만 GB단위라고 하더라.

명의 사람들이 원형으로 앉아서 모자를 쓰고 있다. 각 사람들은 자신의 모자를 제외한 모든 모자들의 색을 볼 수 있는데, 이 모자의 색은 이하의 자연수이다. (easy에서 , hard에서 ) 이 때 모든 사람들이 동시에 손을 들거나 들지 않을 수 있는데, 각 사람들은 다른 사람들의 모자 색과 손을 든 여부만 보고 자신의 모자 색을 맞추어야 한다.

인 이유는 당연히 를 준 것으로 생각했다. 그래서 당연히 이진법으로 하면 될 것이라고 생각하고 번부터 번 사람까지 볼 수 있는 사람들의 번째 비트를 모두 xor한 값이 이면 손을 들고, 이면 들지 않도록 했다.

이렇게 하면 번째 사람이 자신의 번째 비트를 모르는 문제가 생기는데, 번 사람이 볼 수 있는 모든 사람들의 모든 비트를 xor한 값을 기준으로 손을 들면 각 사람들은 자신의 모자 색의 비트 개수가 홀수인지 짝수인지 알 수 있게 되고, 남은 한 개의 비트를 특정할 수 있게 된다.

이 문제에서는 각 사람들의 행동을 lua로 코딩해야 했는데, lua를 처음 써봐서 상당히 말렸다. 처음에 냈다가 틀려서 lua를 깔았는데, 실수로 비트 연산자가 없는 5.1을 받아서 컴파일 오류를 보면서 시간을 꽤 날렸다. 5.3을 깔았는데 계속 모자 색이 이 나와서 당황했다. 결국 ^가 xor이 아니고 지수 연산자인 것을 몰랐던 것이 원인이었다. xor을 ~로 쓰더라…

H12 1:47 OK.

Diuven이 풀어보라고 해서 잡았다. 주어진 프로그래밍 언어로 코드를 짜야 하는데, 코드 길이 제한이 있고, 3진법 비트 연산을 쓰는데다가, if와 같은 분기가 없다. easy와 hard가 많이 달라서 따로 쓴다.

easy : 3진법으로 나타냈을 때, 1~i번 비트가 단조증가하는 최대 i를 구해야 한다.

일단 &를 통해 에서 1인 비트만 뽑아낼 수 있다. 에 0t1111…1111, 0t2222…2222를 xor한 후 똑같은 걸 하면 0, 2인 비트도 뽑아낼 수 있다. 0인 비트를 뽑아낸 것을 , 1인 비트를 , 2인 비트를 라고 하자.

를 의 모든 비트가 1인 prefix중 가장 긴 것을 제외한 모든 비트를 0으로 만든 수라고 하자.

잘 생각해보면 답은 의 비트 중 1의 개수가 된다. f의 값을 구해보자.

의 모든 0인 비트에 에 대해서, 번째 비트부터 번째 비트까지 모두 0으로 만들어버리면 f(X)가 된다.

&를 하면(쉬프트 연산에서 빈 칸은 상수를 이용해서 1로 채워줄 수 있다) 모든 에 대해 번째 비트와 번째 비트가 0이 된다. 를 부터 까지 배씩 늘리면서 반복하면 모든 에 대해 번째 비트부터 번째 비트까지 0이 될 것이고, 이것은 가 된다.

이제 0t1111…0000꼴의 수 X에 대해서 X의 1의 개수를 구하면 끝난다.

이것은 를 32부터 1까지 2배씩 줄여가면서 &를 답에 더해주고, X를 왼쪽으로 쉬프트해주면 된다. 널널하게 짜도 90개 정도의 명령어로 풀린다.

이 문제를 풀면서 상수를 잘못 써서 1번 틀렸다…

hard : 가 소수라면 1, 아니라면 0을 구하면 된다. 는 이하임이 보장된다.

일단 이하의 소수는 개로, 코드 길이 제한인 개로는 풀기 어려워보인다.

대회가 끝날 때 쯤 밀러 라빈을 생각했는데, 코딩이 많이 복잡해서 답이 없었다.

밀러 라빈을 돌리기 위해서는 을 꼴으로 표현해야 한다. 을 번 반복하면 와 을 분리할 수 있다. 적절하게 로 과 을 계산했다고 하면, 이 수들이 모두 이 아니면 합성수이고, 인 것이 하나라도 있으면 소수일 가능성이 있다.

이라는 C언어의 식은 와 동치이다. 모두 boolean으로 바뀌었다면 and와 or을 적절히 사용해서 답을 구할 수 있다.이기 때문에, 에서만 확인하면 충분하다. 명령어 개수가 5000개 이하가 되는지는 잘 모르겠다.

D1 2:42 OK.

C 문제를 도저히 이해할 수가 없어서 B로 넘어왔다. 종이를 몇 번 접은 후에 한 번 자르는데, 종이가 몇 개로 잘리는지 구해야 한다.

이 문제를 처음 봤을 때 easy가 풀려 있었다. 개수를 구하라길래 당연히 오일러 공식을 생각했는데, 컴포넌트 개수가 잘 안 구해졌다. LR로 자르거나 TB로 자르는 경우는 당연히 형태로 답이 나온다. 문제는 대각선으로 자를 때인데, 생각해보면 자른 종이를 폈을 때는 직사각형 내의 마름모가 계속 반복된 형태로 나온다. 종이를 폈을 때 접힌 선들로 만들어진 직사각형들을 생각해봤을 때, 인접한 직사각형은 무조건 잘린 선이 대칭일 것이다. 따라서 최종 형태는 원래의 종이에서 마름모, 삼각형들이 떨어져나온 모양이 된다. 따라서 왼쪽 위 직사각형이 잘린 모양, 세로로 접힌 횟수, 가로로 접힌 횟수를 알아내면 답은 가 된다. 식에서 와 는 왼쪽 위 직사각형이 잘린 모양, 세로로 접힌 적이 있는지의 유무, 가로로 접힌 적이 있는지의 유무를 통해 결정되는 이상 이하의 정수이다.