TopCoder SRM 579 Div1

05. 19. 2013.

아깝다 ㅋㅋ 450짜리도 생각까지 제대로 했는데,

무언가 구현에서 문제가 발생한건지 sysfail ㅜ_ㅜ

어쨌든 오랜만의 성공적인 매치! 레이팅이 1494가 되었다.

이제 다시 옐로로 올라가야지!

250

워드프로세서를 이용해서 vector <string> 에 적은 대로 한 줄씩 출력하고싶다.

(vector의 크기 <= 50, 각각의 길이 <= 50)

그런데 이 워드프로세서는 백스페이스가 없고(...), 버퍼에 한 글자 붙이기,

버퍼를 지금까지 존재했던 모든 버퍼의 상태중 하나로 되돌리기,

그리고 버퍼를 한 줄로 출력하기(단, 버퍼는 비워지지 않는다)

 총 3가지의 기능만 지원한다.

최소한 버튼을 몇 번 눌러야 원하는 출력을 만들 수 있을까?

(처음에 버퍼는 빈 상태이고, 되돌리기시 버튼 2번을 눌러야 하며,

출력시 한 번을 눌러야 하고, 당연히 한 글자 붙이기도 버튼을

한 번 눌러야 한다)

N이 컸다면 어땠을지 모르겠지만 N이 작기때문에 마구 돌렸다.

이 문제의 핵심은 Longest Common Prefix, 최장 접두사이다.

지금까지 존재했던 모든 버퍼중 가장 긴 접두사를 공유하는 버퍼와

지워지지 않은 상태인 현재 버퍼와, 비어있는 버퍼 중 하나를

선택해서 그 뒤에 한 글자씩 붙여나가는게 최적이기 때문이다.

뭐 여기까지 했으면 이제 N^2*M (M:길이) 의 무식한 알고리즘으로도 pass!

450

총 N ( N <= 50 )개의 가게가 있고, 그 가게들중 0 ~ M - 1 (M <= 16) 번째 가게가

Interesting한데, 그 가게들의 개점/폐점 시간과 구매하는데

걸리는 시간이 주어지고, 가게들간에 존재하는 양방향 도로가

소요 시간과 함께 주어질때, 최대 몇 개의 물건을 구매할 수 있을까?

(단, 시작은 N-1번 도시에서 하고, 물건 구매는

개점 <= (도착시간) <= 폐점 시간에 할 수 있고, 구매하는 시간 동안은

움직일 수 없으며, 한 가게에서는 한 개의 물건만 살 수 있다)

Floyd-Warshall등등의 최단거리 알고리즘을 이용해서 최단거리 배열을 만들고,

M * (1 << M) 가지의 경우에 대해 가능한지 불가능한지 여부를 알아내서

가능하면 bitmask의 1인 비트의 개수가 답의 후보가 된다.

가능 / 불가능은 그냥 TSP같은 dp를 써서 bitmask에서 1인 가게들을 들러서

물건을 사고 현재 i번 도시에 있다고 할 때(즉, 마지막 방문이 i번 가게),

소요 시간을 구하는 식으로 짜면 된다. 500이 아니라 450이라 그런가 참 쉽죠?

근데 난 왜 이걸 알면서도 틀렸지 ㅜㅜ..

1000