Codeforces Round #610 (Div. 2)

코드포스르 꾸준히 참가하고는 싶으나 참가할 수 있는 시간대가 거의 없다.ㅠㅠ

시간이 나길래 Codeforces Round #610 (Div. 2) 를 virtual contest로 참가해보았다. 결과는 A,B1,B2만 풀었다.

C번은 '-1' 하나때문에 결국 시간내에 못 풀었다. 

대략적인 풀이는 다음과 같다.

$Ti$을 오름차순으로 정렬하고 각 $Ti$에 해당하는 문제까지 푸는데 걸리는 시간을 $solved[i]$배열에 저장하자.

이 때 $solved[i]$까지 풀었을 때 시험을 종료해도 되는지 살펴보지만 이때 주의할 것은 앞으로 남은 문제 중에

다음 $Ti$ 가 오기 전까지 추가로 얼마나 풀 수 있는지 고려해야 한다. 자명히 easy문제부터 해결해야 될 것이다.

 

위에서 말한 '-1'은 해결한 $Ti$와 다음 $Ti$사이 시간에서 1을 빼줘야하는 뜻이었다. 다음 $Ti$가 와버리면 그 문제까지 해결해야 하니까 말이다.

코드는..

http://codeforces.com/contest/1282/submission/68027192

 

D. Enchanted Artifact

interactive problem이다. 코포에서 interactive문제는 처음이었고 첨에는 문제가 무슨 뜻인지 몰라서 답지를 보고 공부했다.

문제는 길이 $n$짜리 문자열$s$을 구하는 것이다. 한번의 질문으로 문자열 $q$를 물어본다면 $q$ 가 $s$가 되기 위한 최소 변환(삽입, 삭제, 교환) 횟수를 알려준다. 이때 질문은 최대 n+2번 할 수 있다. 

따라서 처음 두 질문으로 a와 b의 개수를 구할 수 있다. 바로 길이 300짜리 a로만 이루어진 수열을 물어보고 다음에는 길이 300짜리 b로만 이루어진 수열을 물어보는 것이다. 그 다음에는 얻은 길이에 해당하는 a로만 이루어진 수열에서 맨 앞부터 하나씩 b로 바꿔가면서 변환 횟수가 증가하는지 알아보는 것이다. 만약 변환 횟수가 늘어나면 해당 index는 a일 것이고 아니면 b이다. 이런 논리이다.

 

http://codeforces.com/contest/1282/submission/68035165

 

E. The Cake Is a Lie

내 기준 가장 재밌는 문제였다. 하지만 푸는데 거의 3시간 넘게 걸렸다.

다각형을 조각조각낸 삼각형의 각 꼭짓점을 통해 다각형을 잘라낸 순서를 알아내는 것($q$)와

다각형의 정점 배열을 알아내는 것($p$) 이렇게 두 문제가 합쳐져 있다.

먼저 $p$부터 구해보자.

각 삼각형마다 변이 3개씩 있으므로 한 변을 이루는 두 정점 번호로 이루어진 쌍 (a,b) 에 연결된 삼각형을 서로 묶자. map과 vector를 이용하면 된다. 이렇게 하면 어떤 삼각형끼리 인접해있는지 알 수 있다.

그리고 위상정렬처럼 삼각형 한 개와만 인접해있는 삼각형부터 잘라내고 (잘라낸 삼각형과의 인접 정보는 끊는다) ..계속해서 아무와도 인접하지 않은 삼각형이 남을 때까지 진행한다.

 

이제 $q$를 구할 차례이다.

앞에서 $p$를 구할 때와 다르게 이번에는 인접한 삼각형 정보를 통해 dfs를 진행해야 한다. 

처음 시작이  삼각형 [1,2,3]이라고 생각해보자.

$set[1]={2,3}$

$set[2]={1,3}$

$set[3]={1,2}$

처럼 설정해놓자. 그리고 다음 인접한 삼각형이 만약 [2,3,5]이면

2와 3의 연결을 끊고 2,5와 3,5의 연결을 추가하면 된다.

$set[1]={2,3}$

$set[2]={1,5}$

$set[3]={1,5}$

$set[5]={2,3}$

처럼 변할 것이다. 이렇게 dfs가 종료되면 각 정점마다 2개씩 이웃 정점이 저장될 것이다. 따라서 이 정보로 차례대로 다시 dfs를 하면 $q$를 구할 수 있다.

 

시간초과가 안나게 정점개수 $n$에 따라서 지정한 set이나 vector를 초기화해줘야 한다.

 

http://codeforces.com/contest/1282/submission/68097966