대선배 ainu7님의 압박+협박으로 에디토리얼을 쓰게되었습니다.
우선 순위표를 봐주세요.
음... -.-; 세 문제 모두 맞춘 사람은 없습니다.. 차분하게 3개 모두 풀었다면 1등할 수 있었던 SRM..
1번) DiceGame
John은 1~6까지 눈이 적힌 평범한 주사위를 던지면서 던져서 나온 눈의 수 만큼 엄마한테 캔디를 받아 먹습니다. John의 목표는 최소 candies만큼의 사탕을 받는 겁니다. 목표를 이루기 위해 주사위 던지는 횟수의 기대값은 얼마일까요?
2번) TheHomework
two lists of integers가 주어졌을 때, 첫 번째 list를 적절히 최소 횟수의 연산 적용을 통해 두 번째 list와 동일하게 만드는 것이 목표 (수 들의 순서는 중요치 않음)
연산1) 임의의 정수들을 첫 리스트에 추가. 새로 추가되는 정수들의 개수는 연산 적용 전의 리스트에 들어있던 수들의 개수보다 많아서는 안됨
연산 2) 리스트에서 몇몇 수들을 지움. 지워지는 수들의 개수는 원래 리스트에 들어있던 수들의 개수의 반 보다 많아서는 안됨
연산 3) 리스트에 들어있는 수들의 값을 임의로 바꿈. 값이 바뀌는 수들의 개수는 원래 리스트에 들어있던 수들의 개수의 반 보다 많아서는 않됨
3번) 평면 위에 정사각형들이 마구 주어집니다. 정사각형들은 영문 알파벳으로 된 이름을 가집니다. 정사각형을 일정한 순서로 선택을 했을 때, 첫 번째 정사각형을 제외하고 나머지 선택된 정사각형들은 각자 자신 이전에 선택된 정사각형에 포함이 되도록 k개의 정사각형을 뽑고 싶습니다. 이것이 우선 가능한지 알아보고, 가능한 경우 이름을 나열했을 때 사전순으로 가장 앞서는 경우를 뽑습니다 (가장 바깥쪽에 있는 정사각형부터 이름을 나열) - 이 순서에 대해서는 문제를 참고 바랍니다.
완전히 겹친 정사각형 (네 꼭지점 좌표가 모두 같을때)은 서로가 서로를 포함한다고 말 할 수 있습니다 - 이 문제에선.
-- 풀이
1) 간단합니다. E(X)를 캔디를 최소 X개 모으기 위해 주사위를 던지는 횟수에 대한 기대값이라 하면 (X>=1),
E(X) = (E(X-1) + E(X-2)+ ... + E(X-6)) / 6 + 1 if X>= 1
E(X) = 0 if X<0
이렇게 정의하고 문제를 풀면 됩니다. (아마도?)
2) 그리디가 되는지 증명해볼 겨를이 없어서 상태공간 탐색을 했습니다.
여러가지 방법이 있는데 저는 상태공간을 최적화 하지 않아서 공간이 좀 큽니다.
탑코더에 올라온 에디토리얼은 제 방법보다 효율적입니다.
저는 우선 두 리스트가 완전히 같은지 비교해보고 (특수 처리라고 하나요), 다를 경우에 한해서 아래와 같이 수를 구합니다:
첫 리스트와 두 번째 리스트에서 같은 수의 개수 A. 예를 들어 {1, 1, 3, 3, 5} 이고 {1, 3, 3, 4} 인 경우 A = 3.
첫 리스트의 크기 - A (as B),
두번째 리스트의 크기 - A (as C).
여기서 입력으로 주어지는 두 리스트의 크기가 50 이므로, B와 C는 50을 넘을 일이 절대 없습니다 - 넘는 경우는 최적해가 될 수 없습니다. 왜냐면 쓸데없이 수를 많이 추가했고, 그 수를 지우는데 연산을 또 적용해야 하므로...
그럼 이 A, B, C에 대해 상태공간이 약 50 x 50 x 50 가지가 가능합니다. 이를 탐색하는데,
각 연산을 적용하면
연산1) 수 추가: 수를 추가하면 당연히 두 번째 리스트에 있는 수와 같은 수들을 추가해서 A를 늘리고 B와 C를 줄여야 합니다. 이 때 얼마나 줄여야 할지에 대해서는 가능한 가지수를 모두 시도해 봅니다.
연산2) 수 변경: 기존의 첫 번째 리스트에 있는 수들 중 두 번째 리스트의 수들과 일치하지 않는 수들을 두 번째 리스트에 있는 수들로 바꿔주어 A를 늘리고 B를 줄입니다. 주의 할 점은 원래 첫 번째 리스트에 있는 수 개수의 절반보다 많은 수들의 값을 변경할 수 없다는 점 입니다. 연산3) 수 지우기도 비슷하게 합니다.
상태공간이 약 50x50x50이 가능하고(실제 탐색 가능한 공간은 훨씩 적음), 각 상태공간에 대해 3 x 50 정도의 (평균적으로는 훨씬 적음) 가능한 수들을 살펴보는데 제한 시간내에 나옵니다. 상태공간을 좀 더 효율적으로 줄일 수 있지만, 저는 미처 생각할 겨를이 없었네요.
문제3) 대회 때는 틀렸는데, 가장 큰 문제는 서로 다른 정사각형이 같은 이름을 가질 수 있다는 점 때문 이었습니다. 당연히 이름이 다르겠지 하고 풀었는데, (문제를 제대로 읽지 않은 탓) 이름이 같은 경우 문제점은 사전순으로 빠른 sequence of squares를 찾을 때, 이름이 같은 두 정사각형을 놓고 아무 생각없이 하나를 선택할 경우, 그 정사각형 안에 ZZZZ의 이름의 정사각형이 포함되어있고, 다른 정사각형 안에 AAAA가 포함되어 있다면, 사전순으로 앞선 경우를 선택하지 못하기 때문에 틀리게 됩니다. 많은 사람들이 이 부분에서 실수를 한 듯 보입니다.
우선 문제를 간단히 살펴보면, 자신보다 크기가 큰 정사각형은 포함할 수 없으므로, 정사각형들을 변의 길이 순으로 정렬하고 나면 항상 뒤쪽에 정렬된 정사각형만이 앞에 놓인 정사각형을 포함할 수 있게 됩니다 (크기가 같고 완전히 겹친 경우는 서로 포함할 수 있지만, 이름 "역"순으로 정렬을 합니다. 즉 알파벳 상 나중에 나오는 정사각형이 알파벳 상 먼저 나오는 정사각형의 '안'에 포함되었다고 하면 문제의 조건대로 사전순으로 앞선 직사각형 수열을 구성할 수 있습니다).
정렬을 하고 나면 문제가 쉬워집니다. 우선 n^2 의 간단한 DP를 통해 i번째 정사각형을 가장 바깥쪽에 두었을 때의 최대 길이 정사각형 수열의 길이를 구해봅니다.
그 후, 가장 길이가 긴 경우가 k 이상인지 체크해보고, k미만이면 빈 vector를 리턴합니다.
이제 답을 찾아야 하는데,
자신이 가장 바깥쪽에 놓였을 때 가장 길이가 긴 경우가 k이상이 되는 직사각형들을 모두 queue에 넣어둡니다. 답이 될 가능성이 있기 때문입니다. 이 중 사전순으로 이름이 가장 앞서는 '이름'을 골라서 return할 vector 변수에 넣어둡니다. 또, 이름이 같은 녀석들은 모두 미리 저장을 해둡니다. queue를 비웁니다.
이름이 같은 녀석들 각각에 대해서, 이녀석들이 포함하고 있는 정사각형 중 가장 긴 길이가 k-1이상이 되는 직사각형들을 모두 queue에 넣어둡니다. 이 작업을 k번 반복하고나면, return 할 vector에는 이름이 k개 들어가게 되고, 이게 정답이 됩니다.
아래의 예제를 보면서 어떤 식으로 답을 구하게 되는지 살펴 봅시다.
사각형들의 이름이 같아 헷갈리므로 옆에 색으로 구분을 했습니다. 모양이 직사각형인건 이해해 주세요.
위와 같은 예제의 경우 직사각형 정렬 후 순서는:
(녹)ZZZ가 가장 작고 (녹)AAA가 가장 크다고 생각합니다.
k가 3인 경우,
처음 queue에는 [(적)AAA, (회색)BBB, (청)AAA, (녹)AAA] 가 삽입됩니다. 순서대로 3, 4, 3, 3 길이의 정사각형 수열을 만들 수 있기 때문입니다.
그 중 사전순으로 앞서는 AAA가 리턴할 벡터의 첫 번째 원소로 들어가게 되고,
QUEUE를 초기화 합니다.
(적)AAA에 포함된 정사각형들 중 길이 2 이상의 정사각형 수열을 만들 수 있는 정사각형 모두 (여기선 (적)BBB 하나 뿐) QUEUE에 들어갑니다.
(청)AAA에 포함된 정사각형들 중 길이 2 이상의 정사각형 수열을 만들 수 있는 정사각형 모두 (여기선 (청)BBB 하나) 가 QUEUE에 들어갑니다.
(녹)AAA도 마찬가지로 (녹)BB를 QUEUE에 넣습니다.
작업이 끝난 후 QUEUE에는 [(적)BBB, (청)BBB, (녹)BB, (녹)B]가 들어가 있습니다.
마찬가지로 이 중 사전순으로 가장 앞서는 B가 리턴될 벡터의 두 번째 원소로 삽입됩니다.
QUEUE가 초기화 되고 (녹)B의 내부에 포함된, 길이 1을 만들 수 있는 (녹)ZZZ가 QUEUE에 삽입됩니다.
같은 과정을 거쳐서 리턴될 벡터의 세 번째 원소로 ZZZ가 삽입됩니다.
이제 모든 과정이 끝났으므로 벡터를 리턴하면 정답은 {AAA, B, ZZZ}가 됩니다.
만약 여기서 (녹)B가 (녹)BB였다면,
QUEUE에는 [(녹)CC, (녹)C, (녹)A, (녹)ZZZ]가 삽입되었을 것이고 정답은 {AAA, BB, A}가 되었을 겁니다.
1000 점 짜리 제가 practice room에서 system test를 통과한 소스를 함께 첨부합니다.
제 소스가 제가 여기에 설명한 방법을 그대로 구현한 것이고,
에디토리얼의 풀이나 대회 당시 통과한 사람들의 풀이는 제 방법과 다를 수도 있습니다.
ltdtl
대선배 ainu7님의 압박+협박으로 에디토리얼을 쓰게되었습니다.
우선 순위표를 봐주세요.
음... -.-; 세 문제 모두 맞춘 사람은 없습니다.. 차분하게 3개 모두 풀었다면 1등할 수 있었던 SRM..
1번) DiceGame
John은 1~6까지 눈이 적힌 평범한 주사위를 던지면서 던져서 나온 눈의 수 만큼 엄마한테 캔디를 받아 먹습니다. John의 목표는 최소 candies만큼의 사탕을 받는 겁니다. 목표를 이루기 위해 주사위 던지는 횟수의 기대값은 얼마일까요?
2번) TheHomework
two lists of integers가 주어졌을 때, 첫 번째 list를 적절히 최소 횟수의 연산 적용을 통해 두 번째 list와 동일하게 만드는 것이 목표 (수 들의 순서는 중요치 않음)
연산1) 임의의 정수들을 첫 리스트에 추가. 새로 추가되는 정수들의 개수는 연산 적용 전의 리스트에 들어있던 수들의 개수보다 많아서는 안됨
연산 2) 리스트에서 몇몇 수들을 지움. 지워지는 수들의 개수는 원래 리스트에 들어있던 수들의 개수의 반 보다 많아서는 안됨
연산 3) 리스트에 들어있는 수들의 값을 임의로 바꿈. 값이 바뀌는 수들의 개수는 원래 리스트에 들어있던 수들의 개수의 반 보다 많아서는 않됨
3번) 평면 위에 정사각형들이 마구 주어집니다. 정사각형들은 영문 알파벳으로 된 이름을 가집니다. 정사각형을 일정한 순서로 선택을 했을 때, 첫 번째 정사각형을 제외하고 나머지 선택된 정사각형들은 각자 자신 이전에 선택된 정사각형에 포함이 되도록 k개의 정사각형을 뽑고 싶습니다. 이것이 우선 가능한지 알아보고, 가능한 경우 이름을 나열했을 때 사전순으로 가장 앞서는 경우를 뽑습니다 (가장 바깥쪽에 있는 정사각형부터 이름을 나열) - 이 순서에 대해서는 문제를 참고 바랍니다.
완전히 겹친 정사각형 (네 꼭지점 좌표가 모두 같을때)은 서로가 서로를 포함한다고 말 할 수 있습니다 - 이 문제에선.
-- 풀이
1) 간단합니다. E(X)를 캔디를 최소 X개 모으기 위해 주사위를 던지는 횟수에 대한 기대값이라 하면 (X>=1),
E(X) = (E(X-1) + E(X-2)+ ... + E(X-6)) / 6 + 1 if X>= 1
E(X) = 0 if X<0
이렇게 정의하고 문제를 풀면 됩니다. (아마도?)
2) 그리디가 되는지 증명해볼 겨를이 없어서 상태공간 탐색을 했습니다.
여러가지 방법이 있는데 저는 상태공간을 최적화 하지 않아서 공간이 좀 큽니다.
탑코더에 올라온 에디토리얼은 제 방법보다 효율적입니다.
저는 우선 두 리스트가 완전히 같은지 비교해보고 (특수 처리라고 하나요), 다를 경우에 한해서 아래와 같이 수를 구합니다:
첫 리스트와 두 번째 리스트에서 같은 수의 개수 A. 예를 들어 {1, 1, 3, 3, 5} 이고 {1, 3, 3, 4} 인 경우 A = 3.
첫 리스트의 크기 - A (as B),
두번째 리스트의 크기 - A (as C).
여기서 입력으로 주어지는 두 리스트의 크기가 50 이므로, B와 C는 50을 넘을 일이 절대 없습니다 - 넘는 경우는 최적해가 될 수 없습니다. 왜냐면 쓸데없이 수를 많이 추가했고, 그 수를 지우는데 연산을 또 적용해야 하므로...
그럼 이 A, B, C에 대해 상태공간이 약 50 x 50 x 50 가지가 가능합니다. 이를 탐색하는데,
각 연산을 적용하면
연산1) 수 추가: 수를 추가하면 당연히 두 번째 리스트에 있는 수와 같은 수들을 추가해서 A를 늘리고 B와 C를 줄여야 합니다. 이 때 얼마나 줄여야 할지에 대해서는 가능한 가지수를 모두 시도해 봅니다.
연산2) 수 변경: 기존의 첫 번째 리스트에 있는 수들 중 두 번째 리스트의 수들과 일치하지 않는 수들을 두 번째 리스트에 있는 수들로 바꿔주어 A를 늘리고 B를 줄입니다. 주의 할 점은 원래 첫 번째 리스트에 있는 수 개수의 절반보다 많은 수들의 값을 변경할 수 없다는 점 입니다. 연산3) 수 지우기도 비슷하게 합니다.
상태공간이 약 50x50x50이 가능하고(실제 탐색 가능한 공간은 훨씩 적음), 각 상태공간에 대해 3 x 50 정도의 (평균적으로는 훨씬 적음) 가능한 수들을 살펴보는데 제한 시간내에 나옵니다. 상태공간을 좀 더 효율적으로 줄일 수 있지만, 저는 미처 생각할 겨를이 없었네요.
문제3) 대회 때는 틀렸는데, 가장 큰 문제는 서로 다른 정사각형이 같은 이름을 가질 수 있다는 점 때문 이었습니다. 당연히 이름이 다르겠지 하고 풀었는데, (문제를 제대로 읽지 않은 탓) 이름이 같은 경우 문제점은 사전순으로 빠른 sequence of squares를 찾을 때, 이름이 같은 두 정사각형을 놓고 아무 생각없이 하나를 선택할 경우, 그 정사각형 안에 ZZZZ의 이름의 정사각형이 포함되어있고, 다른 정사각형 안에 AAAA가 포함되어 있다면, 사전순으로 앞선 경우를 선택하지 못하기 때문에 틀리게 됩니다. 많은 사람들이 이 부분에서 실수를 한 듯 보입니다.
우선 문제를 간단히 살펴보면, 자신보다 크기가 큰 정사각형은 포함할 수 없으므로, 정사각형들을 변의 길이 순으로 정렬하고 나면 항상 뒤쪽에 정렬된 정사각형만이 앞에 놓인 정사각형을 포함할 수 있게 됩니다 (크기가 같고 완전히 겹친 경우는 서로 포함할 수 있지만, 이름 "역"순으로 정렬을 합니다. 즉 알파벳 상 나중에 나오는 정사각형이 알파벳 상 먼저 나오는 정사각형의 '안'에 포함되었다고 하면 문제의 조건대로 사전순으로 앞선 직사각형 수열을 구성할 수 있습니다).
정렬을 하고 나면 문제가 쉬워집니다. 우선 n^2 의 간단한 DP를 통해 i번째 정사각형을 가장 바깥쪽에 두었을 때의 최대 길이 정사각형 수열의 길이를 구해봅니다.
그 후, 가장 길이가 긴 경우가 k 이상인지 체크해보고, k미만이면 빈 vector를 리턴합니다.
이제 답을 찾아야 하는데,
자신이 가장 바깥쪽에 놓였을 때 가장 길이가 긴 경우가 k이상이 되는 직사각형들을 모두 queue에 넣어둡니다. 답이 될 가능성이 있기 때문입니다. 이 중 사전순으로 이름이 가장 앞서는 '이름'을 골라서 return할 vector 변수에 넣어둡니다. 또, 이름이 같은 녀석들은 모두 미리 저장을 해둡니다. queue를 비웁니다.
이름이 같은 녀석들 각각에 대해서, 이녀석들이 포함하고 있는 정사각형 중 가장 긴 길이가 k-1이상이 되는 직사각형들을 모두 queue에 넣어둡니다. 이 작업을 k번 반복하고나면, return 할 vector에는 이름이 k개 들어가게 되고, 이게 정답이 됩니다.
아래의 예제를 보면서 어떤 식으로 답을 구하게 되는지 살펴 봅시다.
사각형들의 이름이 같아 헷갈리므로 옆에 색으로 구분을 했습니다. 모양이 직사각형인건 이해해 주세요.
위와 같은 예제의 경우 직사각형 정렬 후 순서는:
(녹)ZZZ가 가장 작고 (녹)AAA가 가장 크다고 생각합니다.
k가 3인 경우,
처음 queue에는 [(적)AAA, (회색)BBB, (청)AAA, (녹)AAA] 가 삽입됩니다. 순서대로 3, 4, 3, 3 길이의 정사각형 수열을 만들 수 있기 때문입니다.
그 중 사전순으로 앞서는 AAA가 리턴할 벡터의 첫 번째 원소로 들어가게 되고,
QUEUE를 초기화 합니다.
(적)AAA에 포함된 정사각형들 중 길이 2 이상의 정사각형 수열을 만들 수 있는 정사각형 모두 (여기선 (적)BBB 하나 뿐) QUEUE에 들어갑니다.
(청)AAA에 포함된 정사각형들 중 길이 2 이상의 정사각형 수열을 만들 수 있는 정사각형 모두 (여기선 (청)BBB 하나) 가 QUEUE에 들어갑니다.
(녹)AAA도 마찬가지로 (녹)BB를 QUEUE에 넣습니다.
작업이 끝난 후 QUEUE에는 [(적)BBB, (청)BBB, (녹)BB, (녹)B]가 들어가 있습니다.
마찬가지로 이 중 사전순으로 가장 앞서는 B가 리턴될 벡터의 두 번째 원소로 삽입됩니다.
QUEUE가 초기화 되고 (녹)B의 내부에 포함된, 길이 1을 만들 수 있는 (녹)ZZZ가 QUEUE에 삽입됩니다.
같은 과정을 거쳐서 리턴될 벡터의 세 번째 원소로 ZZZ가 삽입됩니다.
이제 모든 과정이 끝났으므로 벡터를 리턴하면 정답은 {AAA, B, ZZZ}가 됩니다.
만약 여기서 (녹)B가 (녹)BB였다면,
QUEUE에는 [(녹)CC, (녹)C, (녹)A, (녹)ZZZ]가 삽입되었을 것이고 정답은 {AAA, BB, A}가 되었을 겁니다.
1000 점 짜리 제가 practice room에서 system test를 통과한 소스를 함께 첨부합니다.
제 소스가 제가 여기에 설명한 방법을 그대로 구현한 것이고,
에디토리얼의 풀이나 대회 당시 통과한 사람들의 풀이는 제 방법과 다를 수도 있습니다.
16년 전