10개의 댓글이 있습니다.
-
-
시영(unbing) -
Hard 문제 같은 경우는 LXXL인 경우 무조건 승부가 난다는 것을 이용해서 효과적으로 하는 방법이 있다고 들었어요.
만약 LXXL을 만들 수 없으면 optimal play에서 Draw인게 증명이 가능하다고 우리학교 학생이 그랬는데 자세한것은 기억이 안난다네요 ㅋㅋ;; (물론 예제 2번 처럼 한번에 LOL을 만드는 경우는 예외죠)
아이디어는 예를 들어서 XXXLXX 일때는 LXXLXX로 만들면 이기고, XXXLX인 경우는 LXXL이 생기면 지니까 OXXLX로 그런 경우를 막는다입니다. 즉, LXXL을 만들었을 때 나머지 X의 개수가 짝수면 이기는거고 홀수면 지니까 OXXL을 만드는 식입니다.
더 생각해 볼것은 LXXL의 형태가 여러곳에 생기는 것인데, 이도 매우 비슷하게 풀리는 것 같습니다 (가운데의 X의 개수가 두개(짝수)이기 때문에)
예제 마지막 경우인 XXXXXXXXXXXXXXXX 인 경우 John은 LXXL이 생기면 전체 X가 짝수라 집니다. 그리고 LXXL이 여러군데에 생기면 경기가 빨리 끝나기 때문에 최대한 LXXL을 막는 방향으로 해야겠지요 (아예 안 생기게 하는게 최적입니다 John의 경우)
그래서 XXXXXXXOXXXXXXXX 이런 식이 되고 그러면 Brus는 LXXL을 만들기 위해 X가 가장많이 연속한 곳 가운데에 L을 심습니다.
XXXXXXXOXXXXLXXX 이러면 John은 LXXL을 막고 싶지만 두 군데에 생기기 때문에 한곳밖에 못막겠죠? 그러면 나머지 곳에 Brus가 LXXL을 만듭니다. XXXXXXXOXOXXLXXL이 생기고 John은 LXXL의 갯수를 최소화하기 위해 XXXOXXXOXOXXLXXL 이런 식으로 만듭니다. 결국 LXXL이 하나밖에 안생겼으니까 경기는 끝까지 가는거죠 (두개 생기면 총 X개수 -2 이런식이 됩니다.)
이런식을 이용하면 스트링의 길이가 더 길어져도 풀리지 않을까요? 제 생각(사실은 학교 토론에서 들은 아이디어들 ㅋㅋ)이 틀렸다면 댓글달아주세요 ㅠ ㅋㅋ 그리고 정확하게 어떻게 코드로 옮겨야 할지도 더 생각해봐야할 것 같습니다 ㅠ
17년 전 link
-
-
-
시영(unbing) -
아 역시 포럼에 잇군요 ㅋㅋㅋ 얼마나 많은 LXXL을 만들수 있느냐가 정하기 단순하지 않은것 같네요 -0- ㅋ
17년 전 link
-
-
-
시영(unbing) -
일주일에 한번해요 ㅋㅋ 근데 아직 토론을 완전히 소화할만큼 영어가 안되네요 ㅠㅠ ㅋㅋ
17년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
JongMan
안녕하세요, JM 입니다.
SRM428 은 무지 쉬운 easy 와 꽤나 어려웠던 medium, 그리고 코딩은 어렵지 않지만 precalc 를 제대로 해야 했던 안드로 hard 덕분에 안드로로 달려간 매치였습니다. 덕분에 한국인 전원은 모두 이지만 풀고 집단 사망... 250에 챌린지 하나로 96위에 올라간 helloneo 님, 250 레코드 하나만으로 -_-; 102위에 올라간 JongMan, 107위의 KooKyungryeol 이 한국 top3 이었습니다.
1등한 건 아니긴 한데, 너무 말린 관계로 가슴이 아파 반성하는 의미로 장문의 에디토리얼을 써 봅니다. 음훗
250 - TheLuckyString
문제 설명
문자열에서 같은 문자가 두 번 반복되는 일이 없을 때, 이 문자열을 Lucky String 이라고 합니다. 길이가 10 이하인 문자열 s 가 주어질 때, 이 문자열의 문자의 순서를 바꿔서 만들 수 있는 Lucky String 의 수는?
Key Insight
s의 문자열을 재배열할 수 있는 수 = 10! = 360만
해법
이런 문제를 보면 제일 먼저 10! 을 윈도우 계산기에서 계산해 봅시다. :) 3백만은 충분히 시간 안에 모든 문자열을 계산해 볼 수 있는 방법이죠. 재귀호출을 이용해 모든 문자열을 만들어 보면서 Lucky String 의 수를 셀 수 있습니다. 그게 아니라면, C++ STL 에 있는 next_permutation 을 쓸 수 있는데요, 이를 이용해 모든 문자열을 간단하게 만들 수 있습니다. 아래 코드처럼요.
~~~ cpp
struct TheLuckyString
{
int count(string s)
{
int ret = 0;
sort(s.begin(), s.end());
do
{
bool ok = true;
for(size_t i = 0; i < s.size(); ++i)
if(s[i] == s[i+1])
{
ok = false; break;
}
if(ok) ++ret;
} while(next_permutation(s.begin(), s.end()));
return ret;
}
};
따라서, 위와 같은 행렬 T 를 만들어 준 뒤, matexpsum 으로 T + T2 + T3 + .. + Tn+1/2 를 구한 뒤, 이것을 [1 0 0 .. 0] 에 곱해 준 다음, 벡터의 모든 원소를 더하면 답을 구할 수 있습니다.... orz
너무 긴 설명에 비해, 짧은 소스 코드 나갑니다.
~~~ cpp
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const ll M = 1234567891;
typedef vector > matrix;
matrix operator * (const matrix& a, const matrix& b)
{
// 생략
}
matrix operator + (const matrix& a, const matrix& b)
{
// 생략
}
// returns an identity matrix of given size
matrix identity(int size)
{
matrix ret(size, size);
for(int i = 0; i < size; ++i)
ret[i][i] = 1;
return ret;
}
// returns ab
matrix matexp(const matrix& a, int b)
{
matrix ret = identity(a.size());
matrix unit = a;
while(b > 0)
{
if(b % 2) ret = ret * unit;
b /= 2;
unit = unit * unit;
}
return ret;
}
// returns a+a2+a3+..+ab
matrix matexpsum(const matrix& a, int b)
{
if(b == 0) return matrix(a.size(), a.size());
// 홀수라면 별도처리
if(b % 2) return a * (identity(a.size()) + matexpsum(a, b-1));
int half = b/2;
// a+a2+..+ahalf
matrix first = matexpsum(a, half);
// 뒷쪽 절반
matrix second = first * matexp(a, half);
return first + second;
}
struct TheLongPalindrome
{
int count(int n, int k)
{
k = min(k, (n+1)/2);
matrix T(k+1, k+1);
for(int i = 1; i <= k; ++i)
{
T[i][i] = i;
T[i][i-1] = (26 - i + 1);
}
matrix even = matexpsum(T, n/2);
matrix odd = matexpsum(T, (n+1)/2);
ll ret = 0;
for(int c = 1; c <= k; ++c)
{
ret = (ret + even[c][0]) % M;
ret = (ret + odd[c][0]) % M;
}
return ret;
}
};
17년 전