그 동안 2부리그도 문제가 어려워져서 미듐도 못 푸는 경우가 있었는데, 전반적으로 쉬운 SRM이었습니다.
(Hard를 푼 사람이 100명이 넘어요 >_< , Hard한번도 풀어본 적이 없는 제가 다 풀고도 시간이 30분 가까이 남았을 정도니까요)
1부리그 올라가기 전에 Hard한번 풀어보고 올라가는 게 소원이었는데(그 동안 한번도 Hard를 풀어본 적이 없습니다 ㅠ_ㅠ)
하드도 풀고, 1부리그로 올라가기도 해서 개인적으로는 뜻깊은운좋은 SRM이었습니다.
기왕에 2부리그 한국인 중에 1등을 하고 싶었으나...이번에 2부리그 SRM 1등이 한국인이십니다. ( dlwjdans , 이정문 ) 이란 아뒤를 쓰시는 분이구요. Petr는 3등하고도 레이팅이 떨어졌네요 >_<. ohhenrie라는 아뒤를 쓰는 중학생도 처음 참가했네요(하계중학교?, 중학생한테 발리면 어떻하죠?) 한국인중에 1등하신 일루님 축하드립니다 :) , 종만님은 1000 fail하고도 25등이라능...ㄷㄷㄷ;;; Gumx님이 1부리그 250 fastest 먹으셨네요- ㅋ
문제는 상당히 쉬운 편이므로 간단히 쓰겠습니다.
Easy (250 pts.)
문제 설명
공식에 의해서 A0, A1, A2, ... An까지 값이 나옵니다. 그 배열 중에 제일 값의 차이가 적게 나는 값을 리턴하면 됩니다.
문제 해법
[spoiler="더 보기..."]
값은 문제에 나온 대로 구하면 되고, 제일 거리가 작은 쌍을 어떻게 찾을까요?
만약, 각각마다 나머지 모든 값들과 비교하면 N^2이 되서 최대 10000^2 인 1억번의 연산을 해야 할 수도 있습니다.
네 그냥 소팅 한 다음에 차례대로 비교하면 O(n)에 찾을 수 있습니다.
[code c++]
#define sz(v) ((int)(v).size())
#define F(i,a,b) for(int i=(a);i<(b);++i)
#define FSZ(i,a,v) F(i,a,sz(v))
#define all(v) v.begin(),v.end()
class MinDifference {
public:
int closestElements(int A0, int X, int Y, int M, int n) {
int rr;
vector vi(n, 0);
vi[0] = A0;
rr = INT_MAX;
for(int i=1; i<n; ++i) {
vi[i] = (vi[i-1]*X+Y)%M;
}
sort(all(vi));
for(int i=1; i<n; ++i) {
rr = min(abs(vi[i]-vi[i-1]), rr);
}
return rr;
}
[/code]
[/spoiler]
Medium (500 pts.)
문제 설명
x, x, y, y의 수가 있고 사이에 연산은 +, -, * 가 가능합니다. 연산의 우선순위는 없는 상황에서 주어진 값과 같은 값을 가지는
6 = 1+1+2*2 모양을 모두 몇 가지나 만들 수 있는지 알고 싶습니다.
문제 해법
[spoiler="더 보기..."]x,x,y,y를 배열하는 방법은 6가지, 연산은 3곳에 3가지씩 들어가므로 3^3=27가지 입니다.
6 * 27 = 162 가지 밖에 안되므로 모든 경우를 다 구해서 주어진 값과 같은 값을 가진 것을 세면 됩니다.
문제는 모든 경우를 어떻게 만드느냐 하는 것인데, x,x,y,y를 배열하는 방법은 next_permutation을 쓰면 쉽게 구합니다.
물론 저처럼 무식하게 하드 코딩해도 됩니다 -.-
[/spoiler]
Hard (900 pts.)
문제 설명
문자열을 왼쪽이 아닌 오른쪽으로만 이동시켜서 원하는 문자열이 수직으로 나오게 하고 싶습니다. 그때의 최소 이동 횟수를 구하면 됩니다.
"TOP"
" TIK"
"PPPO"
"OP"
이런 식으로 밀어서, 수직으로 TOP를 만들고 싶습니다.
문제 해법
[spoiler="더 보기..."]
복잡하게 생각하면, 상당히 복잡해질 수도 있지만, 각 라인마다 만들어야 할 문자가 정해져 있으므로 다른 Hard에 비해 상당히 쉽습니다. 각 자리마다 원하는 문자열을 만들려면 얼만큼의 이동이 필요한 지 계산해서 모든 자리에 대해서 계산해도 최대 50*50 정도에 처리가 가능하기 때문에 문제가 없습니다. 저 같은 경우는 문제를 잘못 읽고 왼쪽, 오른쪽 양쪽으로 밀어서 최소값을 구하도록 했다가 삽질을 좀 했습니다. 혹시 문자열을 구성할 수 없으면, -1을 반환하도록 하는 것에 주의하면 됩니다.
[code c++]
#define sz(v) ((int)(v).size())
#define F(i,a,b) for(int i=(a);i<(b);++i)
#define FSZ(i,a,v) F(i,a,sz(v))
#define all(v) v.begin(),v.end()
class MatchString {
public:
int getLen(string s, char c, int def) {
int dis = INT_MAX;
for(int i=def; i>=0; --i) {
if(i>=s.size()) continue;
if(s[i] == c) {
dis = min(dis, abs(def - i));
}
}
return dis;
}
int placeWords(string matchString, vector matchWords) {
int rr = INT_MAX;
int sum(0);
for(int i=0; i<50; ++i) {
sum = 0;
FSZ(j,0,matchWords) {
int v = getLen(matchWords[j], matchString[j], i);
if(v == INT_MAX) {
sum = INT_MAX;
break;
}
sum += v;
}
rr = min(rr, sum);
}
if(rr == INT_MAX) return -1;
return rr;
}
[/code]
[/spoiler]
nocut98
그 동안 2부리그도 문제가 어려워져서 미듐도 못 푸는 경우가 있었는데, 전반적으로 쉬운 SRM이었습니다.
(Hard를 푼 사람이 100명이 넘어요 >_< , Hard한번도 풀어본 적이 없는 제가 다 풀고도 시간이 30분 가까이 남았을 정도니까요)
1부리그 올라가기 전에 Hard한번 풀어보고 올라가는 게 소원이었는데(그 동안 한번도 Hard를 풀어본 적이 없습니다 ㅠ_ㅠ)
하드도 풀고, 1부리그로 올라가기도 해서 개인적으로는 뜻깊은운좋은 SRM이었습니다.
기왕에 2부리그 한국인 중에 1등을 하고 싶었으나...이번에 2부리그 SRM 1등이 한국인이십니다. ( dlwjdans , 이정문 ) 이란 아뒤를 쓰시는 분이구요. Petr는 3등하고도 레이팅이 떨어졌네요 >_<. ohhenrie라는 아뒤를 쓰는 중학생도 처음 참가했네요(하계중학교?, 중학생한테 발리면 어떻하죠?) 한국인중에 1등하신 일루님 축하드립니다 :) , 종만님은 1000 fail하고도 25등이라능...ㄷㄷㄷ;;; Gumx님이 1부리그 250 fastest 먹으셨네요- ㅋ
문제는 상당히 쉬운 편이므로 간단히 쓰겠습니다.
Easy (250 pts.)
문제 해법
[spoiler="더 보기..."]x,x,y,y를 배열하는 방법은 6가지, 연산은 3곳에 3가지씩 들어가므로 3^3=27가지 입니다.
6 * 27 = 162 가지 밖에 안되므로 모든 경우를 다 구해서 주어진 값과 같은 값을 가진 것을 세면 됩니다.
문제는 모든 경우를 어떻게 만드느냐 하는 것인데, x,x,y,y를 배열하는 방법은 next_permutation을 쓰면 쉽게 구합니다.
물론 저처럼 무식하게 하드 코딩해도 됩니다 -.-
[/spoiler]
Hard (900 pts.)
문제 설명
문자열을 왼쪽이 아닌 오른쪽으로만 이동시켜서 원하는 문자열이 수직으로 나오게 하고 싶습니다. 그때의 최소 이동 횟수를 구하면 됩니다.
문제 해법 matchWords) {
[spoiler="더 보기..."]
복잡하게 생각하면, 상당히 복잡해질 수도 있지만, 각 라인마다 만들어야 할 문자가 정해져 있으므로 다른 Hard에 비해 상당히 쉽습니다. 각 자리마다 원하는 문자열을 만들려면 얼만큼의 이동이 필요한 지 계산해서 모든 자리에 대해서 계산해도 최대 50*50 정도에 처리가 가능하기 때문에 문제가 없습니다. 저 같은 경우는 문제를 잘못 읽고 왼쪽, 오른쪽 양쪽으로 밀어서 최소값을 구하도록 했다가 삽질을 좀 했습니다. 혹시 문자열을 구성할 수 없으면, -1을 반환하도록 하는 것에 주의하면 됩니다.
[code c++]
#define sz(v) ((int)(v).size())
#define F(i,a,b) for(int i=(a);i<(b);++i)
#define FSZ(i,a,v) F(i,a,sz(v))
#define all(v) v.begin(),v.end()
class MatchString {
public:
int getLen(string s, char c, int def) {
int dis = INT_MAX;
for(int i=def; i>=0; --i) {
if(i>=s.size()) continue;
if(s[i] == c) {
dis = min(dis, abs(def - i));
}
}
return dis;
}
int placeWords(string matchString, vector
int rr = INT_MAX;
int sum(0);
for(int i=0; i<50; ++i) {
sum = 0;
FSZ(j,0,matchWords) {
int v = getLen(matchWords[j], matchString[j], i);
if(v == INT_MAX) {
sum = INT_MAX;
break;
}
sum += v;
}
rr = min(rr, sum);
}
if(rr == INT_MAX) return -1;
return rr;
}
[/code]
[/spoiler]
16년 전
6개의 댓글이 있습니다.
ltdtl
이정문...과 ohenrie라는 아이디를 쓰는 두 학생은 제가 가르쳤던 학생들인데..
TopCoder를 하다니...호호
16년 전 link
JongMan
햐 리토도 제자들 ㅋㅋㅋㅋㅋㅋㅋㅋ 아놔
nocut98 님, Div1 진출 축하 ~ :D 아레나에서 만나요!
16년 전 link
nocut98
리토도 님때문에 앞으로 중학생에게 발리게 생겼음 책임지세요 ㅠ_ㅠ (혹시 이미 발린겁니까?)
16년 전 link
ltdtl
그나저나 중딩들 영어 문제 어떻게 해석하고 푸나 모르겟네요 ㅋㅋ;
근데 ... submission보니까 이건 좀 안습인듯:
http://www.topcoder.com/stat?c=problem_solution&rm=269852&rd=12170&pm=8161&cr=22722395
ㅎㅎ return안하고 printf로 답을 출력하다니...에고..
16년 전 link
Megalusion
영어 해석은 잘하던데요 ㅋㅋ
ohhenrie는 정말 return으로 하라고 그토록 말했는데 printf를 하다니 ㅜㅜ
16년 전 link
nocut98
정말 귀엽네요 ^^
16년 전 link
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.