sub sub ::

'programming contest/모의고사'에 해당되는 글 2건

2008/05/17 초등부 올림피아드 2003 전국본선 3번문제
2007/11/18 알고스팟 2007/11/11 모의고사

초등부 올림피아드 2003 전국본선 3번문제

요즘 초등학교 문제밖에 안푸는거 같네요..ㅡㅜ(그것도 과외시간에 풀게 되네요.ㅎㅎ)

이문제가 상당히 괜찮은 문제인거 같습니다. 그렇게 어렵지도 않구요. https://www.kado.or.kr/koi/F04000000000/F04040000000Q.asp?intExBaSEQ=31&strExBaPart=20&strExBaGrad=01&strExBaYear=2003&ExPmSEQ=355

ps1. 그리고 이사이트의 고급 알고리즘 동영상도 꽤 괜찮은거 같네요.(특히 백트랙킹과 계산기하는 추천합니다. 다른건 안봐서..ㅡㅠ)

ps2. 그리고 아래의 글은 문제를 풀어보셨거나, 안풀 사람만 보시길 바랍니다.

처음에는 O(n^2)에 풀릴줄 알았는데, 몇가지 트릭(?)을 쓰면 O(n)에 풀리는 군요. 이때까지 다이나믹에 대해서 많이 알고 있다고 생각했는데, 기초적인 부분이나 대충 공부했던 부분이 많은거 같습니다.

Posted by @,.@

programming contest/모의고사 | 2008/05/17 17:28

Tags : 다이나믹, 생각해볼 문제

Trackback (0) : Comment (0)

문제
http://ncpc.idi.ntnu.no/ncpc2007/ncpc2007problems.pdf
소스코드
http://algospot.com/zbxe/news/1951

- C
sqrt함수 대신에 (j * j <= i) 이렇게 표현할 수 있다.
덧셈의 경우 대칭이니 (2 * j <= i)이런식으로 표현할수 있다.

- D
while (true) {
if (c[now] == 1) break;
a.push_back(now);
c[now] = 1;
now = ((c[g[now].first] == 0) ? g[now].first : g[now].second);
}
길이가 n인 사이클을 찾는 방법이다.(에지가 n개 있을때만)