나나컵 1라운드 토론글

  • 일루
    일루

    보기 드문 열기에 감사드립니다!

    각자 구현한 방법 설명을 해 주시어요~


    11년 전
9개의 댓글이 있습니다.
  • hyunhwan
    hyunhwan

    채점 언제 되나요? 현기증 나네요.


    11년 전 link
  • Taeyoon_Lee
    Taeyoon_Lee
    1. prefix 트리를 만듭니다.
    2. BFS로 답이 될만한 후보를 고릅니다. 다른 글자 수를 최대 한 개로 제한했습니다. (2개 이상이면 점수/셀 효율이 안 좋더라구요.)
    3. 각 셀마다 200개씩 점수/셀 효율이 가장 좋은 후보들을 기억해 놓습니다.
    4. 그리디하게 대충 답을 만듭니다. 3종류로 만들어봤습니다. 하나는 점수/셀이 좋은 순으로 선택한다. 하나는 점수가 높은 순으로 선택한다. 하나는 각 셀이 얻을 수 있는 최고점을 계산해서 최고값과 차이가 작은 순으로 선택한다.
    5. 4번에서 대충 만든 답을 튜닝합니다.
    6. 튜닝이 성공하면 실패 카운트를 0으로 하고, 다시 5번으로 가서 튜닝 ㄱㄱ. 튜닝이 실패하면 실패 카운트를 ++하고 다시 5번으로 가서 튜닝 ㄱㄱ. 근데 실패 카운트가 너무 높다 싶으면 4번으로 돌아가서 새로운 답으로 다시 시작합니다.

    대충 이런 식인데요... 5번은......


    11년 전 link
  • MiNu
    MiNu

    저는 우선 단어장에서 정확히 일치하는 단어를 모두 찾아내서 점수가 높은 순으로 출력하고,
    나머지 문자들로 만들 수 있는 오류를 포함한 단어들을 찾아내서 이것도 점수가 높은 순으로 배열하도록 했습니다.

    1. 단어장의 모든 접두사들을 128bit 해쉬값으로 변환하여 접두사 사전에 저장합니다.
    2. 접두사 사전을 이용하여 단어장과 정확히 일치하는 단어를 문자배열에서 DFS로 모두 탐색합니다. 단어장에 포함된 최대 길이 22까지 탐색하도록 해도 실제로 정확히 일치하는 단어 길이는 11~13 정도가 최대더군요. (현재까지 찾은 경로의 단어가 접두사 사전에 없는 경우 이후 경로 탐색을 중단하도록 하여 탐색 시간을 줄임)
    3. 정확히 일치하는 단어들을 획득 점수가 높은 순, 다른 단어와 최소로 겹치는 순으로 출력합니다
    4. 정확히 일치하는 단어 배치가 완료되고 난 다음 나머지 남은 문자들을 이용하여 오류를 포함한 단어를 만들 수 있는 경우를 특정 길이만큼 모두 탐색합니다. (실험 상 단어 길이는 최대 6이 가장 점수가 높았음)
    5. 오류를 포함한 단어들을 획득 점수가 높은 순, 다른 단어와 최소로 겹치는 순으로 출력합니다

    나나컵 1라운드의 기록: http://minu.kr/나나컵-라운드1-단어-뱀놀이


    11년 전 link
  • Taeyoon_Lee
    Taeyoon_Lee

    튜닝 과정만 따로 써보자면...
    5-1. 현재 만들어진 답(4번에서 만든 답 or 몇 번의 튜닝을 거친..)에서 제거해볼 덩어리를 하나 고릅니다.
    5-2. 그 덩어리 + 그것과 붙어있는 모든 덩어리를 제거합니다. (여기서 약간 랜덤을 섞었는데, 1칸 붙어있는 덩어리들만 제거할 때도 있고, 2, 3칸 붙어있는 덩어리까지 제거할 때도 있습니다.)
    5-3. 덩어리가 제거된 셀마다 3번에서 미리 만들어둔 가성비 좋은 후보 리스트를 보며, 현재 상태에 추가할 수 있는 지 확인하고, 가능하면 추가합니다. 각 셀의 1등 후보들부터 시작해서, 각 셀의 200등 후보들까지 가성비 좋은 순으로 그리디하게... 이 과정에서 셀의 순서도 랜덤하게 섞어보고, 1~200등 후보 덩어리들도 가성비가 같은 애들끼리는 조금씩 등수가 섞이도록 했습니다.

    그림으로 보자면 아래처럼 되지요.

    ## 현재 상태
D311SS_8_OO_
D331_S_8ROO_
D_TTTS78RONN
444TT_77RQNN
_JJHH227RQMP
JJJ_H227LQMP
IIJJ_0_7LMMP
II5_G000LMMP
KK55GG__L99_
KK_AB_EFF9VV
K_CABBE_FWWV
CCCABBEX_WWU
666_B__XXXUU

## 3 주변을 제거해본 상태
____SS_8_OO_
_____S_8ROO_
_____S78RONN
444___77RQNN
_JJHH227RQMP
JJJ_H227LQMP
IIJJ_0_7LMMP
II5_G000LMMP
KK55GG__L99_
KK_AB_EFF9DD
K_CABBE_F11D
CCCABBE3_11T
666_B__333TT

## 가성비 좋은 후보로 갱신한 상태
VVWWSS_8_OO_
VVWWWS_8ROO_
VVUUUS78RONN
444UU_77RQNN
_JJHH227RQMP
JJJ_H227LQMP
IIJJ_0_7LMMP
II5_G000LMMP
KK55GG__L99_
KK_AB_EFF9DD
K_CABBE_F11D
CCCABBE3_11T
666_B__333TT

445점에서 -> 452점으로 야호!

    속도 최적화를 위해서 bit mask를 썼는데.... :'( 더 이상 자세한 설명은 생략한다.

    마지막으로, 재밌는 대회 열어주신 ainu7, LIBe 등 운영진 분들과 끝까지 경쟁심에 불을 붙여준 kriii군에게 감사 인사를 전합니다. 덕분에 무척 재밌었어요. :)


    11년 전 link
  • hyunhwan
    hyunhwan

    http://libe.lavida.us/mmjudge/final_summary.php

    현재 채점 링크입니다.


    11년 전 link
  • 음매~@
    음매~@
    1. 단어장으로 오토마타 생성(prefix 트리)
    2. 입력 보드에서 아직 단어로 사용되지 않은 문자를 새로운 파싱 시작점으로 선택. 파싱의 성공->단어. 여기서 랜덤으로 사용되지 않은 문자라도 일정 확률로 스킵했습니다.
    3. 파싱된 단어를 스코어((l-e)^2/(1+e))를 구하고 패널티 텀으로 다른 단어와 경로가 겹치는 경우를 뺀 뒤에 정렬한 뒤, 상위 단어부터 그리디하게 선택.
    4. 사용되지 않은 셀에서 typo를 최대 1개 까지 허용하면서 파싱. 3과 마찬가지 방법으로 정렬 및 단어 선택.
    5. 아직까지 보드에 남은 문자 중에 3.4.에서 고른 단어에 접두어 접미사로 붙일 수 있는 부분을 typo가 없는 단어부터 붙여봄. 2 반복.

    11년 전 link
  • hyunhwan
    hyunhwan

    다음 링크에서 최종 full submission에 대한 점수를 확인할 수 있습니다.

    http://goo.gl/lt5CB


    11년 전 link
  • ILyoan
    ILyoan

    제 방식은 altertain님의 서브셋이네요 흠..
    1. 사전으로 prefix trie 를 만듭니다.
    2. dfs로 후보리스트를 만듭니다. 보아하니 에러가 2개가 넘는것도 찾으려면 시간도 오래걸리고 효율도 떨어집니다. 에러는 하나까지만 허용하기로 합니다.
    3. 차지하는 칸수(단어길이)대비 점수가 높은순으로 소팅을 합니다.
    4. 소팅된 순서로 뱀을 놓을수 있으면 놓습니다.
    5. SA
    5.1. 선택받지 못한 뱀중 하나를 골라봅니 다.
    5.2. 이놈을 놓으려면 꺼내야 하는 놈들이 있습니다. 이놈듩을 꺼내고 새로 생긴 빈칸에 새로운 뱀들을 그리디하게 놓습니다.
    5.3. 이득이 있으면 바꾼상태로 가고 이득이 없으면 확률적으로 바꾼상태를 받아줍니다.
    5.4 무한반복

    더 높은 점수를 얻으려면 랜덤요소를 넣어야 한다고 생각했습니다.
    1. 적합도가 같은 애들의 소팅된 순서를 바까본다.
    2. 두개 이상의 뱀들을 바까치기 해본다.
    는 속업하느라 시간이 부족해서 시도해보지 못했네요 .
    대신 토욜에 속업에 신경을 많이 써봤습니다만...계산해보니 선두와 대등해지려면 다섯배 빨라져야합니다. 하지만 현실은 30프로 향상에 그칩니다.OTL

    재밌는 문제였습니다.
    라운드2도 기대해볼께요.


    11년 전 link
  • kriii
    kriii
    1. prefix trie를 만든다.
    2. 각 시작점에 대해 단어를 찾아서 그 길이와 오타수, 경로를 저장한다.
    3. 각 칸당 점수가 높은 순으로 막 집어 넣는다.
    4. 그다음은 약간씩 고쳐가면서 최댓값을 찾는과정을 반복.

    이 과정에 대해 써보자면
    랜덤한 점에서 다이아몬드 모양으로 잘라 냅니다. 이때 다이아몬드 영역안에 들어가면 모두 잘라냄.
    그리고 각 칸당 점수가 높은 순서대로 또 집어 넣는데, 이때
    가장 높은 것을 넣는다/안넣는다. 두번째 높은 것을 넣는다/안넣는다....로
    다섯번째 까지만 정해줘서 그 중 최댓값으로 계속 갱신했습니다.
    점수가 같으면 랜덤으로 조금씩 바꿔줬구요...

    처음에는 SA로 하다가 마지막 날에 깨달았는데 SA를 하는 것 보다는 점수가 낮아질 기회를 안주는게 더 점수가 잘 나온 것 같습니다.
    아쉬운 점은 구해지는 답이 편차가 너무 심해요ㅋㅋ. 두배 정도만 더 빨라졋으면 점수도 엄청 올랐을 거고 편차도 줄어들었을텐데...
    마지막 날은 계속 최적화만 했는데 별 효과를 못봤네요

    mm류의 문제를 처음으로 코딩해 봤는데 재미있었습니다. 중간에 고치면서 소스가 복잡해지고 머리가 터지는 재미가 있네요 ㅎㅎ R2도 기대됩니다ㅎㅎ

    모두 수고하셨습니다.


    11년 전 link

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