Wednesday, May 28, 2014

SRM 622

오랜만에 말려서 다 틀린 셋. Easy는 걍 말려서 헉헉 거리다가 결국 틀렸고 Medium은 몇 초를 남겨두고 다 짰는데 제출이 안됬다. 알고보니 아레나에서 컴파일을 안해서 제출이 안됬었음ㅠㅠ

Easy
두 정점 사이에 최단거리로 갈 때, 그 경로 상에 있는 간선들을 '사용'했다고 한다. 간선들이 T번 이상 사용된 걸 '불안'하다고 하는데 불안한 간선들의 가중치 합을 출력하시오.

플로이드로 풀릴 것 같아서 곧바로 짰는데 생각이 꼬여서 말리고 다익스트라로 급하게 짰다가 틀림ㅋㅋ 차근히 생각해보면 우선, 최단경로부터 다 구한 다음에 d[a][b] == d[a][i]+e[i][j]+d[j][b]인 e[i][j]를 카운팅해주면 됨. N<=50이라서 O(N^4)에도 너끈히 나온다.

Medium
그리디 알고리즘. 짤라내야하는 거 다 잘라내고 최대한 남겨둔 다음에 위로 올려서 재귀적으로 계산. 증명은 귀류법으로 됨.

Hard
안 읽어봤음.

Tuesday, May 27, 2014

2005년도 KOI 지역본선 고등부 5번

Problem Link

자연수 N의 양의 배수 집합을 S라 할 때, S의 원소 중 각 자릿수를 이루는 숫자의 종류가 가장 적은 수의 집합을 T라 하고, T의 원소 중 최솟값을 구하는 문제를 풀었는데...
T에서 숫자의 종류가 항상 2이하가 되는 것 같다.

만약, N이 2나 5의 배수가 아니라면 S에서의 숫자의 종류는 항상 1개이다.
1,11,111, 111111 같이 1들로 이루어진 수들은 무한개이므로 이 수들 중 N으로 나눈 나머지가 같은 두 수가 항상 존재한다. 그 두 수의 차이는 11111....* 10^k이고 N으로 나누어떨어진다. 즉 11111 .... *10^k = Q(몫)*N이고 N은 10의 배수가 아니므로 11111....은 N으로 나누어떨어진다. N이 2나 5의 배수라도 앞서 말한 10^k을 나누고 곱함으로써 연속된 숫자들로 나타날 수 있게 만들 수 있고, 그 뒤에 임의의 개수의 0을 붙여서 N으로 나누어떨어지게 할 수 있다. 따라서 모든 수의 T에서 숫자의 종류는 1개 또는 2개이다. 몇 가지를 생략하고 적어놓아서 엄밀하지않아 보이지만 뭐...ㅋㅋㅋ 이와 비슷한 문제를 접하면 이런 쪽으로 생각하면 되겠다.

Source Code

Monday, May 26, 2014

acmicpc.net 3103 - 순열의 순서

Problem Link

Croatian Highschool Competitions in Informatics 2010 Final Exam #1 - ASISTENT

1부터 K까지의 숫자로 이루어진 길이가 K인 순열 X에서 N개의 쿼리에 대해 A[i]번째와 B[i]번째(1 ≤ i ≤ N)의 숫자를 Swap한다. 각 쿼리에 대해서, 모든 가능한 순열을 정렬했을 때, 순열의 순서가 몇 번째인지 출력하는 문제이다.

우선, 어느 순열의 순서는 각 X[i]마다 (X[i]>X[j](i<j)인 j의 개수 : P(i)) × Factorial (K - i)을 더해줌으로써 구할 수 있다. (K log K)

A[i]번째와 B[i]번째를 스왑하는 경우를 생각해보자.

1 ... X(A[i]-1) X(A[i]) X(A[i]+1) ... X(B[i]-1) X(B[i]) X(B[i]+1) ... K

A[i]번째와 B[i]번째를 제외한 A[i]+1부터 B[i]-1번째까지의 P(j)들은 최대 1까지만 증가할 수 있다. 그리고 1~A[i]-1번째와 B[i]+1~K번째 P값은 변화가 없다. 따라서 X의 첫번째 원소부터 차례대로 보면서, P를 계산할 BIT와 Factorial을 계산할 BIT 2개를 update시켜주면서 각 쿼리에 가감해야할 값을 계산해주면 된다. 시간복잡도는 O(K log K + N log K).

Source Code