Sunday, August 24, 2014

20140824

Codeforces Round #151(Div. 2) : All solved

내가 AC 받았던 소스코드들

Problem A

Problem B

Problem C

Problem D

Problem E

E에 관해서 정리를 해보면

1) BFS로 numbering

2) 각 node마다 2^k 위의 parent를 구함

3) 쿼리 (v, k) : depth[v] + k의 깊이에 해당하는 노드 L(i)~R(i)에 대해 이분탐색을 하면서 k 깊이 위의 부모가 v인지 검사하는 식으로 구간 [L, R]을 구함.

4) 구간들을 Bucket Sorting하고( [L/루트(N)]*루트(N) + [R/루트(N)], [ ] : 가우스 기호 ) acmicpc.net 8462 '배열의 힘' 문제 솔루션 대로 쿼리에 대해서 답을 구한다.
(acmicpc.net 8462 솔루션 링크)

전체적인 시간복잡도는 O(Q log^2 N + N루트(N))이 된다.

ALPS 회원들한테 문제를 공유하고나서 좀 더 생각해보니, 쿼리가 만약 (r, v, k) : 루트가 r일 때, 쿼리 (v, k)로 루트가 입력받을 때로 지정된 게 아니라 쿼리에서 바뀔 수 있다면, 에디토리얼에 있는 BIT나 세그먼트 트리를 써야지 풀릴 것 같다. 루트가 바뀌면 구간이 [P,P]+[L,R]꼴이 되는데 [P, P]처리가 안되네 ㅋㅋ

자꾸 연습을 div2만 돌고 있는데, div1에서는 보통 많아야 2~3문제 밖에 못 푸는데 그게 div2랑 겹치다보니 ㅋㅋㅋ... 자꾸 연습하다보면 div1에서 편하게 연습 돌 때가 오겠지ㅎ

Tuesday, August 19, 2014

20140817 ~ 20140819

1. Baekjoon Online Judge 모의고사 : All solved


나랑 경근이형만 첫날부터 시작하고 나머지 사람들은 둘째날부터했다. 내일까지 계속 진행된다. F번 같은 건 한번에 맞추었어야한다. int 배열로 잡아야할 걸, char로 잡는 실수를 했다.

2. Codeforces Round #261(Round 2) : All solved

내가 AC 받았던 소스 코드

백준 저지에서 모의고사를 풀던 중, min-plus algebra라는 걸 명우를 통해서 알게되었다. 내가 대회 도중에는 직관적으로 플로이드 비슷한 Loop를 떠올리면서 행렬 곱을 해주어서 log T에 계산했었는데, 그게 알고 보니 수학적인 베이스가 기초된 정리였다.
min-plus algebra Link
행렬 곱을 함으로써 A^T을 계산하던 걸, 서로 다른 두 행렬의 원소를 Plus Calculation한 걸 min 값으로 취하는 연산으로도 같은 방식을 적용할 수 있다. 사실 A^T을 A*A*A*....해보면 차이가 없다는 걸 알 수 있는데, 거듭제곱 꼴이 과연될까 싶었는데 대회 도중에 해보니까 되더라 ㅋㅋ
비슷하게 max-plus algebra도 가능한 경우가 있으니 참고하자.

Saturday, August 16, 2014

20140815 ~ 20140816

2014 KOI 지역본선 중등부4번/고등부3번
Baltic OI 2009 4번
Baltic OI 2014 2번
NOI, China 2012 Day1 1번
IOI 2005 Mean Sequencec
IOI 2010 Quality
ACM ICPC 2012 Japan Tokyo A번
ACM ICPC 2013 Japan Aizu A번
ACM ICPC 2013 Japan Aizu G번 (복습이 필요...ㅠㅠ)

월간 텝스 풀어보고 복습하느라 PS 거의 못함ㅠㅠ

내일은 시간 내서 GA 모의고사 한 번 쳐봐야겠다.

Thursday, August 14, 2014

National Olympiad in Informatics, China, 2006 Day 2, Problem 1 - Maximum Profit

Problem Link

정점 n개와 간선 m개가 있는데, 정점에는 음의 가중치가 있고, 간선에는 양의 가중치가 있다. 이 때 정점을 몇 개 고르면, 그 정점들로 구성되는 간선을 모두 선택할 수 있다. 정점을 잘 골라서 정점들과 간선들의 가중치의 합을 최대화하는 문제이다.
MCMF인 것 같지만, Min-Cut 문제이다. 이분 그래프 구성법이 독특하여 매우 어려운 문제였는데, 왼쪽에는 간선들을, 오른쪽에는 정점들을 두고
1) 소스에서 간선들에는 유량을 간선의 가중치만큼 준다.
2) 간선에서(u-v면 i->u, i->v) 정점들에는 유량을 무한대 준다.
3) 정점에서 싱크에는 유량을 정점의 가중치만큼 준다.
위 처럼 이분 그래프를 구성하고 max-flow 돌린 다음에, 간선들의 가중치 합에서 maxflow값을 빼주면 됨. 가중치의 합을 최대화하는 문제를, 전체 가중칭서 빼주는 가중치의 합을 최소화하는 문제로 바꿔서 생각해보는 것이 중요하다고 할 수 있겠다.

Source Code

National Olympiad in Informatics, China, 2012 Day 1, Problem 1 - Random Number Generator

Problem Link

A(n) = (a*A(n-1)+c) mod m 이고 A(0)가 주어졌을 때, A(n) mod g를 구하는 문제.

g가 10^8 이하이고, 나머지 값들은 모두 10^18 이하라서, 계산 도중 long long 범위를 넘어갈 수 있음에 주의해야한다. log 시간복잡도에 a^x 계산과 1+a+a^2+....a^x 계산을 할 줄 알면 풀 수 있다. 그리고 ( X mod m ) mod g를 계산할 때에는 X나 m을 g로 나눈 나머지로 계산하면 안되고, m으로 나눈 나머지로 다 계산한 다음에 g로 나눈 나머지를 계산해야한다. modular를 공부했었다면 다 아는 사실이겠지만...

Tuesday, August 12, 2014

Note #1

1. 항상 경계값, 극한값 생각하기. 최소일 때, 최대일 때, 같을 때 고려하기.

2. 일반화의 오류에 빠지지 않기. 해법이 안 떠오를수록 문제를 반복해서 읽고, 1로 돌아가서 풀이를 떠올리기.

3. 제출하기 전에 30초만 차분히 생각하고 제출하기.

4. 1,2,3이 무의식적으로 행해질 수 있도록 반복 연습하기.

Wednesday, August 6, 2014

Counting Subsequences

Problem Link(PEG Judge)

Given a string, count all distinct subsequences (not substrings).
As defined previously, a subsequence is a collection of characters from the string (they don't have to be contiguous)

For example, for the string aba, there are 6 distinct subsequences: (a, b, aa, ab, ba, aba).

Input

The string, on one line. It will consist only of lowercase letters.
It will be no longer than 100,000 characters long (this is easier than all substrings!)

Output

The number of distinct subsequences.
Note that this number may be ridiculously large, so print it mod 10,007.

D(i) = "i번째에서 끝나고, i번째 문자를 반드시 넣을 때 만들어지는 
distinct subsequences의 개수"라고 정의하자.

i번째 문자를 S(i)라고 하자. S[i] = S[j](j<i)인 j중 가장 큰 j에 대해서 D[i] = Sum(D[j] ~ D[i-1])

만약 S[i]가 처음 등장했다면, D[i] = Sum(D[1]~D[i-1])+1이 된다.

Source Code

Friday, August 1, 2014

ICPC 팀명ㅋㅋ

'One Rest, Two Retired'에서 문제 많이 맞추자고 'ACRush'로 바꿨다ㅋㅋ

재밌겠다ㅎㅎㅎ