좀 전에서야 다 풀어봤네요.
워낙 잘하시는 분들이 많아서 DIV 2에 관심을 갖으실리 없지만 그래도 혹시나 하는 마음에, 그리고 정리하는 마음에 이렇게 로그를 남겨봅니다.
제가 Top Coder에 발을 붙인지 몇일 안됐고, 더더욱 통계페이지는 찾을 수가 없어서 그림을 첨부하지 못한 점 죄송합니다.
1. 250 PT - RussianSpeedLimits
기본속도는 60, 도시에서 나오게되면 속도는 90으로 바뀌고, 도시로 들어갈땐 다시 속도가 60으로 줄어듭니다.
그 외에는 도로에 맞게 속도가 설정되어 있는데요.
연속된 도로표지판을 주고, 현재 속도를 구하는 문제입니다.
도로표지판의 갯수는 1~50개 이구요,
각각의 사인은 "default" , "city", 그리고 1~100까지의 속도입니다.
[spoiler="풀이보기"]조금 시시할 정도로 단순한 문제입니다.
도시가 홀수 번 째 나올 때 기본속도를 90으로 바꿔주고 카운트를 하나 올려줍니다.
도시가 짝수 번 째 나올 때 기본속도를 60으로 바꿔주고 카운트를 초기화 합니다.
나머지는 인자값을 그대로 기록하고만 있으면 되지요 ^^
[/spoiler]
2. 500 PT - UnderscoreJustification
DIV 1 의 1번 문제와 동일한 문제였지요.
밑에 유키님께서 잘 설명해주셨다 싶이
[spoiler="더 보기..."]몇 개의 단어로 이루어진 문장이 하나 주어집니다. 각 단어들 사이에 한 개 이상의 공백을 집어넣어, 전체 문장을 width 만큼의 폭 에 맞춰 넣으려고 합니다. 이 때 가능한 문장들(공백을 포함한) 중에서 사전 식으로 가장 앞서는 것을 구하는 문제입니다.
가장 긴 공백의 길이와 가장 짧은 공백의 길이는 1까지 차이날 수 있습니다. 즉, 공백을 한 쪽에 몰아서 넣으면 안되고 전체적으로 고르게 넣어야 합니다. 또한 사전 순서의 기준은 A < … < Z < _(공백) < a < … < z 으로 합니다. 단어의 개수는 최대 10개까지 가능하며, 각각의 단어는 최대 10자까지 입니다. width는 200 이하이며, 전체 단어 길이의 합 + 단어의 개수 - 1 이상입니다.
[/spoiler]
이런 문제입니다.
[spoiler="풀이보기"]저는 공백이 들어갈 수 있는 모든 경우의 수를 계산하고, 그 중에서 최소 원소값을 찾는 방법으로 구현하였습니다.
기본 공백 크기인 spaces를 (width - len) / (words.size()-1) 로 계산한다면 남는 공간의 크기는 (width - len) % (words.size()-1) 가 될 텐데요. spaces만큼의 길이를 갖는 "_"를 벡터에 넣고, 남는 공간의 크기에 대한 보정을 해줍니다.
그리고 spaces 벡터를 정렬한뒤 next_permutatoin 으로 모든 조합 결과를 생성하고 그 결과중에서 최소 원소 뽑아내면 문제가 해결됩니다.
[/spoiler]
3. 1000 PT - SummingArithmeticProgressions
수식 편집이 된다면 참 좋겠지만.. 수식 편집이 안되네요. 양의 정수 x, d에서 x, x+d, x+2*d, ...., x+(k-1)*d 와 같은 수열이 있다고 합니다.
정수값인 left와 right가 주어졌을 때 left와 right 사이에 위의 수열에서 나오는 숫자가 총 몇개인지를 판단하는 문제입니다.
left와 right는 1~1000000000, k는 2~5사이의 숫자가 주어진다고 하네요
[spoiler="풀이보기"]제가 문제들을 많이 안풀어봤긴 하지만, 정수론 문제는 거의 처음 풀어보네요.
정수론 중에서도 일차합동에 관한 내용인데요, k가 2~5인 각각의 케이스마다 식을 세워서 풀어주시면 됩니다.
저의 경우에는 right까지의 해의 갯수 - left-1까지의 해의 갯수 로 해결을 하였습니다.
문제 난이도가 조금 높았던데다가, 정수론 과목을 수강하지 않아서 해결하는데 꽤 어려움이 있었네요..
[/spoiler]
2부 리그라고도 할 수 있는 DIV의 문제지만 1000점짜리 문제들은 조금 고민을 해봐야되는 문제들이 많이나오더라구요.
다음주나 다다음주 대회부터는 대회시간에 맞춰서 참석해서 보다 공정한 평가를 받아봐야하겠습니다. ^^
Rada
좀 전에서야 다 풀어봤네요.
워낙 잘하시는 분들이 많아서 DIV 2에 관심을 갖으실리 없지만 그래도 혹시나 하는 마음에, 그리고 정리하는 마음에 이렇게 로그를 남겨봅니다.
제가 Top Coder에 발을 붙인지 몇일 안됐고, 더더욱 통계페이지는 찾을 수가 없어서 그림을 첨부하지 못한 점 죄송합니다.
1. 250 PT - RussianSpeedLimits
기본속도는 60, 도시에서 나오게되면 속도는 90으로 바뀌고, 도시로 들어갈땐 다시 속도가 60으로 줄어듭니다.
그 외에는 도로에 맞게 속도가 설정되어 있는데요.
연속된 도로표지판을 주고, 현재 속도를 구하는 문제입니다.
도로표지판의 갯수는 1~50개 이구요,
각각의 사인은 "default" , "city", 그리고 1~100까지의 속도입니다.
[spoiler="풀이보기"]조금 시시할 정도로 단순한 문제입니다.
도시가 홀수 번 째 나올 때 기본속도를 90으로 바꿔주고 카운트를 하나 올려줍니다.
도시가 짝수 번 째 나올 때 기본속도를 60으로 바꿔주고 카운트를 초기화 합니다.
나머지는 인자값을 그대로 기록하고만 있으면 되지요 ^^
[/spoiler]
2. 500 PT - UnderscoreJustification
DIV 1 의 1번 문제와 동일한 문제였지요.
밑에 유키님께서 잘 설명해주셨다 싶이
[spoiler="더 보기..."]몇 개의 단어로 이루어진 문장이 하나 주어집니다. 각 단어들 사이에 한 개 이상의 공백을 집어넣어, 전체 문장을 width 만큼의 폭 에 맞춰 넣으려고 합니다. 이 때 가능한 문장들(공백을 포함한) 중에서 사전 식으로 가장 앞서는 것을 구하는 문제입니다.
가장 긴 공백의 길이와 가장 짧은 공백의 길이는 1까지 차이날 수 있습니다. 즉, 공백을 한 쪽에 몰아서 넣으면 안되고 전체적으로 고르게 넣어야 합니다. 또한 사전 순서의 기준은 A < … < Z < _(공백) < a < … < z 으로 합니다. 단어의 개수는 최대 10개까지 가능하며, 각각의 단어는 최대 10자까지 입니다. width는 200 이하이며, 전체 단어 길이의 합 + 단어의 개수 - 1 이상입니다.
[/spoiler]
이런 문제입니다.
[spoiler="풀이보기"]저는 공백이 들어갈 수 있는 모든 경우의 수를 계산하고, 그 중에서 최소 원소값을 찾는 방법으로 구현하였습니다.
기본 공백 크기인 spaces를 (width - len) / (words.size()-1) 로 계산한다면 남는 공간의 크기는 (width - len) % (words.size()-1) 가 될 텐데요. spaces만큼의 길이를 갖는 "_"를 벡터에 넣고, 남는 공간의 크기에 대한 보정을 해줍니다.
그리고 spaces 벡터를 정렬한뒤 next_permutatoin 으로 모든 조합 결과를 생성하고 그 결과중에서 최소 원소 뽑아내면 문제가 해결됩니다.
[/spoiler]
3. 1000 PT - SummingArithmeticProgressions
수식 편집이 된다면 참 좋겠지만.. 수식 편집이 안되네요. 양의 정수 x, d에서 x, x+d, x+2*d, ...., x+(k-1)*d 와 같은 수열이 있다고 합니다.
정수값인 left와 right가 주어졌을 때 left와 right 사이에 위의 수열에서 나오는 숫자가 총 몇개인지를 판단하는 문제입니다.
left와 right는 1~1000000000, k는 2~5사이의 숫자가 주어진다고 하네요
[spoiler="풀이보기"]제가 문제들을 많이 안풀어봤긴 하지만, 정수론 문제는 거의 처음 풀어보네요.
정수론 중에서도 일차합동에 관한 내용인데요, k가 2~5인 각각의 케이스마다 식을 세워서 풀어주시면 됩니다.
저의 경우에는 right까지의 해의 갯수 - left-1까지의 해의 갯수 로 해결을 하였습니다.
문제 난이도가 조금 높았던데다가, 정수론 과목을 수강하지 않아서 해결하는데 꽤 어려움이 있었네요..
[/spoiler]
2부 리그라고도 할 수 있는 DIV의 문제지만 1000점짜리 문제들은 조금 고민을 해봐야되는 문제들이 많이나오더라구요.
다음주나 다다음주 대회부터는 대회시간에 맞춰서 참석해서 보다 공정한 평가를 받아봐야하겠습니다. ^^
16년 전