므므 데뷔 후기

  • iddaga
    iddaga

    어떻게 MM이라는 함정에 빠졌는지 정확히 기억은 나지 않지만

    아마 일루님이 #icpc 에서 재밌게 하시는걸 보고 낚인듯요

    문제링크 입니다
    http://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=15101&pm=11984

    문제를 읽고 든 생각은

    1. 답을 이분검색하자

    2. 해밀토니안 경로 C개를 만들어서 적당히 나눠주자

    테스트 생성코드를 읽고 든 생각은

    1. 하아......

    2. rose 는 나의 적 base 랑 rim 은 나의 친구

    3. rim 이 있는 부분과 없는 부분이 계속 번갈아 나온다면
      이 조각케잌을 먹을 손님이 애매할듯..

    -> 경로는 달팽잌ㅋㅋㅋㅋㅋ 거의 7,8 년만에 짜보는 달팽이..

    그럼 어떻게 적당히 그리디하게 나눠줄 것인가

    1. 먹을 손님을 고르면 가장 적은 면적으로 만족할 수 있는 조각을 먹음

    2. 먹을 손님을 고르는 방법은
      (두번째로 적은 면적) - (가장 적은 면적) 를 최대화

    3. 조각의 후보는 달팽이의 양끝

    짜고 제출.

    9천점대 ㅎㅎ 올ㅋ 므므 쉽네

    는 무슨 여기서부터 초보자에겐 꿈도 희망도 없는 고난의 길이어씀다 ㅜ ㅜ

    뭘하지.. 경로를 바꿔볼까

    달팽이를 반대방향으로 돌려보자

    -> 좀 오르네

    두 방향의 달팽이를 C개에 배치해서 2^C 를 돌려보자

    -> 좀 오르네 ㅜㅜ 왜 10점씩 밖에 안오르는거야 엉엉

    근데 좀 이상하게 오름..

    이분검색을 할 때 중앙값을 뭐로 잡느냐에 따라 답이 많이 달라짐

    는 그리디 알고리즘에 의한 순서가 최적이 아니기 때문

    이 사실을 알고서 케잌 먹는 순서를 로컬서치 또는 SA 하셨다면 성공 !

    전 실패 ㅋㅋㅋㅋㅋㅋ 늅늅이는 저 생각이 안떠오르더군요

    그래서 답과 답*1.1 사이를 백분할 해서 답을 갱신시키는 쪽으로 삽질을..

    했더니 너무 느려서 그리디를 BIT 를 이용해서 고속화하니까

    최종 점수쯤 오더라구요

    그리고나서 달팽이를 변형시켜 여러가지 맵을 시도하다가

    여전히 10점씩 정도밖에 안올라서 멘붕!

    50등으로 대회를 마무리짓고 풀테스트 결과 기다리고 있는중입니다

    꽤 흥미로웠던 MM 데뷔였슴다. 끝


    11년 전
5개의 댓글이 있습니다.
  • Taeyoon_Lee
    Taeyoon_Lee

    좋아요


    11년 전 link
  • JongMan
    JongMan

    좋아요


    11년 전 link
  • Baekjoon
    Baekjoon

    매우 좋아요


    11년 전 link
  • wookayin
    wookayin

    매우매우 좋아요


    11년 전 link
  • Being
    Being

    욱이 좋아요


    11년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.