sub sub ::

SRM 393 div 2

250과 500은 그냥 시키는데로 하면 된다. -_-; 약간의 코딩 실수(인덱스, while대신에 if등을 쓰는등의 실수로..고생을 했다)를 했다.

1000점을 보니 minimum set cover문제인거 같다. 이거는 NP-Complete아닌가?? -_-;
그래프로 만들어서 고향에서 이어져 있는 방문도시들은 제외 하고 남은 도시들을 기존의 에지로 연결된 곳을 하나의 셋으로 하여 최소의 연결(셋 끼리) 하는거 같다.

쩝 이래서 언제 div 1 올라 가냐..ㅡㅜ

Posted by @,.@

programming contest/Top Coder | 2008/03/12 01:08

Trackback (0) : Comment (0)

SRM 312 Div2

250 500 통과했네요..ㅡㅜ 500에서 삽을 너무 많이 펐네요..ㅡㅜ

- 250 : 시키는데로 하면 되네요. 근데 10진수와 약간 다른 시스템 (ex 10을 10 + 0 형태가 아닌 10으로 생각함. 즉 0은 존재하지 않는다. 1~10 으로 표현)만 신경쓰면 될듯. 그리고 2자리 출력시 사이 공백만 신경쓰면 어렵지 않은듯하네요.ㅋ

- 500 : 문제는 어렵지 않은듯 하네요. 근데 코딩의 압박이(스트링 처리) 장난이 아니네요.ㅋ 알고리즘은 대충 이렇습니다. 각 도형의 부피를 구해서 더하고, 교차하는 부분의 부피를 빼주면 되는데 교차의 x1 은 두도형의 x1중에 큰값, x2는 두도형의 x2중 작은값(y,z도

동일)이고, x2-x1이 음수나 영이면 교차부피는 0
아니면 교차점을 구하면 됩니다(y,z도 같은방식으로).

- 1000 : 기하 문제네요.ㅋ 시간상 풀지는 않았지만 제 생각에는 각으로 소트 시킨다음 한점에서 시작해서 직선이 원점을 지나면서 회전시키면 될거 같네요. 다음으로 이동은 현재의 점이거나 아니면 현재를 원점 대칭한 점에서 다음점까지중 작은점으로 가면 될거 같네요. 그리고 이점을 가기 전에도 한번 계산해주면 될거 같네요.(앞의 연산을 할때마다 2영역에서 옮겨져가는 점의 수나 포함안되는것(직선에 있는것)만 생각해주면 될거 같네요).

Posted by @,.@

programming contest/Top Coder | 2008/03/02 21:13

Trackback (0) : Comment (0)

SRM 293 Div 2

이번셋은 문제 이해가 어려웠던거 같습니다. 그리고 1,2번 문제를 그냥 다 해보는식으로 구한듯 합니다ㅋ. 라이브러리를 잘몰라서 조합이나 파워는 for문을 이용해서 구했습니다ㅡㅜ.
3번 문제는 "이걸 어떻게 짜지 -_-;; 란 생각이 들더군요. 그리고 이제 막 문제를 읽기 시작했는데 옆에서 키보드 치는 압박이 상당하더군요.-_-;;

1번 문제 : 처음에는 안되는 구간들을 저장해서 나중에 합치는 방식으로 할려고

했으나, 구현이 어려울것 같아서 가능한 범위를 다 돌면서 조건을 만족하면 카운트 시키는 방법으로 했습니다.

2번 문제 : 다이나믹 비슷하게 조합을 쉽게 구할려다. 출력이 double형이라서 그냥 double형으로 조합을 구했습니다. 그리고 파워도 포문으로..ㅡㅜ

3번 문제 : 문제는 그렇게 어렵지 않은것 같은데, 코딩의 압박이(문자열 처리가 -_-;;) 느껴지는 문제이고, 시간이 얼마 남지 않아서..ㅡㅜ

Posted by @,.@

programming contest/Top Coder | 2008/02/18 01:31

Trackback (0) : Comment (0)

SRM 379 div2

- 500
그냥 다돎 O(n^2)
현제의 가격보다 더크거나 같으면서 비용은 작은것을 다 더한후 결과를

벡터에 저장하고, 정렬해서 젤앞에거 출력, 벡터에 아무것도 없으면 0을 출력

Posted by @,.@

programming contest/Top Coder | 2007/11/30 23:13

Trackback (0) : Comment (0)

SRM 378 div2

처음 해봤다...ㅋ 근데 컴파일이 안되서 문제만 보고 나왔음..ㅡㅜ

- 250
정수론의 컨거런스 응용하면 된다. 그냥 시키는대로 하면 될듯.

- 500
특정 값이 나올때마다 해당 인덱스의 값을 1씩 증가시키고, 인덱스와 값이 같은것중 큰것을 출력하면 될듯. 없을때는 -1을

-

1000
젤밋에서 부터 현제의 위치와 목표위치를 보고 같으면 위로(필요없을듯 자동적으로 해줄듯) 현재높이 -1 개를 옮기는게 m보다 작으면 옮긴다. 그리고 m에서 빼주고, 이를 반복하면 된다.
문제는 범위 넘어가는 문제 2^50-1개까지 나올수 있다.(long long이면 되나??

Posted by @,.@

programming contest/Top Coder | 2007/11/21 02:10

Trackback (0) : Comment (0)