므므 데뷔 후기 iddaga 어떻게 MM이라는 함정에 빠졌는지 정확히 기억은 나지 않지만 아마 일루님이 #icpc 에서 재밌게 하시는걸 보고 낚인듯요 문제링크 입니다 http://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=15101&pm=11984 문제를 읽고 든 생각은 답을 이분검색하자 해밀토니안 경로 C개를 만들어서 적당히 나눠주자 테스트 생성코드를 읽고 든 생각은 하아...... rose 는 나의 적 base 랑 rim 은 나의 친구 rim 이 있는 부분과 없는 부분이 계속 번갈아 나온다면 이 조각케잌을 먹을 손님이 애매할듯.. -> 경로는 달팽잌ㅋㅋㅋㅋㅋ 거의 7,8 년만에 짜보는 달팽이.. 그럼 어떻게 적당히 그리디하게 나눠줄 것인가 먹을 손님을 고르면 가장 적은 면적으로 만족할 수 있는 조각을 먹음 먹을 손님을 고르는 방법은 (두번째로 적은 면적) - (가장 적은 면적) 를 최대화 조각의 후보는 달팽이의 양끝 짜고 제출. 9천점대 ㅎㅎ 올ㅋ 므므 쉽네 는 무슨 여기서부터 초보자에겐 꿈도 희망도 없는 고난의 길이어씀다 ㅜ ㅜ 뭘하지.. 경로를 바꿔볼까 달팽이를 반대방향으로 돌려보자 -> 좀 오르네 두 방향의 달팽이를 C개에 배치해서 2^C 를 돌려보자 -> 좀 오르네 ㅜㅜ 왜 10점씩 밖에 안오르는거야 엉엉 근데 좀 이상하게 오름.. 이분검색을 할 때 중앙값을 뭐로 잡느냐에 따라 답이 많이 달라짐 는 그리디 알고리즘에 의한 순서가 최적이 아니기 때문 이 사실을 알고서 케잌 먹는 순서를 로컬서치 또는 SA 하셨다면 성공 ! 전 실패 ㅋㅋㅋㅋㅋㅋ 늅늅이는 저 생각이 안떠오르더군요 그래서 답과 답*1.1 사이를 백분할 해서 답을 갱신시키는 쪽으로 삽질을.. 했더니 너무 느려서 그리디를 BIT 를 이용해서 고속화하니까 최종 점수쯤 오더라구요 그리고나서 달팽이를 변형시켜 여러가지 맵을 시도하다가 여전히 10점씩 정도밖에 안올라서 멘붕! 50등으로 대회를 마무리짓고 풀테스트 결과 기다리고 있는중입니다 꽤 흥미로웠던 MM 데뷔였슴다. 끝 12년 전
5개의 댓글이 있습니다. Taeyoon_Lee 좋아요 12년 전 link JongMan 좋아요 12년 전 link Baekjoon 매우 좋아요 12년 전 link wookayin 매우매우 좋아요 12년 전 link Being 욱이 좋아요 12년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
iddaga
어떻게 MM이라는 함정에 빠졌는지 정확히 기억은 나지 않지만
아마 일루님이 #icpc 에서 재밌게 하시는걸 보고 낚인듯요
문제링크 입니다
http://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=15101&pm=11984
문제를 읽고 든 생각은
답을 이분검색하자
해밀토니안 경로 C개를 만들어서 적당히 나눠주자
테스트 생성코드를 읽고 든 생각은
하아......
rose 는 나의 적 base 랑 rim 은 나의 친구
rim 이 있는 부분과 없는 부분이 계속 번갈아 나온다면
이 조각케잌을 먹을 손님이 애매할듯..
-> 경로는 달팽잌ㅋㅋㅋㅋㅋ 거의 7,8 년만에 짜보는 달팽이..
그럼 어떻게 적당히 그리디하게 나눠줄 것인가
먹을 손님을 고르면 가장 적은 면적으로 만족할 수 있는 조각을 먹음
먹을 손님을 고르는 방법은
(두번째로 적은 면적) - (가장 적은 면적) 를 최대화
조각의 후보는 달팽이의 양끝
짜고 제출.
9천점대 ㅎㅎ 올ㅋ 므므 쉽네
는 무슨 여기서부터 초보자에겐 꿈도 희망도 없는 고난의 길이어씀다 ㅜ ㅜ
뭘하지.. 경로를 바꿔볼까
달팽이를 반대방향으로 돌려보자
-> 좀 오르네
두 방향의 달팽이를 C개에 배치해서 2^C 를 돌려보자
-> 좀 오르네 ㅜㅜ 왜 10점씩 밖에 안오르는거야 엉엉
근데 좀 이상하게 오름..
이분검색을 할 때 중앙값을 뭐로 잡느냐에 따라 답이 많이 달라짐
는 그리디 알고리즘에 의한 순서가 최적이 아니기 때문
이 사실을 알고서 케잌 먹는 순서를 로컬서치 또는 SA 하셨다면 성공 !
전 실패 ㅋㅋㅋㅋㅋㅋ 늅늅이는 저 생각이 안떠오르더군요
그래서 답과 답*1.1 사이를 백분할 해서 답을 갱신시키는 쪽으로 삽질을..
했더니 너무 느려서 그리디를 BIT 를 이용해서 고속화하니까
최종 점수쯤 오더라구요
그리고나서 달팽이를 변형시켜 여러가지 맵을 시도하다가
여전히 10점씩 정도밖에 안올라서 멘붕!
50등으로 대회를 마무리짓고 풀테스트 결과 기다리고 있는중입니다
꽤 흥미로웠던 MM 데뷔였슴다. 끝
12년 전