IPSC 2018 후기

https://ipsc.ksp.sk/

TAMREF, Diuven과 함께 참가했다. 대회가 새벽이라서 정신없었다.

시작할 때 Diuven이 앞 문제, TAMREF가 뒤 문제를 보기로 해서 대충 가운데인 E부터 읽었다.

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

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

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

 F1 0:24 OK.

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

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

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

 $C=4000$인 이유는 당연히 $2^{12}$를 준 것으로 생각했다. 그래서 당연히 이진법으로 하면 될 것이라고 생각하고 $2$번부터 $13$번 사람까지 볼 수 있는 사람들의 $i-2$번째 비트를 모두 xor한 값이 $1$이면 손을 들고, $0$이면 들지 않도록 했다.

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

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

 H12 1:47 OK.

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

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

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

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

잘 생각해보면 답은 $f(C | f(B | f(A)))$의 비트 중 1의 개수가 된다. f의 값을 구해보자.

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

$X$&$(X >> j)$를 하면(쉬프트 연산에서 빈 칸은 상수를 이용해서 1로 채워줄 수 있다) 모든 $i$에 대해 $i$번째 비트와 $i+j$번째 비트가 0이 된다. $j$를 $1$부터 $32$까지 $2$배씩 늘리면서 반복하면 모든 $i$에 대해 $I$번째 비트부터 $i+64(\geq 40)$번째 비트까지 0이 될 것이고, 이것은 $f(X)$가 된다.

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

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

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

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

일단 $\sqrt{10^9}$ 이하의 소수는 $3401$개로, 코드 길이 제한인 $5000$개로는 풀기 어려워보인다.

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

밀러 라빈을 돌리기 위해서는 $X - 1$을 $2^s(2d-1)$ 꼴으로 표현해야 한다. $D = D \div (2 - (D mod 2) )$을 $log_2{10^9}(\leq 30)$번 반복하면 $2^s$와 $2d - 1$을 분리할 수 있다. 적절하게 $mod X$로 $a^d-1$과 $a^{2^rd}+1$을 계산했다고 하면, 이 수들이 모두 $0$이 아니면 합성수이고, $0$인 것이 하나라도 있으면 소수일 가능성이 있다.

$A != 0$이라는 C언어의 식은 $A \div (A \div 2 + 1)$와 동치이다. 모두 boolean으로 바뀌었다면 and와 or을 적절히 사용해서 답을 구할 수 있다.

$X \leq 10^9$이기 때문에, $a = 2, 7, 61$에서만 확인하면 충분하다. 명령어 개수가 5000개 이하가 되는지는 잘 모르겠다.

 D1 2:42 OK.

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

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