안녕하세요, 간만에 돌아온 나나입니다.
이번 MM은 제가 TCO MM Round 2 후로 처음 참가한 MM이었습니다. 사실은 5위까지 주어지는 상금이 목표였구요 -_-;; 그래서 필사적으로 5위권에 들려고 했는데 좀 모자랐네요.
일단 문제 링크가 날아갔으니 번역을 해보도록 하죠.
전위(위치바꾸기) 암호화는 평문(암호화되기 전 텍스트)의 글자들을 바꾸지 않고 재배열만 하는 암호화를 말한다. 여기서 암호키는 글자들이 섞이는 순서가 된다. 당신이 해야 할 일은 다음과 같은 전위 암호화를 풀어내는 것이다.
길이 L인 메시지 M을 암호화해야 한다고 하자. N = ceil(sqrt(L))이 되고, 메시지의 글자들을 한 칸에 하나씩 NxN 격자에 써 나가게 된다. 시작하는 칸은 랜덤하게 결정되며, 각 단계마다 우리는...
격자의 현재 셀에 메시지의 현재 글자를 써넣는다.
다음 글자와 다음 셀로 이동한다. 다음 셀을 고르는 방법은 다음 의사코드에 설명되어있다.
for d = 3 to (현재 셀과 격자의 임의의 셀과의 최대 거리)
0.2의 확률로 다음 반복으로 이행 (즉 continue; 를 한것과 같은 효과겠죠)
집합 A = 현재 셀과 거리 d이면서, 현재 셀과 같은 행이나 열에 있지 않고, 아직 글자가 쓰여지지 않은 칸들.
집합 A가 비어있다면 다음 반복으로 이행
집합 A에서 랜덤한 셀 선택(선택되었으면 반복은 없음)
만약 위의 의사코드가 메시지의 모든 글자들을 격자에 써 넣는데 실패한다면, 격자를 비우고 이 과정을 다시 수행하게 된다.
마지막으로, 만들어진 격자를 암호문으로 변환하는 방법은 행 우선으로 글자들을 읽어서 한 줄로 쓰는 것이다. 글자들이 없는 셀들이나 빈 칸이 쓰여있는 셀들은 '.' 글자로 대체된다.
당신은 암호화에 의해 만들어진 ciphertext와 격자에서 인접한 각 단계에 채워진 셀들간의 거리들의 수열인 delta를 입력으로 받는다. 당신은 원문에 대한 당신의 추측을 리턴해야 한다. 리턴의 길이는 반드시 원문의 길이(delta.length()+1 로 계산가능)와 일치해야 한다. 당신의 리턴은 반드시 글자 'A'-'Z'와 '.'(공백문자가 아님)로 이루어져 있어야 한다.
한 테스트 케이스에 대한 당신의 점수는 실제 메시지와 당신의 추측과의 최대공통부분문자열(Longest Common Substring)의 길이를 실제 메시지의 길이로 나눈 값이다. 당신의 총점은 각 테스트 케이스마다 이 점수들을 모두 더한 점수가 된다.
테스트 케이스들은 우선 원문(나열된 문장들 - 따로 주어짐)에서 25글자 이상('a'-'z', 'A'-'Z', ' '가 아닌 문자들을 모두 제거하고 연속된 공백문자를 하나로 줄인 뒤에..)의 문장을 랜덤하게 선택한 뒤, 길이 L을 25 이상 문장길이 이하의 랜덤한 값으로 선택해서, 문장의 길의 L의 prefix를 메시지로 얻게 된다. 메시지가 문장 중간에서 끊어지지 않도록 하기 위해서, 이렇게 얻은 메시지는 다음 공백문자(또는 문장의 끝)까지 연장된다. 이후, 메시지는 위에 설명된 방법으로 암호화되며, 현재 셀과 다음 셀간의 거리들은 delta로 저장되게 된다.
사용가능한 라이브러리가 존재하는데, vector val = Statistics::getWords() 를 하면 원문들에 나온 단어들을 빈도수 순서대로 정렬해서 보내주게 된다. ("THE 678728", "OF 397189" 식...)
추가사항
(row1, col1)과 (row2, col2) 사이의 거리는 abs(row1-row2) + abs(col1-col2) 로 계산된다.
메모리 제한은 1GB, 시간제한은 20초이다 (당신의 코드 안에서 수행된 시간만 따진다)
소스 화일 크기 제한은 500KB이다.
10개의 example 테스트 케이스와 100개의 full submission 테스트 케이스가 있다.
원문(corpus)의 각 줄은 arXiv e-Print archive (arxiv.org) 에서의 abstract 이다.
온라인에 보면 words.txt(1.15M)가 있는데, getWords()를 하면 받을 결과가 들어있습니다. 또한 all.txt(53M)가 있는데, 이건 corpus 전체 내용입니다. words.txt와 all.txt가 대회 중간이나 대회 후에 바뀌지는 않습니다.
자 그러면 제가 문제를 해결해나간 과정을 설명해보도록 하겠습니다.
목요일(대회 1일째) -
이날은 좀 바빠서 아무것도 안하고 그냥 지나갔습니다.
금요일(대회 2일째) -
오후 5시에 문제를 프린트해보았습니다.
"이게 뭠미???"
"아 지난주에 했어야 하는건데..."
뭐 어쩔 수 없는 일이라 일단 문제를 보다가 연말행사를 하러 놀러갔습니다.
토요일(대회 3일째) -
아침 7시에 잠이 들어서 오후 2-3시에 깼습니다. 스타를 좀 보다가 그담엔 뭘했는지...?? 기억이 안나는군요. 아마 자다깨다 자다깨다를 반복한것 같습니다.
일요일(대회 4일째) -
오후에 약속이 있어서 나갔다 와서 저녁 늦게에 침대에 노트북을 가지고 앉았습니다. 일단 주어진 원문은 평범한 영어로 쓰여져 있어서, 문제 조건에 맞추어서 문장을 만드는 작업을 했습니다. (밤 12시) 그리고 나서 자기 전까지는 랜덤하게 문장을 선택하는 부분과 채점을 위해서 데이터 입/출력을 하는 부분을 코딩했습니다. 그리고 예제 데이터를 뽑아보았습니다. 자 이제 귀찮은걸 다 끝냈으니 함수 하나만 짜면 됩니다. string KnightsMoveCipher::decipher(string, vector) 를 말이죠..
월요일(대회 5일째) -
이거 글을 쓰다보니 진짜 뻔뻔히 놀다가 막판에 몰아서 했네요 -_-;; 아무튼 이 날부터 사흘간 바짝 코딩을 했습니다.
예제 데이터를 보니 길이가 긴 것들이 많더군요. 그런데 delta는 대부분의 경우 3~4를 왔다갔다 하고 있어서 각 위치에서 백트래킹으로 가능한 모든 단어들을 찾아보면 그리 많지 않을 것이라는 생각이 들었습니다.
.. 왠걸 실제로 돌려보니 단어의 수가 자비가 없더군요. 게다가 짧은 단어들이 너무 자주 나와서 아주 태클이 제대로네요.
일단 일정 길이 미만인 것은 다 자르고, 일정 길이 이상이더라도 빈도수가 단어의 길이와 사용된 글자의 자주 나오는 정도에 비해서 너무 적다 싶으면 잘라서, 각 위치별로 나올법한 단어들을 뽑아보았습니다. 뭔가 문장의 키가 될만한 단어들은 잘 나오는 편인데, 그렇지 않은 단어들은 잘 나오지 않더군요.
그래도 서밋은 한번 해봐야겠다 싶어서, 제가 각 위치의 단어별로 매긴 가중치가 높은 순서대로 무조건 그리디하게 넣게 해놓고 이것을 제출했습니다.
1 12-15-2008 18:15:45 9.89
음? 생각보다 훌륭하빈다 -_- 15등 정도에 랭크되었는데 1등이 35점? 5등이 15점? 그 정도라서... 어차피 어려운 문제니 조금만 열심히 해보자! 라고 생각했습니다. 이 때부터 순위권과의 사투가 벌어지면서 급속도로 버닝하게 됩니다...
저녁부터는 최적화 위주로 접근해보았습니다. (하카다를 다녀오긴 했지만 뭐 가면서도 가서도 오면서도 했으니...) 위에서는 문장에 채워넣는 것을 그리디하게 했는데... 이걸 가중치가 높은 것들에서 약간 순서를 바꿔서 넣어보거나... 좀 더 랜덤하게 넣어서 횟수를 많이 반복하거나... 옆에 단어가 채워지면 가중치를 높인다거나.. 옆에 단어가 채워졌는데 위치상 안되는건 자른다거나... 이런것들을 시도해보았습니다.
화요일(대회 6일째) -
아무튼 심혈을 기울여서 결과가 좀 개선되었다고 느꼈습니다. 그래서 submit!
2 12-16-2008 11:07:08 6.91
뭠미!? 좀 여러모로 상태가 좋지 않습니다. iteration을 많이 돌아서 길이가 긴거에서 TLE가 났다거나, 뭐 이럴 수 있다고 생각했습니다. 그래서 iteration 횟수를 최적화하고, 속도를 좀 더 빠르게 하는 이런저런 귀찮은 것들을 하고, factor들을 좀 고쳐서 다시 submit!
3 12-16-2008 15:08:06 7.96
음.. 뭔가 문제가 있는게 분명합니다. 버그가 있거나, TLE가 나거나, 아니면 알고리즘이 영 글러먹은 겁니다. 그래도 MM을 몇 번 해본 경험이 있어서 도움이 된거인지는 모르겠지만, 여기서 알고리즘이 잘못된거라 판단하고 아예 포기를 하게 됩니다.
길이 40짜리 문자열을 갖다두고 손으로 이걸 풀어볼라고 노력하는데... 답을 알고 찾는데도 잘 안됩니다 -_- 그럼에도 불구하고 컴퓨터의 힘이라면 가능할 것이라고 생각하고, 백트래킹을 해보는 만행을 저지르게 됩니다. 근거는... 점수를 한 10점 정도만 올려도 순위권에 들 것이라고 생각해서.. 전체의 10%도 안되는 길이짧은 문자열을 집중공략해보자? 라는 것이었습니다.
일단 길이 40 이하인 문자열에 도전합니다. 커팅을 조금 하긴 했습니다. 연속 몇 단어가 길이가 너무 짧거나, 길이에 비해서 빈도수가 너무 짧은 것으로 판단되는 이상한 단어들이 연속해서 나온다거나.. 하면 과감하게 짤랐습니다.
생각외로 길이 40 이하는 꽤나 잘 나오더군요. 길이를 64까지 늘려보니까 너무 안드로메다로 가서 49까지만 늘려서 돌려보았습니다. 전체 케이스 1만개중에 4.87%를 차지하는데 평균 0.87점이 나왔습니다. 곱하면 4.24점이니까 괜찮은 성과겠지요... 라고 생각하고.. submit을 질러보았습니다. 길이 49 이하인 경우에만 백트래킹을 하고, 그 위에서는 원래 9.89점을 맞았던 그리디 솔루션으로 접근합니다.
4 12-16-2008 20:05:48 10.96
음.. 9.89점이던게 10.96점이 되었군요? 아놔.. ㅠㅠ 데이터가 자비가 없는걸까 라고 생각했습니다. 그래도 희망을 놓지 않고 전체의 17% 정도를 차지하는 길이 100 이하의 메시지를 집중공략해보기로 했습니다.
오후 8시 33분(원래버젼) L<=100 : 평균 0.42773
오후 9시 20분 L 무제한 : 평균 0.14413
몇몇 정확도를 희생하는 커팅을 넣어보았습니다.
오후 10시 36분 L<=100 : 평균 0.69407
여기까지는 소스 길이가 13K 이하의 우아한 길이였는데, 이제부터 여러 안드로메다적 접근방법을 선택하면서 소스 길이가 급 증가하게 됩니다. (마지막에는 499KB까지 증가)
가장 처음 선택한 것은 각 단어별로 문장에서 가장 처음 나오는 위치를 저장하는 겁니다. 이렇게 되면 잘 안나오는 단어들은 초반에 잘 선택이 안될 것이고, 한 번만 등장하는 단어들은 위치가 고정되겠죠. 커팅에 아주 큰 도움이 되었고, 오후 8시만 해도 L<=49의 성공률이었던 것을 이제는 L<=100에서 볼 수 있게 되었습니다.
오후 11시 51분 L<=100: 평균 0.82192
5 12-17-2008 00:14:23 16.56
뭔가 무지하게 열심히 했어요 암튼 ㅡ.ㅡ 이리저리 계속 커팅조건 바꿔보고 하면서...
오전 4시 31분 L 무제한 : 평균 0.22707
6 12-17-2008 04:53:07 15.84
음? 뭔가 잘 안되는데요... 어디선가 TLE가 걸리나요? L<=150일때는 백트래킹 그 넘어서는 그리디로 하게 했는데, 아무래도 L<=150의 성능이 완전하지는 않거나 TLE가 걸린 것 같습니다.
오전 4시 56분 L<=100 : 평균 0.87148
오전 5시 47분 L<=100 : 평균 0.88406
이제 내일은 L 제한을 150까지 올려서 테스트를 해봐야지 라고 생각하고 자러 갔습니다.
수요일(대회 7일째, 마지막 날) -
대회 종료는 밤 2시입니다. 그 전에 어떻게든 해 봐야할텐데...
일단 밤과 아침에 약간의 최적화를 더 했으니 서밋을 해보긴 해봅니다. TLE 염려해서 커트를 좀 낮추기도 하고.. (아직 시간 커트는 없었습니다)
7 12-17-2008 10:53:18 16.71
음? 그렇게 결과가 좋아지지가 않습니다. 이유는 모르겠지만 좀 더 노력해보기로 했습니다.
오전 11시 13분 L<=150: 평균 0.71760
그러다가 불현듯 떠오른 생각... 문장의 각 위치별로 해슁을 하면 어떨까? 란 생각이 들었습니다.
즉 a[i] = (a[i-1]*a+message[i])%b 를 한 다음에 각 문장별로 h15[a[15]]=1 을 하면, 실제로 문장을 만들어나가다가 길이 15인 순간 h15[x]가 0이면 거기서 자르는겁니다. 저는 a=29, b=103093을 잡았고, 이렇게 하면 전체 문장 갯수가 8~9만개 정도이니 겹치는거 고려하면 절반 정도는 잘리게 됩니다. 또한 hash table 크기가 103093인데 base64로 표현하면 17K의 공간만 사용하게 되므로, 적절한 길이들에 대해서 테이블을 저장할 수 있다는 장점이 있습니다.
우선 길이 15, 20, 25, 30에 대해서 이 작업을 해보니, 엄청난 속도 개선이 이루어졌습니다. 여기에다가 몇몇 길에 대해서 추가로 이 작업을 했습니다. 이거 추가하면서 기존 단어별 위치데이터도 base64 인코딩을 해서, 전체 소스 크기는 300K 정도로 유지되었습니다.
또한 phase를 나누어서 공략하기로 했습니다. 즉 phase 1에서는 좀 커팅을 공격적으로 하고, 여기서 결과가 나오지 않으면 phase 0에서 찾아보는 겁니다. 이 방법도 꽤나 효과가 있었습니다.
오후 2시 52분 L<=150: 평균 0.80254
오후 3시 16분 L 무제한: 평균 0.31306
앗 점수가... 이것은 순위권?
8 12-17-2008 14:54:23 17.71
이번엔 좀 많이 당황스럽습니다... 로컬과 점수가 14점 차이나네요. 데이터 차이로만은 설명될 수 없어서, 분명히 TLE 문제가 있을 것이라고 생각했고, 다음 서밋때는 반드시 clock()으로 시간제한을 걸겠다고 다짐했습니다.
그러는 와중에 추가로 해쉬 테이블들이 추가되었고, 오후 3시 34분에는 길이 15, 20, 25, 30, 35, 40, 17, 22에 대해서 해쉬 테이블이 존재하게 되었습니다. (phase도 2 1 0의 3개가 존재) 이제 길이 151~200을 공략해보기로 했고, 수행이 빨라짐에 발맞추어 소스 크기도 점점 증가해갑니다.
오후 4시 59분 L<=100 : 평균 0.98584 (이제는 뭐 할 필요도 없는..)
오후 5시 3분 L<=150 : 평균 0.90503
오후 5시 13분 150<L<=200: 평균 0.41925
길이 151~200은 좀 공략이 힘들었습니다. 애초 커팅들이 다 길이 150 이하를 대상으로 설계되어있어서, 150 이상이 아주 큰 은총을 받지는 못한 모습입니다. phase 3을 추가했으며, 해쉬 테이블도 계속 추가해보았습니다. 그리고 원래 있었던 그리디 부분은 아예 날려버리고, 무조건 백트래킹을 하도록 바꿨습니다.
오후 5시 35분 150<L<=200: 평균 0.51668
오후 5시 42분 L 무제한: 평균 0.37269
점수가 꽤나 많이 좋아졌습니다. 예제도 4개가 1.0점이 나오기 시작합니다.
오후 6시 6분 150<L<=200: 평균 0.54987
9 12-17-2008 18:54:38 28.80
이번엔 결과가 많이 좋아졌습니다! TLE 문제점이 해결된 것까지 모두 반영이 된 것 같습니다. 이제 39점인 5위권과는 약 10점의 차이밖에 나지 않습니다.
그런데 아이디어가 떨어져갑니다 ㅠㅠ 해쉬 테이블도 몇개 더 추가해보고, 최적화도 좀 더 해봤는데 점수 상승폭이 더뎌집니다. 위치 테이블을 없애고 해쉬 테이블을 왕창 늘려보았는데 원래것만 못합니다. 새로운 아이디어를 짜내기엔 너무 시간이 없으니 최적화만 할 수밖에요. 인코딩 방식이나 데이터 저장 방식을 바꿔서 해쉬 테이블을 더 추가하는데 주력했습니다.
오후 7시 31분 150<L<=200: 평균 0.58989
오후 9시 39분 L<=150: 평균 0.95196 (이것도 이제 뭐 볼 필요가 없는..)
오후 10시 10분 L<=150: 평균 0.60792
오후 10시 21분 L 무제한: 평균 0.42968
슬슬 512K의 압박이 -_-;; 마지막에 해쉬 테이블을 우겨넣기 위해서 좀 많은 고생을 했습니다. 하지만 마지막에 큰 결과 개선은 없었습니다.
오전 12시 53분 L 무제한: 평균 0.42980 (차이가 없죠?)
오전 1시 8분 L<=150: 평균 0.61608 (여기서도 차이가 거의 없네요)
결국 최적화를 하다가 아이디어 고갈로 그냥 서밋해버렸습니다.
10 12-18-2008 01:41:35 30.80
5위랑은 8.41점 차이가 나는 8위네요. 이정도면 뒤집기는 좀 힘들어보입니다.
오늘 회사에서 와서 데이터를 바꿔서 500개 데이터에 대한 테스트를 해 보았습니다.
Number of case: 500
Total score = 183.61919
Average score = 0.36724
원래 사용했던 100개 데이터보다 평균이 6점 낮네요. 100개 데이터가 길이가 짧은 쪽으로 치중해서 선택되었나봅니다. 그래도 1000개 케이스를 대상으로 한 실제 결과는 308점보다는 367점에 가까울거라고 생각합니다. 운이 좋으면 7등, 아주 아주 많이 좋으면 6등 정도 기대해볼 수 있겠네요. 어쨌든 상금은 힘들겠죠.
역시 MM은 최적화보다는 아이디어입니다. 아이디어가 잘못된 것 같으면 바로 포기하고 딴 방법을 모색해야 합니다. 저 같은 경우는 한번은 방향을 잘 틀었는데, 두번째 방향을 틀 시간은 없었네요.
'Post your approach' thread를 보니까 다양한 방법들이 있더군요. 또한 최근의 MM을 했을 때 도움이 되는 것도 많았겠구나 하고 느꼈습니다. 상위 유저들의 코드를 분석해보고 고민해봐야겠지요.
최종 점수는 다음과 같습니다.
일루
안녕하세요, 간만에 돌아온 나나입니다.
이번 MM은 제가 TCO MM Round 2 후로 처음 참가한 MM이었습니다. 사실은 5위까지 주어지는 상금이 목표였구요 -_-;; 그래서 필사적으로 5위권에 들려고 했는데 좀 모자랐네요.
일단 문제 링크가 날아갔으니 번역을 해보도록 하죠.
전위(위치바꾸기) 암호화는 평문(암호화되기 전 텍스트)의 글자들을 바꾸지 않고 재배열만 하는 암호화를 말한다. 여기서 암호키는 글자들이 섞이는 순서가 된다. 당신이 해야 할 일은 다음과 같은 전위 암호화를 풀어내는 것이다.
길이 L인 메시지 M을 암호화해야 한다고 하자. N = ceil(sqrt(L))이 되고, 메시지의 글자들을 한 칸에 하나씩 NxN 격자에 써 나가게 된다. 시작하는 칸은 랜덤하게 결정되며, 각 단계마다 우리는...
1위부터 소스 코드 분석한 에디토리얼은 저녁 먹고 별도의 글로 올리겠습니다.
15년 전