[mathjax]

인터넷에서 acm-icpc 2016 평양 리저널 문제를 찾았습니다. 북한 문제는 어떤 수준인지, 컴퓨터 과학 용어는 우리와 얼마나 많이 차이나는지 궁금해서 저화질의 사진을 보기 쉽게 글로 다시 정리해 보았습니다. 줄바꿈과 일부 기호는 임의로 수정했습니다.

총 12문제로 구성되어 있습니다. 개인적으로는 Mathforces 대회 같은 느낌의 문제들이라고 생각됩니다.

모든 문제는 ICPC Live Archive에서 풀어볼 수 있습니다. 시간제한이 다릅니다.

---

문제 1. 배렬전도수

• 시간 제한: 1초
• 메모리 제한: 64MB

설명

당신들은 모두 배렬1배열.의 전도수에 대하여 알것이다. 배렬 \(\left\{ a_1, a_2, \cdots, a_n \right\} \)의 전도수는 \(i < j\)이고 \(a_i > a_j\)인 \(\left(i, j \right)\)의 쌍의 개수로 정의한다.

한민이는 총명한데 지금 새로운 배렬의 전도수를 생각하고있다.

만일 \(i\) 와 \(j\) 의 짝홀성이 같으면서 \(a_i > a_j\)이면 그는 \(\left(i, j \right)\)를 전도된 쌍으로 생각한다. 한편 짝홀성이 다르면서 \(a_i < a_j\)이면 그는 이런 쌍\(\left(i, j \right)\)도 전도된 쌍으로 생각한다. 다른 말로 말한다면 첨수쌍2벡터. \(\left(i, j \right)\)는 \(i\) 와 \(j\) 의 짝홀성이 같을 때 \(a_i > a_j\)이거나 다를 때 \(a_i < a_j\)이면 전도된 쌍이다.

당신은 한민의 딱친구3단짝 친구.이고 배렬의 전도된 쌍의수를 계산할데 대한 부탁을 받았다. 당신은 풀수 있는가?

입력

입력파일의 첫행은 입력자료4테스트 케이스.개수 \(T \left(1 \leq T \leq 5\right)\)로 되어있다.

매입력자료의 첫행은 한개의 옹근수5정수. \(N \left(1 \leq N \leq 5000\right)\)을 포함하는데 그것은 배렬의 길이이다.

다음행에 \(N\) 개의 실수가 공백단위로 분리되어 들어온다.

출력

당신은 매 입력자료별로 한행에 전도수를 찍는다.

표준입력

1
5
1 4 3 2 5

표준출력

5

---

문제 2. \(B_N\)

• 시간 제한: 1초
• 메모리 제한: 128MB

설명

총명한 학생 리기웅은 물리를 아주 잘하지만 수학은 잘하지 못한다. 그의 동무 신영진은 반대로 수학을 잘하고 물리를 잘하지 못한다. 그래서 리동무는 신동무의 물리숙제를 도와주고 신동무는 리동무의 수학숙제를 도와준다.

오늘 리동무는 아주 힘든 수학문제를 받아가지고 와서 신동무에게 물어보았다. 그러나 신동무는 아주 바빠서 그는 당신에게 풀어줄것을 부탁하였다. 당신은 신동무의 딱친구이며 반드시 그것을 풀어야 한다. 문제는 다음과 같다.

배렬 \(\left\{ A_1, A_2, \cdots, A_n \right\} \)이 주어졌다. 새로운 배렬 \(\left\{ B_1, B_2, \cdots, B_n \right\} \)은 다음의 공식에 따라 정의된다.

\[ B_N = \left( \sum_{\substack{i_1+i_2+\cdots+i_k=N \\ 1\leq k \leq N}} A_{i_1}A_{i_2}\cdots A_{i_n} \right) \% 1000000007 \]6%는 나머지 연산 기호

물론 \(1 \leq i_1, i_2, \cdots, i_k \leq n\) 이다. \(u \neq v\)에 대하여 \(i_u = i_v\)도 가능하다. 실제로 \(B_3 = A_1 \times A_1 \times A_1 + A_1 \times A_2 + A_2 \times A_1 + A_3\)이다. 당신은 반드시 주어진 \(N\)에 대하여 \(B_N\)을 계산해야 한다.

당신은 그들을 도와줄수 있는가?

입력

입력파일의 첫행은 입력자료개수 \(T\)로 되어있다.

매 자료의 첫행은 두개의 옹근수 \(n\) 과 \(N\)으로 되어있다. \(\left(1 \leq n \leq 100, 1 \leq N \leq 100\right)\)

다음행에는 \(n\) 개의 옹근수가 공백단위로 분리되어 들어온다.

출력

문제의 결과를 출력하시오.

표준입력

1
2 5
3 2

표준출력

495

---

문제 3. 행렬검사

• 시간 제한: 1초
• 메모리 제한: 512MB

설명

정교수는 제 41 차 국제대학생프로그람아시아평양지역경연 문제출제자이다. 그는 100개조의 2016 × 1946 행렬과 1946 × 2016행렬의 곱하기를 끝냈다. 물론 결과는 2016 × 2016행렬식이다. 계산하는데 거의 10일 걸렸다. 결과는 100개조이고 문제 C의 입출력자료로 될것이다.

계산이 끝난 후 정교수는 잠들었고 그의 아들이 결과에 손을 댔다. 그는 어느 한 수의 하나의 자리를 지우고 수자7숫자. 1을 써넣었다.

다음날 정교수는 매우 성났다. 그러나 아들애는 겨우 2살이어서 모든것을 기억하지 못한다.

정교수는 그의 아들의 말을 들어보고 세부를 검사한다. 그래서 그는 아들이 매 조의 한수의 하나의 자리수를 변화시켰고 그 수자가 2, 0, 1, 6 중의 하나라는것을 알았다. 그리고 그는 아들이 변화시킨 위치가 행번호와 렬번호가 70 이하라는것을 알았다. 행렬의 왼쪽웃구석의 번호는 (1, 1) 이다. 첫 첨수는 행번호이고 다음번호는 렬번호이다.

그는 입출력을 오늘중으로 전송하여야 한다. 그래서 그는 결과를 검사할 결심을 하였다. 당신은 그의 우수한 학생이다. 정선생을 도우시오.

입력

입력파일은 꼭 100조의 입출력자료로 되어있다. 매 조는 다음과 같이 정의되었다.

첫행은 5개의 옹근수 \(a_1, a_2, a_3, a_4, a_5\)로 되어있다. 당신은 다음과 같이 행렬 \(A\)를 얻을수 있다.

\[A_{ij} = (a_1 \times i^4 + a_2 \times i^3 + a_3 \times j^2 + a_4 \times j + a_5) \% 1946002016\]

다음행은 5개의 옹근수 \(b_1, b_2, b_3, b_4, b_5\)로 되어있다. 당신은 다음과 같이 행렬 \(B\)를 얻을수 있다.

\[B_{ij} = (b_1\times i^4 + b_2\times i^3 + b_3\times j^2 + b_4\times j + b_5) \% 1946002016\]

다음 왼쪽웃구석의 70 × 70 옹근수 행렬이 있다. 당신은 이 행렬식을 검사하여야 한다.870 × 70 행렬의 정확한 입력형식은 주어지지 않았으나 공백과 줄바꿈으로 구분될 것으로 예상합니다.

당신은 두 행렬을 곱할 때 행렬을 반드시 2016011010에 관하여 나머지를 취한다.

출력

당신은 어느 입력조가 아들에 의해 변화되었는가를 출력해야 한다. 입력의 번호는 1부터 100까지 이다. 당신의 출력은 반드시 증가순서로 출력해야 하며 공백단위로 분리되어있어야 한다. 만일 모든 입력조들이 변화되지 않았다면 0을 출력하시오.

입력과 출력의 실례

입력과 출력이 너무 커서 우리는 당신들에게 입력과 출력의 실례를 보여줄수 없다. 당신은 입출력의 형식을 담보해야 한다.

---

문제 4. 사과나누기

• 시간 제한: 8초
• 메모리 제한: 512MB

설명

현일은 도덕있는 학생이다. 그는 항상 그의 학급동무들과 친구들을 자기자신처럼 대해준다. 하루는 그가 맛있고 큰 사과를 가져와 그의 친구들에게 나누어주려고 한다. 흥미있는것은 사과가 타원모양이라는것이다.

그는 항상 두가지 조작을 진행한다.

첫번째는 사과의 \(L\)부터 \(R\)각도사이의 남은 면적을 계산하는것이다.

둘째는 \(L\)부터 \(R\)각도사이의 모든 사과쪼각들을 주는것이다.

현일은 사과를 데카르트자리표계9데카르트 좌표계. (=직교좌표계.)에 놓았으며 결과 사과는 타원 \(\frac{x^2}{a^2}+\frac{y^2}{b^2}=1\) 에 자리잡고있다.

현일의 형인 당신은 어린 동생의 계산능력을 시험해보려고 하는데 당신은 모든 질문들에 반드시 대답해야 한다.

할수 있는가? 있다.

아, 한가지 조건이 또 있는데⋯ \(prev\)는 마지막으로 출력된 수이며 실제 \(L\)과 \(R\)은 다음의 공식에 의해 계산된다.

\[L_{real} = \left( L_{given} + prev \right) \% 360, R_{real} =\left( R_{given} + prev \right) \% 360\]

만약 \( L_{real} > R_{real} \)이면 당신은 두값을 바꾸어야 한다. 당신은 조작을 \(L_{real}\)과 \(R_{real}\), 두값을 가지고 해야 한다. 처음에 \(prev = 0\)이다.

입력

입력파일의 첫행은 세옹근수를 포함한다. – \(a\) \(b\) \(n\) \(\left( 1 \leq a, b \leq 100, n \leq 300000 \right)\)

\(a\)와 \(b\)는 우에서 설명한 수이고 \(n\)은 조작회수이다.

다음의 \(n\)개 행은 세 수 “\(type\) \(L\) \(R\)”을 포함한다. (\(1 \leq type \leq 2\), \(L\)과 \(R\)은 임의의 실수이다.) \(0 \leq L + prev,0 \leq R + prev\) 라는것은 담보할수 있다.

출력

모든 조작1에 대해서 결과를 계산해야 한다. 소수점아래 5자리에서 반올림하여 출력하시오.

표준입력

10 10 3
1 10.00000 30.00000
2 40.00000 70.00000
1 10.00000 300.00000

표준출력

17.45329
226.89280

주해

문제가 쉬워 지도록 \(L\)과 \(R\)도 소수점아래 5자리로 주어진다. 그리고 \(prev\)는 마지막으로 출력된 첫번째 질문의 값이다. 실례로 \(prev = 17.45329\) 이지만 실제 대답은 \(17.453297519943295769236907684886\cdots\)이다.10쉽게 말해 prev를 계산할 때는 출력된 (반올림된) 값을 사용하라는 뜻입니다.

---

문제 5. 쉬운 기하문제

• 시간 제한: 1초
• 메모리 제한: 32MB

설명

\(ABCD\)는 4면체이며 \(\overline{DA} = a\), \(\overline{DB} = b\), \(\overline{DC} = c\), \(\angle BDC = \alpha\), \(\angle ADC = \beta\), \(\angle ADB = \gamma\)로 주어진다. 당신은 \(ABCD\)의 내접원11내접하는 구.반경을 계산해야 한다.

입력

첫행은 입력자료개수 \(T (1 \leq T \leq 100000)\)로 되어있다.

매 입력자료는 6개의 수 \(a, b, c, \alpha, \beta, \gamma\) \((1 \leq a, b, c \leq 100, 0 < \alpha, \beta, \gamma < 360)\) 을 포함한다.

출력

내접원의 반경을 소수점아래 6자리에서 반올림하여 출력하시오.

표준입력

1
10 10 10 90 90 90

표준출력

2.113249

---

문제 6. 가장 좋은 경로찾기

• 시간 제한: 4초
• 메모리 제한: 256MB

설명

비트시는 바이트랜드의 수도이다. 비트시에는 현대적인 고속도로체계가 있으며 그 체계는 자주 갱신되는데 고속도로들이 체계에 추가된다. 체계는 교차점들을 연결하는 고속도로들로 이루어져있다.

운수회사 사장인 당신은 어느 한 교차점에서 다른 곳으로 콤퓨터들을 수송하려고 한다. 그런데 바이트랜드에서 휘발유값이 너무 비싸 당신은 한대의 화물자동차로만 나르려고 한다. 당신은 가능한껏 많은 콤퓨터들을 나르려고 하지만 모든 고속도로들은 \(W\)대이상의 콤퓨터들은 나를수 없다는 제한을 가지고있다.

당신은 나를수 있는 콤퓨터의 최대값을 계산해야 한다. 당신의 초기의 고속도로체계상에서 임의의 두 교차점사이로 이동할수 있다. 다시말하여 원래 체계는 연결되었다.12연결되어 있다.

입력

첫행은 입력자료개수 \(T (1 \leq T \leq 3)\)로 되어있다.

매 입력자료는 교차점과 도로수를 의미하는 두 옹근수 \(N\)과 \(M\)으로 시작된다. \((3 \leq N \leq 70000, N-1 \leq M \leq 150000)\)

다음의 \(M\)개행은 \(a\)와 \(b\)사이에 도로가 있으며 제한은 \(c\)임을 의미하는 세개의 옹근수 \(a\) \(b\) \(c\)를 포함한다. \((1 \leq a, b \leq N, 1 \leq c \leq 10000)\)

다음 행은 질문의 개수를 의미하는 하나의 옹근수 \(Q (1 \leq Q \leq 105000)\)를 포함한다. 모든 질문은 다음의 두 종류중 하나이다.

1. \(a\) \(b\) \(c\): \(a\)와 \(b\)사이에 도로를 련결하며 제한은 \(c\)이다.
2. \(a\) \(b\): \(a\)로부터 \(b\)로 나를수 있는 콤퓨터의 최대개수를 계산하시오. \((1 \leq a, b \leq N, 1 \leq c \leq 10000)\)

두 교차점사이에는 둘 혹은 그 이상의 도로가 있을수 있다.

출력

둘째 종류의 매 질문에 대해 나올수 있는 콤퓨터의 최대대수를 출력하시오.

표준입력

1
5 6
1 2 2
1 3 3
2 4 7
2 5 1
3 4 6
3 5 5
4 
2 2 5
1 4 5 8
2 2 5
2 3 4

표준출력

5
7
6

---

문제 7. 좋은 날들

• 시간 제한: 1초
• 메모리 제한: 64MB

설명

당신은 두개의 날자 \(\texttt{y/m/d}\)와 \(\texttt{yy/mm/dd}\)를 입력 받는데 하나는 첫번째 좋은 날이고 하나는 마지막 좋은 날이다. 그것들사이의 모든 날들도 역시 좋은 날이며 다른것들은 그렇지 않다. 당신은 좋은 날자수를 계산해야 한다.

입력

첫행은 입력자료개수 \(T (1 \leq T \leq 10000)\)로 되어있다.

매 입력자료는 6개의 옹근수 \(y\) \(m\) \(d\) \(yy\) \(mm\) \(dd\)로 되어있다. \((1 \leq y, yy \leq 5000)\)

출력

좋은 날자수를 출력하시오.

표준입력

1
2016 11 8 2016 11 11

표준출력

4

---

문제 8. 효성과 광성

• 시간 제한: 1초
• 메모리 제한: 256MB

설명

영어소문자로 이루어진 긴 문자렬 \(S\)가 있다. 두 소년 효성이와 광성이는 재미난 경기를 한다. 경기규칙은 다음과 같다.

초기에 심판원 학명이가 그들에게 비지 않은 \(S\)의 부분문자렬을 준다. (우리는 그것을 \(P\)로 표시하자.) 두명의 경기자는 교대로 뒤에 한개의 문자를 추가하여 새로 생긴 문자렬이 \(S\)의 부분문자렬이 되게 한다. 만일 그들이 문자를 추가하지 못하면 경기는 끝난다.

효성이는 마지막 문자렬이 가능한껏 짧게 하려고 하고 광성이는 문자렬이 가능한껏 길게 하려고 한다. 효성이는 첫 경기자이다. 만일 그들이 최량13최선.으로 경기를 한다면 매 문자렬에 대하여 추가되는 문자의 수를 추측할수 있다. (우리는 그것을 \(f(P)\)로 표시하자.)

부분문자렬 \(A\)는 만일 \(f(A) < f(B)\) 이거나 \(f(A) = f(B)\)이고 \(A\)가 \(B\)보다 사전순으로 앞에 놓이면 부분문자렬 \(B\)보다 작다고 정의한다.

주어진 옹근수 \(K\)에 대하여 문자렬 \(S\)의 \(K\)-번째로 작은 문자렬을 찾으시오. 찾아낼수 있는가?

입력

첫행은 한개의 문자렬로 되어있는데 그것의 길이는 500000 이하이다.

두번째행은 하나의 옹근수 \(K (1 \leq K \leq 1000000000)\)로 되어있다.

출력

결과 문자렬에 대하여 그것에 추가되는 문자의 수와 결과문자렬을 공백단위로 분리하여 출력하시오.

표준입력

aababb
8

표준출력

1 abab

---

문제 9. 국제망봉사

• 시간 제한: 1초
• 메모리 제한: 256MB

설명

지구상에는 수많은 망봉사기14서버(server).들이 있다. 모든 수 \(i\)에 대하여 \(i\)번째 망봉사기는 “반경” 이라고 불리우는 지수값 \(R_i\)를 가지고있으며 봉사기는 자기로부터 떨어진 거리가 \(R_i\)이하인 모든 점들까지 봉사15서비스(service).할수 있다.

일부 점들은 많은 봉사기들로부터 봉사받을수 있다. 너의 과제는 최대로 많은 개수의 봉사기로부터 봉사받을수 있는 점을 찾는것이다.

지구는 6370의 반경을 가진 완전구로 보며 지구겉면의 구 점사이거리는 유클리드거리가 아니라 겉면상에서의 거리이다.

문제를 쉽게 하기 위해 망봉사기들의 반경을 2012 부터 2016 사이로 한다. (2012와 2016 포함)

입력

첫행은 입력자료개수 \(T (1 \leq T \leq 6)\)로 되어있다.

매 입력자료의 첫행은 봉사기의 대수 \(N (1 \leq N \leq 1000)\)을 포함한다.

다음 \(N\)개 행은 봉사기의 경도와 위도, 반경을 나타내는 세 옹근수를 포함한다. (0 ≤ 경도 < 360, -90 < 위도 < 90)

출력

문제의 답을 출력하시오.16데이터에서 알 수 있지만, 가장 많은 서버가 서비스하는 지역의 위치가 아닌 그 지역에 서비스하고 있는 서버의 대수를 출력해야 됩니다.

표준입력

1
2
0 0 2012
0 1 2016

표준출력

2

---

문제 10. 보석통

• 시간 제한: 3초
• 메모리 제한: 256MB

설명

성영은 아무런 수학문제도 아주 빨리 풀수 있다. 그의 형 최광은 비싼 보석들을 보관할수 있는 빈 \(N\)개의 보석통들을 가지고있다.

하루는 최가 보석상점에서 \(N\)개의 보석을 가져왔다. 최는 모든 보석들을 한통에 한개씩 넣을것이다. 다시말하여 그는 매통에 오직 하나의 보석을 보관할것이다.

모든 보석들은 4개의 수를 가지고있는데 보관번호 \(p\), 통에 도착하는 시간 \(t\), 그리고 2가지 값 \(a\)와 \(b\)를 가진다. \((p, t, a, b)\)에대한 설명을 하자.

보석\((p, t, a, b)\)이 도착하면 최는 이미 도착한 보석들가운데서 가장 잘 결합되는 보석을 찾아내야 한다. 가장 잘 결합되는 보석\((p_1, t_1, a_1, b_1)\)은 다음의 조건을 만족시켜야 한다.

1. 그것은 반드시 새 보석보다 먼저 도착하여야 한다. 다시말하여 \(t_1 < t\).
2. 그것의 통번호는 \(p\)보다 작아야 한다. 다시말하여 \(p_1 < p\).
3. 결합효과가 최대로 되어야 한다. 결합효과는 다음과 같이 정의한다. \(a_1 \times a + b_1 \times b\).

그리고 최는 그 통의 뚜껑에 보석들의 결합효과를 써넣으려고 한다. 그래서 최는 성영에게 매통의 뚜껑에 수를 계산하여 써놓을것을 부탁했다. 성영을 도와주자.

입력

첫행은 옹근수 \(N (1 \leq N \leq 100000)\) 을 포함하는데 이것은 보석통의 개수이다.

그리고 다음 \(N\)개의 행이 있다.

\(p\)번째행은 3개의 변수 \(t\) \(a\) \(b\)를 포함한다. – 그곳은 보석 \((p, t, a, b)\)를 의미한다. \((1 \leq t \leq 1000000000, 1 \leq a, b \leq 1000000)\)

어느 두개의 보석도 동시에 도착하지는 않는다.

출력

\(N\)개의 옹근수들을 출력하시오. \(p\)번째수는 \(p\)번째 뚜껑에 써넣을 수이다.

표준입력

3
1 1 1
2 2 2
3 3 3

표준출력

0
4
12

---

문제 11. K번째 그라프 절단

• 시간 제한: 3초
• 메모리 제한: 512MB

설명

지성은 그라프리론17그래프 이론.을 배우기 좋아한다. 처음 그는 최소생성나무18최소 스패닝 트리(minimum spanning tree).에 대하여 배웠다. 다음 그는 최단경로에 대하여 배웠다. 그리고 그는 지금 그라프의 절단문제에 대하여 배우고있다.

무게붙은 방향그라프19가중 방향 그래프(weighted directed graph).(그것은 연결이 아니어도 된다)와 원천과 목적지가 주어진다. 말할 필요는 없지만 원천과 목적지는 그라프의 한개 정점이다.

다음 당신은 그라프에서 원천지와 목적지사이에 아무런 경로도 없게 그라프에서 마디20간선.를 없애야 한다. 그때 제거한 마디들의 무게 합을 “절단” 이라고 부른다.

지성은 이미 일반그라프에서 최소절단이 원천지와 목적지사이의 최대흐름과 같다는것을 알고있다. 그리고 그는 지금 \(K\)째 최소절단에 대해서 알고싶어한다. 그는 \(K\)째 최소생성나무와 \(K\)째 최단경로를 구할수 있지만 \(K\)째 최소절단을 구할수 없다. 그를 도와주자.

입력

첫행은 5개의 옹근수 \(N\) \(M\) \(K\) \(S\) \(T\)를 포함한다.

\(N (1 \leq N \leq 100)\) – 그라프의 정점수를 의미한다.

\(M (1 \leq M \leq 1000)\) – 그라프의 마디수를 의미한다.

\(K (1 \leq K \leq 100)\)

\(S (0 \leq S < N)\) – 원천지의 정점번호.

\(T (0 \leq T < N)\) – 목적지의 정점번호. \((S \neq T)\)

다음 \(M\)개 행은 3개의 옹근수 \(a\) \(b\) \(c\)를 포함한다. – \(a\)와 \(b\)사이의 미디이며 그것의 무게는 \(c\)이다. \((0 \leq a, b < N, a \neq b)\)

문제를 쉽게 하기 위하여 매 \(i (0 \leq i < N, i \neq S, i \neq T)\)에 대하여 \(i\)와 \(T\)사이에 적어도 하나의 마디가 있다.

출력

문제에 대한 답을 출력하시오.

만일 \(K\)째 최소절단이 없다면 -1을 출력하시오.

표준입력

3 3 3 0 2
0 1 1
0 2 3
1 2 2

표준출력

6

---

문제 12. 긴옹근수 인수분해

• 시간 제한: 1초
• 메모리 제한: 256MB

설명

나는 대수를 아주 좋아하는데 특히 인수분해를 좋아한다. 긴옹근수 인수분해는 나에게 즐거움을 주지만 그것은 힘든 문제다.

나의 선생님은 새 인수분해 문제를 주었다. “옹근수 \(N\)이 주어졌을 때 큰 옹근수 \(N^4 + 64\)을 인수분해해야 한다.”

첫단계로 나는 \(N^4 + 64\)을 2개의 옹근수 \(a\) \(b\)의 적21곱.으로 표시하고싶다. 물론 \(1 < a, b < N^4 + 64\)이다.

나는 이것을 할수 있지만 바쁘다. 나를 도울수 있는가?

입력

첫행은 입력자료의 개수 \(T (1 \leq T \leq 10000)\)를 포함한다.

매 입력자료는 한개의 옹근수 \(N (1 \leq N \leq 10000)\)을 포함한다.

출력

\(N^4 + 64 = a \times b\)를 만족하는 \(a\)와 \(b\)를 출력하시오. 만일 여러가지 경우가 있다면 그중 하나를 출력하시오.

표준입력

1
1

표준출력

5 13

11월 23일에 2018 서강대학교 프로그래밍 대회가 3시간동안 열렸습니다. 매년 서강대학교 학부생을 대상으로 열리는 개인 단위의 ACM-ICPC 스타일 알고리즘 대회입니다. 올해로 14년째입니다. (2016년에 제 12회였으니까 아마 올해가 14번째겠죠 ..? 잘 모르겠지만 그럴거에요)

1~2학년만 참가할 수 있는 Master 디비전과 전학년이 참가할 수 있는 Champion 디비전이 있습니다. 저는 오프라인 대회 경험이 별로 없는 새내기라서 Master 디비전에 참가했습니다. 내년부터 알고리즘 학회장을 하게 되기 때문에 교내 대회를 참가자로서 참여하는 건 이번이 처음이자 마지막일지도 모르겠네요 😄

문제는 디비전마다 6문제, 총 12문제였어요. Baekjoon Online Judge에서 오픈 컨테스트를 풀어볼 수 있어요. Master 디비전에는 오픈 컨테스트의 A, C, D, E, G, I 번 문제가, Champion 디비전에는 B, F, H, J, K, L 번 문제가 출제되었습니다.

여름에 2018 전국 대학생 프로그래밍 대회 동아리 연합 대회(UCPC 2018)에서 풍선 스탭으로 일하면서 참가자 분들 책상에 풍선을 달아드렸는데, 이번엔 제 책상에 풍선이 달리는(?) 입장이었어요. 제가 풍선을 달 때는 참가자 분들이 신경쓰이실까봐 다소 걱정도 했지만 문제를 푸는 입장이 되어 보니 생각보다 신경쓰이진 않았어요!

풍선이 많이 달리면 대회장이 예뻐져요. 이런 문화 좋아요!

대회에서 Kotlin을 못 써서 조금 아쉬웠어요. 제 주력 언어는 Kotlin이고, 제가 BOJ에서 푼 문제 중 90% 넘는 문제는 Kotlin으로 풀었거든요. 하지만 학회에서 스터디 하면서 C++에 어느 정도 익숙해져서 딱히 무리는 없었어요. Kotlin은 icpc 월드 파이널 나갈 일이 있다면 거기서 써서 제트브레인의 관심을 한 몸에 받는 거로 만족하고 싶어요. 근데 뭐 일단 월드 파이널을 나갈 수가 있어야..

아무튼 이런 대회가 처음인 새내기의 잡소리는 치워 두고, 문제 이야기를 해 봐요!

문제 이야기

경고: 이 밑에는 솔루션이 있습니다.

솔루션은 제가 문제를 푼 순서입니다.

C. 어려운 소인수분해 / BOJ #16563

A번 풀이가 의외로 곧바로 생각나지 않아서 C부터 풀었습니다. 에라토스테네스의 체는 자신있었거든요.

2와 500만 사이의 자연수가 들어오기 때문에 먼저 $\sqrt{5000000} \approx 2236$까지의 소수를 에라토스테네스의 체로 전처리해 둡니다. 대회에서는 정확하게 500만의 제곱근을 하는 대신 대략 3000으로 잡았습니다. $\pi (2236)=331$이기 때문에, 대략 350개가 안 되는 소수를 얻을 수 있습니다.

어떤 수 n을 입력받습니다. 이제 소수 p에 대해 n이 p로 안 나눠질 때까지 n을 p로 나누고, 동시에 p를 출력합니다. p를 2부터 점점 늘려가다가 n이 $p^2$보다 작아질 경우엔 더 이상 p로 나눠질 리가 없다고 판단하고 루프를 빠져나옵니다. 2236까지의 모든 소수로 나눠봤는데도 n이 1이 아니면, 남아 있는 n 자체가 소수라는 뜻이기 때문에 이 때는 n을 추가로 출력합니다. 이렇게 하면 소인수분해를 해야 되는 수의 개수가 100만 개이더라도 나눗셈을 시도하는 소수 p의 개수가 얼마 안 되기 때문에 큰 걱정이 없습니다. 대회 시작 9분 후 퍼스트 솔브.

A. 3의 배수 / BOJ #16561

의외로 이 문제는 처음에 문제를 잘못 이해해서 고민을 많이 했어요. 자연수 3개로 분할해야 하는데 그걸 놓쳐서 그냥 자연수를 분할하는 갯수로 이해해버렸어요. 아무튼.

문제를 읽어보면 알겠지만 n이 3의 배수인 건 별 의미가 없죠? 사실 $\frac{n}{3}$을 자연수 3개로 분리하는 것과 같습니다. 근데 순서가 상관이 있다고 하네요. 어떻게 분리해야 될까요?

일단 3을 3개로 분리하는 건 1 + 1 + 1 하나밖에 없죠. 4를 3개로 분리하는 건 2 + 1 + 1을 순서를 적절히 바꿔서 3개가 나오고, 5를 3개로 분리하는 건 3 + 1 + 1과 2 + 2 + 1을 순서를 적절히 바꿔서 6개가 나오고… 그러면 이 문제는 공 $\frac{n}{3}$개를 3개의 서로 다른 상자에 각각 1개 이상씩 나눠 담는 경우의 수를 구하는 문제로 생각할 수도 있겠네요! 이건 중복조합 $$\textstyle\left\langle{3\atop {\frac{n}{3}-3}}\right\rangle\left(=_{3}\mathrm{H}_{\frac{n}{3}-3}\right)$$과 같습니다. 계산해 보면 간단히 $$\frac{(\frac{n}{3}-1)(\frac{n}{3}-2)}{2}$$이고, 이렇게 풀면 AC를 받아요!

물론 저는 고등학교 확률과 통계는 잊어버린 지 오래이기 때문에 3, 4, 5, 6을 분할해 보고 각각 1, 3, 6, 10개가 나오는 걸 보고 ‘이건 뭔가 nCr이겠구나!’ 싶어서 바로 그렇게 짰더니 맞았습니다. 대회 시작 14분 후 정답.

B. 친구비 / BOJ #16562

간단한 그래프 문제였어요. 연결 요소들을 찾고, 그 중 최소인 값들만 다 더해주면 됩니다. 연결 요소들은 BFS로 찾든 DFS로 찾든 별 상관은 없고, 모든 노드를 한 번씩만 방문하기 때문에 $O(N)$으로 뚝딱 풀려요. 이 합이 K보다 클 때만 “Oh no”를 출력하면 됩니다. 대회 시작 21분 후 정답.

D. 히오스 프로그래머 / BOJ #16564

팀 목표레벨 T를 0과 $2 \times {10}^{9}$ 사이에서 이진 탐색하는 방식으로 풀었어요. 사실 대회에서는 T의 이론적 최댓값을 신경쓰지 않고 0과 ${10}^{12}$ 사이에서 탐색했어요. 왠진 모르겠지만 범위를 어디까지 잡아야 될지 감이 잘 안 와서..

탐색할 때마다 목표 레벨이 T일 때 올려야 하는 레벨 총합 $\sum \mathrm{max} (0, T-X_i)$를 K와 비교하는 방식이었어요. N이 1백만 이하이고 K가 10억 이하라서 int로 풀면 터지겠죠? 당연히 long long을 썼습니다.

올려야 하는 레벨 총합을 구하는 건 $O(N)$이고 목표 레벨 T를 탐색하는 건 $O\left(\log\left(2\times{10}^{9}\right)\right)$입니다. 따라서 이 문제도 선형 시간 안에 풀립니다. 이진 탐색 범위를 잘못 잡아줘서 한 번 틀리고, 대회 시작 32분 후 퍼스트 솔브.

E. N포커 / BOJ #16565

확률과 통계 문제입니다. 문제지에 숫자를 많이 끄적이게 됐던 거 같아요.

7개를 고를 때를 예로 들어볼게요. 문제의 그림에서 13개의 줄 중 세로줄을 한 개 고르고, 나머지 48장의 카드 중 3장을 고르면 됩니다. 이 때에는 경우의 수가 총 $$\binom{13}{1}\binom{48}{3}$$가지에요.

하지만 11개를 고른다면 어떻게 될까요? 일단 문제의 그림에서 세로줄을 한 개 고르고, 나머지 48장의 카드 중 7개를 고른다고 치면 고른 7장의 카드 중에 또 세로줄을 만드는 경우가 생길 수도 있어요. 이 때엔 세로줄을 두 개 고르고, 나머지 44장의 카드 중에 3장을 고르는 경우를 빼면 됩니다. 경우의 수는 $$\binom{13}{1}\binom{48}{7}-\binom{13}{2}\binom{44}{3}$$가지가 나오겠네요!

15개를 고른다면 어떻게 될까요? 위와 같이 생각한다면 중복을 빼 줄 때 세로줄이 3개 나오는 경우도 빠져버립니다. 따라서 세로줄이 3개 나오는 경우의 수를 다시 더해준다면 $$\binom{13}{1}\binom{48}{11}-\binom{13}{2}\binom{44}{7}+\binom{13}{3}\binom{40}{3}$$가지가 나옵니다.

이쯤 하면 대충 감이 오죠? 일반화할 수 있을 것 같아요. 위의 패턴을 보면 임의의 n에 대해 우리가 구하고자 하는 경우의 수는 $$\sum_{i=1}^{\lfloor n/4 \rfloor} {(-1)}^{i-1} \binom{13}{i}\binom{52 – 4i}{n – 4i}$$가지가 될 것 같고, 실제로도 그래요!

이항 계수를 구하는 게 또 문제인데요, 팩토리얼을 구해 나누는 걸로는 이항 계수를 구할 수가 없어요. long long의 범위는 $2^{63}-1$까지인데, $21! \approx 2^{65.46} $에서 이미 이 범위를 아득히 넘어버리기 때문에 위에 나온 $\binom{48}{7}$을 구하는 건 생각조차 할 수 없을 거에요. long double은 범위는 long long보다 크긴 한데, 엄청 커지면 정확도가 long long보다 못한 것도 있고요. 대신 재귀식 $$\binom nk = \binom{n-1}{k-1} + \binom{n-1}k$$을 쓰면 n ≤ 52, k ≤ 52, k ≤ n에 대해 이항 계수를 다이나믹 프로그래밍으로 전처리해 둘 수 있을 거에요. 숫자가 너무 커질 수도 있간 한데, 어차피 결과는 10,007로 나눈 나머지만 출력하면 되니까 모듈로 연산의 성질을 이용해 전처리할 때 모든 이항 계수는 10,007로 나눈 나머지를 저장하면 돼요.

이렇게 전처리해 둔 이항 계수를 이용하면 n이 얼마가 들어오더라도 최대 13개의 항만 더해서 $O(\lfloor n/4 \rfloor)$에 해결 가능합니다. 식을 잘못 짜서 맞기 전에 3번 틀리고, 대회 시작 1시간 1분 후 퍼스트 솔브.

F. 카드 게임 / BOJ #16566

나중에 알았는데, 이 문제는 원래 Champion 디비전의 F번으로 계획되었다고 합니다. 하지만 이 문제가 더 쉽다고 생각해서 Champion의 F랑 Master의 F를 바꿨다는 것 같습니다. (어쩐지 카드 문제만 연속으로 두 개가 나오더라고요)

여하튼, 처음엔 ‘아 이거 바이너리 서치 트리인가..?’ 하고 한 10분 동안 바이너리 서치 트리를 구현해 보려고 했는데, 트리 연습을 진짜 너무 안 했기 때문에 (게다가 위에서 언급했듯이 Kotlin 하느라 C++에서 struct 짤 일이 별로 없었기 때문에) 포기하고 ‘뭐 어차피 원래 목표는 5등 안에만 드는 거였으니까’ 하고 던지듯이 풀었어요. 근데 맞았습니다!! 이건 데이터가 좀 약했던 것 같아요.

일단 민수가 가져간 카드들을 정렬합니다. 그리고 M의 카드가 쓰였는지 안 쓰였는지 저장하는 플래그 배열을 하나 만듭니다. 이제 철수가 내는 카드의 값을 x라고 할 때, 민수의 카드에서 lower_bound로 x + 1을 찾아봅니다. 이게 아직 안 쓰였다면 바로 출력합니다. 쓰였다면 안 쓰인 카드가 나올 때까지 index를 하나씩 증가시켜 보고, 찾으면 출력합니다.

사실 이 방법은 최악의 경우 $O\left(K^2\log M\right)$이고 TLE가 나도 이상하지 않은 복잡도에요. 그냥 운이 좋았던 것 같아요! 문제를 제대로 풀었다고 말하긴 힘들 거 같지만 여하튼 대회 시작 1시간 47분 후 퍼스트 솔브.

정해는 index sort를 사용하는 것이라고 합니다. M ≤ N ≤ 4,000,000이라서 가능한 것 같은데, 정해로 다시 풀어봐야겠어요.

---

6문제를 전부 풀어 Master 디비전에서 우승했어요. 참가자로서 아마 처음이자 마지막일 교내대회에서 우승한 것이라 개인적으로도 의미가 큽니다. 참가자, 출제진 모두 수고하셨습니다. 좋은 대회 만들어 주신 운영진 분들께 감사합니다!

코딩하다 중간에 백스페이스가 안 먹어서 고생했지만 (나중에 알고 보니 일부 유학생 분들께서 키보드 언어 설정을 자국 언어로 바꿔 두셔서 그랬다는 것 같습니다) 오랜만의 오프라인 대회 너무 재밌었어요. 내년부터는 출제진이 될 것 같은데, 저도 노력해서 모두 재밌게 즐길 수 있을 만한 대회를 만들어보겠습니다 😊

수고하셨어요! 🎈