NYPC 1회 후기

제 1회 NYPC에 참가했다.

예선

예선 문제는 처음 보는 유형들이라 당황스러웠다. 간단한 문제들은 적당히 풀었고, 지질학자 마리드도 풀었다. 넥스카 유적 문제도 적당히 만져봤는데, 그렇게 좋은 결과가 나오지는 않았다.

본선

본선 대회는 판교에 있는 넥슨 사옥에서 열렸다.

옷이 기모가 들어있어서 적당히 따뜻해서 좋았다. 그런데 대회 때는 긴장하고 긴장하면 배가 아픈데, 그래서인지 꽤 춥게 느껴져서 힘들었다.

S

N과 M이 주어지고, N×N 격자에 있는 블럭들은 중력에 따라 아래쪽으로 쏠린다. 90도 회전시키고 모든 블럭이 떨어질 때까지 기다리는 것을 M번 했을 때 최종적인 결과를 출력하는 문제였다.

풀이

N, M ≤ 100 이어서 적당히 풀면 된다.

M

성냥개비로 이루어진 수식이 있다.

숫자는 seven segment의 형태로 나와있다. seven segment는 반드시 다음과 같아야 한다.

값	켜져있는 세그먼트
1	2, 3
4	2, 3, 6, 7
6	2 빼고 전부
7	1, 2, 3, 6
9	5 빼고 전부

주어지는 식은 (숫자)(기호)(숫자)(기호)...(숫자)(기호)(숫자) 형태로 나와있다. 숫자는 네 자리 수 이하이며, 0으로 시작하지 않는다. 기호는 +와 -만 있다.

어떤 성냥개비를 집어서 다른 자리에 놓을 수 있다. 단 새로운 숫자를 만들거나 기호를 없앨 수는 없다.

또한 존재하지 않는 숫자나 기호가 되어서도 안 된다. 즉 새로 만들어진 식은 완벽하게 해석 가능해야 한다.

새로 만들어진 식에서 각 숫자는 0으로 시작하여도 된다. 이 때 그런 leading zero들은 무시된다. (ex: 0009→9, 0123→123)

M1

단 하나의 성냥개비를 움직여서 전체 식의 값이 0이 되도록 만들어라. (답은 항상 존재한다.) 문자열의 길이는 1000 이하이다.

풀이

성냥개비의 움직임은 다음 두 가지 중 하나이다.

1. 한 글자에서 빼어서 다른 글자에 넣거나
2. 한 글자 내에서 움직이거나

그러면 다음의 세 가지 자리가 있다.

1. 성냥개비를 없애도 제대로 된 값이 남게 되는 자리
2. 성냥개비를 넣어도 제대로 된 값이 남게 되는 자리
3. 성냥개비를 그 글자 내의 다른 자리로 옮기면 제대로 된 값이 남게 되는 자리

이러한 자리들을 정리해놓고, 1번과 2번 자리들의 모든 쌍을 테스트해보고, 3번 자리들을 모두 테스트해보면 된다.

M2

원래 식의 절댓값이 I라고 하자. 성냥개비를 N회 움직여서 전체 식의 절댓값이 X가 되었을 때, 당신의 포인트는 다음과 같다.

$$\max \left ( \left \lfloor \frac{I-X}{\sqrt{N+100}} \right \rfloor, 0 \right)$$

열 개의 테스트 데이터 각각에 대해 점수를 매겨 합산한다. 해당 데이터에 대해 가장 많은 포인트를 획득한 사람의 포인트가 $$M$$ , 당신의 포인트가 $$P$$ 이라고 하자.

• $$M = P$$ 이면 10점.
• $$M \neq P$$ 이면 $$\left \lfloor \frac {10 \cdot P} {M} \right \rfloor$$ 점.

풀이

Greedy way to find local minimum

먼저 처음 식에서 위에서 설명한 세 가지 자리들을 모두 찾아놓는다. 그 후 매 상황마다 현재 할 수 있는 것중에 최선의 선택을 한다. 정확하게는 다음과 같다.

---

1e3번동안 반복하며: ​ 2e3번동안 반복하며: ​ 0.15의 확률으로: ​ 그 글자 내의 다른 자리로 옮김이 가능한(정확히는 가능했던) 곳을 랜덤하게 선택한다. ​ 만약 아직도 그 동작이 가능하다면: ​ 그 동작을 수행했을 때의 값의 변화를 계산하여 최솟값 동작을 갱신 ​ 1-0.15의 확률으로: ​ 없앰이 가능했던 자리와 넣음이 가능했던 자리 각각을 랜덤하게 선택한다. ​ 만약 아직도 두 동작 모두 가능하다면: ​ 그 동작을 수행했을 때의 값의 변화를 계산하여 최솟값 동작을 갱신 ​ 만약 절댓값이 작아지는 동작이 없다면: ​ break ​ 절댓값이 가장 작아지는 동작을 수행한다

---

옮김, 없앰, 넣음이 가능한 자리들은 다른 동작을 수행하다보면 불가능하게 될 수도 있기 때문에 해당 동작이 가능한지 매번 확인하는 것이다. 물론 옮김, 없앰, 넣음을 거치다 보면 새로운 자리(없앰, 넣음 등이 가능해지는 자리)가 생기기도 하지만, 생각하기 귀찮아서 고려하지 않았다.

간단히 말하면 2e3개의 random으로 선택한 sample을 확인해보고 그중에서 최적인 동작을 수행하는 전략이다. 항상 값이 작아지는 쪽으로만 동작하기 때문에, 이는 사실 greedy한 방법이다. 그런데 값이 커지는 쪽으로도 가끔 가는 알고리즘도 있다. 그것이 다음에 소개할 SA이다.

Simulated Annealing

이런 풀이도 있을 수 있다. (C는 임의의 상수)

---

for i in [0...N]:
	임의의 가능한 동작 m을 선택한다.
	if P(m에 의한 절댓값의 변화, 1 / exp(C * i / N)):
		m을 수행한다

---

이런 방법을 Simulated Annealing이라고 한다. 여기서 함수 $$P(\delta, T)$$ 은 확률적으로 True를 반환하는 함수인데,

• $$\delta < 0$$ 면 항상 True를 반환한다.
• $$\delta > 0$$ 일 때, $$T$$ 가 클 수록 True를 반환할 확률이 높다

물리학와의 analogy를 위해서 $$T$$ 를 온도라고 부르는 경우가 많다. 처음에는 $$\delta > 0$$ 인 경우(절댓값이 커지는, 손해보는 경우)라도 어느 정도 허용해준다. 그러나 시간이 지남에 따라 $$T$$ 가 작아지면서, $$\delta < 0$$ 인 경우를 선호하도록 한다. $$T = 0$$ 일 때는 $$\delta < 0$$ 인 경우만 허용해주는 식이다.

이런 P는 이런 식으로 짜는 경우가 많다.

 
xxxxxxxxxx
def P(delta, temp):
    if delta < 0: return True
    if temp == 0: return False
    tmp = exp(delta / temp)
    return random.random() < tmp # random.random() returns random number in [0, 1]

이 P에 적절한 값이 들어가도록 위의 상수 C를 조절해보면 된다.

대회 때는 이 P 함수를 어떻게 설계할지 잘 모르겠어서, SA를 짜지 않고 위의 greedy한 방법을 짰다. SA는 하나의 random한 move를 평가하지만, 내 방법은 몇 개(2천개)의 sample을 잡아서 그 중에서 최적인 것을 선택했다.

보통 이렇게 어떤 복잡한 목표값을 줄이는 문제는 이렇게 푼다.

• 기저 solution을 잡는다. (이 문제의 경우 주어진 식 그대로가 하나의 solution이다. TSP의 경우 그냥 1-2-...-N 으로 이어버려도 되고, 랜덤하게 이어도 된다.) 이 solution은 좋을 필요가 절대 없다. (오히려 local minimum이면 안 좋을 수도 있음)
• 한 solution에서 다른 solution으로의 어떤 'move'를 생각한다. (이 문제의 경우 빼고 넣음, 혹은 제자리에서 바꿈 등이다. TSP의 경우, 두 도시의 순서를 서로 바꾸는 것을 쓸 수 있겠다.)
• SA 등으로 그러한 move를 확률적으로 선택하거나, 위의 방법처럼 여러 개를 뽑아서 각각 평가하여 선택한다.
• 이를 반복하면 최종 상태에 수렴하게 된다. 이것이 일단 지금 나온 최적해이다.
• 초기 조건(기저 solution)에 따라 결과값이 다를 수 있으므로, 이 전체 과정을 다섯 번 정도 반복할 수도 있다. (시간만 많다면...)

이 해법으로 마지막 데이터에서는 무려 12만점이 나왔다. 순간 숫자가 너무 크길래 예선의 크레이지 아케이드 문제처럼 값이 클 수록 안 좋은건가 했다. 대회가 끝날 때까지 주변 사람들의 점수를 보면서 따라잡힐지 조마조마했다.

F

F1

x와 y를 바꿔서 출력한 것 때문에 제출을 9번인가 했다.

F2

처음에 낸 풀이는 밭을 하나 찾고(없으면 만들고), 값이 제일 싼 농작물만 무식하게 계속 심고 수확해서 최종 상태에 도달하려는 것이었다. 부분점수(45점?)를 받길래 어떻게 하지 하고 고민하다가, 농작물을 심을 시점마다 지금 심을 수 있는 것중에 가장 많이 벌 수 있는 것을 심었다. 그랬더니 50점이 나왔다.

후기

일단 프로그래밍 대회에서 많이 보지 못했던 스타일(NP 문제의 포인트 경쟁, 머신 러닝 등)이었기 때문에 좀 충격이기도 했지만, 생각보다 재미있었다.

근데 그런 포인트 경쟁 문제가 본선에도 나올 줄은 몰랐다(...) 스코어보드와 내 주변 점수가 실시간으로 보여서 다행이었다. M2 문제는 진짜 운이 좋았던 것 같다.

IOI 후기는 쓰려다가 몇 달째 방치되어 있다. 한 번 써야 할텐데...