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도 가능한 경우가 있으니 참고하자.

No comments:

Post a Comment