ACM-ICPC Seoul Internet Preliminary 2019

스코어보드가 아직 공개되지 않았지만, 교내 대회의 결과가 이미 나온 시점이라 대회를 회고하고자 합니다.

 

채점 도중에 Codeforces에서도 일어나지 않았던 채점 서버 다운이라는 정말 거대한 이슈가 있었습니다. 시작한지 30분 후에 제출한 소스코드의 AC/WA여부가 제출 1시간 30분 후인 2시간 후에 제공 되는 일이 있었습니다. 그거 말고도 채점이 지연되자 채점서버를 전부 닫아버리는(...) 일도 있어서 어느 시점 이후로부터는 채점이 전혀 되지 않았습니다.

 

.. 뭐 이런 일도 있는 법인가 봅니다.

출제된 문제들

ProblemSet

 

등록을 제외한 몇 문제는 굉장히 난이도가 낮았지만, 그 문제들을 제외하고는 체감 난이도가 굉장히 높아서 당황했다. 개인적으로 느낀 난이도를 기준으로 정렬해서 서술해보겠습니다. 저희가 대회를 진행했던 Time Line은 아래에 따로..

풀었던 문제는 풀었던 문제의 해설을, 풀지 못한 문제는 이렇게 하면 되지 않았을까 하는 생각을 적어봅니다.

I. Registration

아이디와 비밀번호를 그대로 출력하는 문제였다.

 

B. Balanced String

0과 1로 이루어진 이진 문자열 중, 첫 번째 문자를 포함하는 모든 부분문자열이 모두 0과 1의 총 개수가 차이가 1 이하인 문자열을 Balanced String이라고 한다. 문자열 $S$의 부분 문자열 중, 1부터 $i$번 문자 까지의 부분문자열을 $S_{i}$라고 해보자.

$|S_i|$가 홀수라면 반드시 0과 1중 한 개의 개수가 많을 것이다. $|S_i|$가 짝수라면 0과 1의 개수가 같을 것이다. 그럼 부분문자열의 길이가 홀수일때는 반드시 0과 1중에 개수가 적은것이 와야 문자열 안의 0과 1 개수의 차이가 1 이하로 줄어들 것이다. 그럼

$s[i]$에서

i가 홀수라면, $s[i-1]$에서 1가지 문자만 붙일 수 있게 된다, 즉 $s[i]=s[i-1]$.

i가 짝수라면, $s[i-1]$에서 0또는 1, 즉 2가지 문자를 붙일 수 있게 된다. 따라서 $s[i]=2*s[i-1]$이 된다.

 

즉, 이 문제는 쉽게 정리하자면 $2^{(n+1)/2} mod 16769023$을 출력하는 문제라고 할 수 있다.

저렇게 생각하지 않더라도 n이 6일때까지만 직접 해본다면 규칙을 쉽게 파악할 수 있다.

C. Byte Coin

한때 유명했던 코인에 관한 문제이다. 시간에 따른 코인의 가격이 이산적으로 주어졌을 때, 언제 사고 언제 파는것이 최대의 이익을 가져다 줄 수 있는가에 대한 문제이다. 그리디하게 저점에 팔고 고점에 팔아야한다. 가격이 1자로 유지되는 지점의 극점 처리가 어려워서 앞에 들어온 숫자와 다음에 들어온 숫자가 같은 경우 입력을 받지 않고 진행했다. 어차피 $N <= 15$라서 그냥 $O(N^2)$의 무식한 방법으로 극대 극소를 구해줘도 상관 없었겠지만 그게 더 귀찮을 것 같아서 적당히 처리한 후 구해줬다.

Output에 'Beware that even though the initial amount of money W is not so big but the final amount of money can be very large.'라는 글이 있어서 최대 얼마까지 떡상할 수 있을까 하는 생각에, 1->50->1->50->...->1까지 반복한다면 최대 50^7(7.8125 * 1e11)까지 증가할 수 있기 때문에, long long을 사용하게 되었다. 이 지문이 없었다면 1번 틀린 사람들이 많지 않았을까?

H. Four Squares

라그랑주가 발견한 사실을 이용해 주어진 자연수를 4개 이하의 최소 개수의 제곱수의 합으로 표현하는 방법을 찾으라는 문제였다. 개수를 찾으라고 하는 문제다. $t[i]$ =  자연수 $i$를 제곱수의 합으로 표현하는 최소의 방법이라고 해보자.

먼저 $t[i]=INF$로 초기화를 해 주도록 하자.

$i=0$부터 시작해서 $i+j^2 (1 <= i+j^2 <= n)$에 대해 $i+j^2$를 계산해보자.

앞에서 미리 최소 개수를 구해뒀다면(예를 들어, 4+3^2는 9+2^2보다 먼저 계산된다) 그 값을 사용하면 될 것이고, 그게 아니라면 $i$에 $j^2$를 더한 값이 될 것이므로 $t[i+j^2] = t[i]+1(j^2)$이 된다. 이것을 반복해주면 합이 $n$이 되는 최소 제곱수의 최소 개수를 전부 구할 수 있게 된다.

for(int i=0; i < 50001 ; i++){
    for(int j=1;i+j*j <= 50000; j++){
        t[i + j*j] = min(t[i +j*j], t[i]+1);
    }
}

 

L. Two Machines

굉장히 유명한 스케쥴링 DP였던 것 같다. 시간 t에 대해, a를 선택하거나 b를 선택하는게 나은지 판단해서 dp 값을 갱신하면서 풀면 되는 문제였다.

 

D. Canal

2차원 평면 상의 300,000개의 모든 지점에 대해서 임의로 그은 수직선 2개에 대한 거리의 최대값의 최소값을 구하는 문제이다.

맨 처음엔 어차피 $y=x, y=-x$를 기점으로 x축에 가까울 수 밖에 없는 점과 y축에 가까울 수 밖에 없는 점을 나눠 생각했었는데 이 방법은 반례가 반드시 생겨서 버렸었다.

잘 생각해보니 $x,y$축을 각각 기준으로 거리가 가장 멀리 떨어져있는 점 두 개의 거리를 $L$이라고 했을 때, 이를 이용해 Parametric Search를 사용해서 $L$을 좁혀나가면 풀 수 있을 것 같았다. 

 

F. Dryer

$T$에 대한 $m_i$의 직선을 그려서 주어진 $k$의 개수에 따라 건조 시간이 최소가 되게 분리하는 문제였다. n이 1000개라서 x축에 접하는 지점에서 T가 1000개쯤 생기게 된다. 이걸 사용해 빨래를 잘 분류하면 되는 문제같았다........ 어느 T를 선택하게 되면, 그 T뒤에있는 빨래들은 고려 안해도 되는 문제이고 결국 어느 T에 대해 칸막이를 2개 세우는 문제이므로 1000개 * 1000개의 경우의 수를 고려하면 $O(N^2)$에 풀 수 있지 않았을까..?

 

A. All You Need is Dating

지문이 길어서 처음엔 던지고 시작했는데 해석해보면 블라인드 매칭을 위해 각각 m IC학생 ,n명의 Pㅊ 학생들에 대한 다음의 제약조건을 만족하면서, 최대 매칭을 구하는 문제였다. 처음엔 이분매칭이라고 생각했는데 제약 조건을 읽어보면 단순한 이분 매칭이 아니었다.

(1) 각각의 학생은 preferred partner가 있고.

(2) IC 학생들이 데이트가 가능한 하한, 상한이 있었으며 - 사실 여기서 L-R Maximum Flow라는걸 눈치 챘다.

(3) PC 학생들에게도 데이트 하한과 상한이 있다.

 

이제서야 n,m이 이렇게 작았던 이유가 떠올랐다. IC가 있는 쪽을 source, PC학생들이 있는 tank라고 해서 유량의 하한과 상한을 지정해준 후 Maximum Flow를 구해준 후 출력하면 될 것 같다......

E,G,J,K.

이 친구들은 손도 대지 못했다. J는 그나마 맛이라도 봤는데 DP같았다.

타임라인

I. Registration(0:03)

등록 코드를 작성한 후 제출하려고 했으나 웹서버 다운으로 3분에 AC

B. Balanced String(0:24)

보자마자 경우의 수 DP겠거니 해서 바로 내가 잡았는데, 몇번 해보니 $2^{(n+1)/2}$를 구하는 문제라 빠르게 풀고 여러가지 확인. 대회중엔 $a^b%$를 $O(log b)$에 계산할 수 있는 Fast Exponential(그냥 분할정복..)을 했으나 n이 작아서 그럴 필요가 없었다. AC를 확신하고 웹서버가 정상으로 돌아올 때까지 대기. 제출 후 AC

H. Four Squares(0:24)

문제가 쉬워보여서 옆에 있는 후배에게 던졌다. 후배가 빠르게 해결했으나나 마찬가지로 웹서버 장애로 대기하다가 24분에 제출, AC.

C. Byte Coin (~0:40)

얘는 같이 하던 친구가 바로 집어가서 이거 그리디네~ 하고 풀었다. 여러 개 돌려봐도 맞다길래 제출. 근데 이때부터 채점 결과가 안온다..

L. Two Machines(0:50~)

스케줄링 회사, A, B보고 바로 아 이거 DP네 하고 집었다가 계속 답이 나오지 않아 다른 친구들에게 pass.. 그리고 문제가 길었던 A를 잡았다. 작년에 문제 길다고 안읽었다가 다익스트라로 풀리는 로봇문제를 못풀었기 때문에..

 

A. All you need is dating(1:10~)

처음에 블라인드 데이트 보고 어 이분매칭아냐? 개꿀이네 이거; 했다가 밑의 제약조건을 보고 또 다른게 떠올랐다. 상한- 하한이 정해져있는 바이퍼타이트 그래프에서 최대 매칭을 구하는 문제였다. 바로 L-R Maximum Flow가 떠올랐는데 아쉽게도 이걸 해결하는 알고리즘이 팀노트에 없었다. 어제 인터넷 뒤져보다가 설마 이게 나오겠어 하고 넘어갔는데.. 하지만 알아도 어차피 못풀었을거 그냥 버리고 D를 잡았다.

D. Canal (~1:30)

처음엔, 문제 이해를 잘못해서 어떤 점에서 다른 점들에 도달하는 거리의 최대값의 최소값을 구하라는 문제인줄 알고 어 이거 UCPC 기출이네 개꿀 ㅎㅎㅎㅎ 하고 있다가 아무리 생각해도 예제처럼 답이 적게 나올 수 없어서 일단 친구한테 던지고 F를 봤다.

F. Dryer (~2:03)

어 이거 냅섹처럼 생겼네 하고 봤다가 읽어보니 냅색이 아니었다. k가 3이라 최대 3종류로 분류하면 된다! 라는 생각에 할만하겠는걸 이라고 보고 (T,  m) 그래프를 그려봤다. 그래프를 그리고 나서 얘를 어떻게 분류한담..  하고 고민하던 사이 C번 문제의 채점 결과가 떴다. C가 WA??????

C. Byte Coin (~2:10)

서로 각자 L, D, F풀다가 C가 WA 떠서 셋다 멘붕하고 일단 내가 C를 잡았다. 일단 가격이 유지되는 점을 제거(항상 뾰족한 구간만 존재하게) 하기로 하고 (이게 문제인 줄 알았다) 일단 제출.

제출 직후 여러가지 코너케이스를 넣어봤는데.

1 1

1

을 넣어봤더니 답이 11이 출력되었다. 셋다 멘붕와서 코드를 다시 읽어보니. 처음 가격에서 증가하는 구간이 하나도 없을 경우에는 코인을 사지 않고 W를 출력하는걸로 처리를 이미 해놨으나, W를 출력한 다음 코드의 맨 마지막에서 W를 다시 한 번 출력한다.

그래서 1이 아니라 11이 출력되었던 것. 빠르게 고치고 2:11에 답을 제출했다. AC를 확신했지만.. 패널티도 엄청난데다 채점이 안되고 있다. 대회 시간이 총 30분 연장되었다.

D. Canal (~3:08)

처음엔 Canal이 점 인줄 알았는데 그게 아니라는걸 다시 문제를 천천히 읽어보면서 깨달았다. y=x,-x로 점을 나눠서 위쪽과 아래쪽에 있는 점들은 y축에 가까우니까 y축으로 가는 거리를 계산하고, 좌 우에 있는 점들은 x축으로 가는 거리를 계산해 가장 멀리있는 점 들 사이에 canal을 만드는 전략을 세웠다. 예제가 둘 다 제대로 나오고, 만들어본 예제도 제대로 나와서 제출. (WA..)

 

L. Two Machines (3:15)

후배와 친구가 풀고 제출했다.

J. StarTrek (~3:30)

나와 친구는 J를 잡았다. 둘다 열심히 J에 대한 DP식을 세웠는데 결국 코드를 완성하지 못하고 스코어보드의 재미를 위해 A와 J에 제출을 했으나 A는 No input, J는 Too late를 받았다 (ㅋㅋ..)

 

...

 

L. Two Machines (5:00)

컴파일 에러란다..

 

 

마지막 ICPC라서 정말 재밌었다. ICPC를 더이상 나오지 못하게 되었는데 이제 Problem Solving을 하는 목적이 사라져버려서 덜하게되지 않을까 싶다. 조금만 더 빨리, 열심히 PS를 했다면 본선은 한번 더 나갔을텐데 조금 아쉬운 대회였다. 이번은 대회 환경도 그렇고 생각보다 L번같은 문제에서 퍼포먼스가 안나와서 고생했다.

 

그래도 개천절날 나와서 연습해준 TheQuickBrownFox 팀원들도 고맙고 재밌었던 대회였다.