태터데스크 관리자

도움말
닫기
적용하기   첫페이지 만들기

태터데스크 메시지

저장하였습니다.
블로그 이미지
Lonewolf dlbo

calendar

  1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31      

Notice

2010.08.14 23:27 Solving process

뭐, 그냥
말로만 풀고있다고 하는 것보다야 직접 보여주는게 낫겠다 싶어서 -_-a



보다시피 3번째 케이스에서 제대로 된 답이 안나오고 있음//


경로 탐색 방식상
3번째 케이스처럼 양방향 길이 존재하는 경우에 대한 처리가 아직 잘 안되고있음 :(

'Solving process' 카테고리의 다른 글

UVa 341 진행상황  (0) 2010.08.14
[PKU 1989. The Cow Lineup] 문제해석  (2) 2009.12.25
PKU [2234]. Matches Game. [WA]  (10) 2009.06.03
이걸 어떻게 구현해야 할 지  (1) 2009.01.22
[PKU 1904. King's Quest] 문제해석  (12) 2009.01.21
PKU [1089]. Intervals. [TLE].  (2) 2009.01.19
posted by Milkskin
2009.12.25 02:52 Solving process

N(10만 이하의 자연수)마리의 소가 K(1만 이하의 자연수)가지의 품종을 가지고 있다

그 N마리 소들의 품종을 수열로 나열해놓자

그러면 이 소수열(cow수열)에서 부분수열(연속하지 않아도 됨)을 찾을 수 있다

이 때, 1~K의 수들로 이루어진 임의의 수열 중 소수열의 부분수열이 아닌 것들이 있을 것이다

그러한 수열들 중 길이가 제일 짧은 수열의 길이를 출력하시오

―가 이 문제의 내용입니다 =_=



문제의 입출력 예시를 보면

[입력: 편의상 수열을 가로로 나열했습니다]
14 5
1 5 3 2 5 1 3 4 4 2 5 1 2 3
[출력]
3

입니다


힌트에도 버젓이 나와있습니다만,
영어를 잘 모르는 탓에 처음 문제가 올라왔을 땐 제대로 읽지도 않았는데요 -_-; 오늘(24일)은 유독 눈에 들어오더라구요

위 수열에서 단항(원문과 비교하자면 single digit)으로 이루어진 수열은 [1], [2], [3], [4], [5]가 모두 존재합니다

그리고 이항(two digit)으로 이루어진 25개의 수열 [1,1], [1,2], [1,3], [1,4], [1,5], [2,1], …, [5,4], [5,5]들도 모두 위의 소수열에서 찾아낼 수 있습니다

그러면 출력값이 3인 만큼,
삼항으로 이루어진 수열 중에서는 소수열의 부분수열이 아닌 것들도 있겠구나 하시겠지요

힌트 끝부분을 보시면 [2,2,4]는 찾을 수 없다고 쓰여있습니다


----------------

간단한 예시를 하나 들어봅시다
7 3
1 2 3 2 1 3 2

이 경우에도 출력값은 3이 나옵니다, 가장 간단하게 생각해서 [1,1,1]을 찾을 수 없기 때문인데요


개인적으로는 이것을 matrix에 대응시켜서 풀었습니다

단항 수열의 경우 1×3 matrix를 이용하였고,
(소수열 안에 [1], [2], [3]이 존재할 경우 각각의 위치에 true 대입)


이항 수열의 경우 3×3 matrix, 삼항 수열의 경우 3×3×3 matrix(?)를 이용하였습니다


3항 수열의 경우 [1,1,1], [2,1,1], [3,1,1], [3,3,1], [3,3,3]을 찾을 수 없다


이 방법의 경우 최대 [N/K]+1 차원까지 계산해야하기 때문에
시각적으로 형상화할 수 있는 것은 3항 수열(3차원, 큐브형태)까지입니다
(붉은색 대괄호는 가우스기호(고등학교과정)입니다)

최대 [N/K]+1 차원이라는 말은
다시 말하자면 출력값의 최대값이 [N/K]+1 정도 된다는 말과 같습니다 (거의 정확합니다)


-------------

이렇게 풀었는데도 TLE가 나온 이유를 살펴보자면

N과 K가 적당히 크고, 품종의 분포가 고를 경우 가장 시간이 오래 걸립니다
입출력 예시의 경우가 그 한 예라고 볼 수 있습니다

N = 14, K = 5 이므로 최대 차수는 [14/5]+1 = 3 이고, 이것은 곧
최대 5^1 + 5^2 + 5^3 = 155 번의 탐색을 하고 나서야 답이 나오게 됩니다


그럼 이제, N과 K가 적당히 크고 품종의 분포가 고를 경우를 가정해봅시다
N = 30000, K = 50, 각 품종당 600마리씩 존재

이 경우 최소 50^1 + 50^2 + 50^3 + … + 50^600 + 1 = ??? 번의 탐색을 하고 나서야 답이 나오게 되므로 당연히 TLE입니다


아.. 이래서 TLE였구나 -_-;;

'Solving process' 카테고리의 다른 글

UVa 341 진행상황  (0) 2010.08.14
[PKU 1989. The Cow Lineup] 문제해석  (2) 2009.12.25
PKU [2234]. Matches Game. [WA]  (10) 2009.06.03
이걸 어떻게 구현해야 할 지  (1) 2009.01.22
[PKU 1904. King's Quest] 문제해석  (12) 2009.01.21
PKU [1089]. Intervals. [TLE].  (2) 2009.01.19
posted by Milkskin
2009.06.03 22:12 Solving process


WA 입니다.

님 게임(Nim Game) 의 일종인 것 같습니다만, 이 문제는 가져올 수 있는 갯수의 제한이
최대 쌓여진 뭉치의 갯수더군요.

그래서 간단하게 '뭉치의 갯수가 짝수이면 첫번째 플레이어는 이길 수 없는 거고, 홀수라면 이기겠다.'
... 라고 생각했습니다만, WA 입니다.



...

Why???????

'Solving process' 카테고리의 다른 글

UVa 341 진행상황  (0) 2010.08.14
[PKU 1989. The Cow Lineup] 문제해석  (2) 2009.12.25
PKU [2234]. Matches Game. [WA]  (10) 2009.06.03
이걸 어떻게 구현해야 할 지  (1) 2009.01.22
[PKU 1904. King's Quest] 문제해석  (12) 2009.01.21
PKU [1089]. Intervals. [TLE].  (2) 2009.01.19
posted by 비회원
2009.01.22 17:47 Solving process
세 번째 케이스

6
3 1 2 3
3 2 4 6
2 3 4
1 5
2 3 6
4 1 2 4 5
//1 2 3 5 6 4



3 1 2 3
3 2 4 6
2 3 4
1 5
2 3 6
3 1 2 4

이 방법이 맞지요?

'Solving process' 카테고리의 다른 글

[PKU 1989. The Cow Lineup] 문제해석  (2) 2009.12.25
PKU [2234]. Matches Game. [WA]  (10) 2009.06.03
이걸 어떻게 구현해야 할 지  (1) 2009.01.22
[PKU 1904. King's Quest] 문제해석  (12) 2009.01.21
PKU [1089]. Intervals. [TLE].  (2) 2009.01.19
Rush : Dlbo군의 Matrix Solution  (8) 2008.12.28
posted by 지환태
2009.01.21 03:53 Solving process

안녕하십니까 Mr. K입니다
다들 이번 문제에 대해 혼란스러워하는 것 같아서 일단 제가 해석한 대로 전개해보겠습니다

친구와 약간의 음주를 하고 와서 쓰는 것이라 약간 말이 안되어보이는 것이 있을지도 모르겠습니다만 그냥 쓰겠습니다


문제의 입력 예시를 보면
4
2 1 2
2 1 2
2 2 3
2 3 4
1 2 3 4
라고 되어있는데,
여기서 마지막줄의 "1 2 3 4", 즉 '마법사가 만들었던 원래의 결과물'은 무시하기로 합니다
(왜 우리가 output으로 나와야 하는 한가지 경우의 수를 input으로 넣어야 하는지에 대한 의문도 잠시 접어두기로 하고)


그리고나서
2 1 2
2 1 2
2 2 3
2 3 4
를 보면,
첫번째 왕자는 2명의 소녀를 좋아하고, 그 소녀의 번호는 각각 12입니다
두번째 왕자는 2명의 소녀를 좋아하고, 그 소녀의 번호는 각각 1과 2입니다
세번째 왕자는 2명의 소녀를 좋아하고, 그 소녀의 번호는 각각 2와 3입니다
네번째 왕자는 2명의 소녀를 좋아하고, 그 소녀의 번호는 각각 3과 4입니다

이것을 표로 그리면 아래와 같은데요


문제가 요구하는 것이 무엇인고 하니,

왕자(B)와 소녀(G)가 겹치지 않도록 일대일로 짝을 지어주는 모든 경우를 세고,
어느 왕자도 결혼하지 않은 상태를 가정하고 각 왕자가 다른 왕자의 결혼을 방해하지 않도록 선택할 수 있는 소녀를 모두 나열하는 것입니다

말이 좀 어려운데,
문제에 나온 예시를 먼저 보도록 하죠
위의 표를 참고해도 좋습니다

우선, 1번 왕자와 1번 소녀를 결혼시킵니다
그러면 2번 왕자는 1번 왕자와 같은 소녀를 고르면 안되므로 2번 소녀와 결혼시킵니다
그러면 3번 왕자는 1,2번 왕자와 같은 소녀를 고르면 안되므로 3번 소녀와 결혼시킵니다
마찬가지로 4번 왕자는 1~3번 왕자와 같은 소녀를 고르면 안되므로 4번 소녀와 결혼시킵니다

그러면 (1, 1) - (2, 2) - (3, 3) - (4, 4) 와 같은 한가지 경우가 만들어집니다

그런데 1번 왕자는 2번 소녀도 좋아하므로 위에서 했던 작업은 다 잊어버리고,
1번 왕자와 2번 소녀를 결혼시킵니다
2번 왕자는 1번 왕자와 같은 소녀를 고르면 안되므로 1번 소녀와 결혼시킵니다
그러면 3번 왕자는 1, 2번 왕자와 같은 소녀를 고르면 안되므로 3번 소녀와 결혼시킵니다
그리고 4번 왕자는 1~3번 왕자와 같은 소녀를 고르면 안되므로 4번 소녀와 결혼시킵니다

그러면 (1, 2) - (2, 1) - (3, 3) - (4, 4) 와 같은 한가지 경우가 만들어집니다

이 결과를 정리해보면,
어느 왕자도 결혼하지 않은 상태를 가정했을 때,
1번 왕자는 1번 소녀나 2번 소녀를 선택할 수 있습니다
2번 왕자도 1번 소녀나 2번 소녀를 선택할 수 있습니다
3번 왕자는 3번 소녀만을 선택할 수 있습니다
4번 왕자는 4번 소녀만을 선택할 수 있습니다

그래서 출력 예시에
2 1 2
2 1 2
1 3
1 4
가 나오는 것이 아닐까 생각해봅니다



이 문제를 풀면서 혼자 만들어본 케이스가 2개 더 있습니다
두번째 케이스입니다


이번에도 역시
1번 왕자를 1번 소녀와 결혼시킵니다
이 때, 2번 왕자는 2번 소녀와 3번 소녀 모두와 결혼할 수 있는데, 3번 소녀와 결혼시키게 되면 3번 왕자가 결혼할 수 없게 됩니다
그러므로 2번 왕자는 2번 소녀와 결혼시킵니다
그러면 3번 왕자는 3번 소녀와 결혼하게 됩니다

그리고나서 보면 4번 왕자는 3~5번 소녀를,
5번 왕자는 4, 5번 소녀를 좋아하고 있으므로 (4, 4) - (5, 5) 나 (4, 5) - (5, 4) 로 결혼시킬 수 있습니다
따라서 이 경우엔
(1, 1) - (2, 2) - (3, 3) - (4, 4) - (5, 5) 또는 (1, 1) - (2, 2) - (3, 3) - (4, 5) - (5, 4) 의 두가지 경우가 가능합니다

다음,
1번 왕자를 2번 소녀와 결혼시킵니다
그러면 2번 왕자는 3번 소녀와 결혼하게 됩니다
그러면 3번 왕자는 1번 소녀와 결혼하게 됩니다
4번 왕자와 5번 왕자는 위의 경우와 같은 꼴이므로 이 경우에는
(1, 2) - (2, 3) - (3, 1) - (4, 4) - (5, 5) 또는 (1, 2) - (2, 3) - (3, 1) - (4, 5) - (5, 4) 의 두가지 경우가 가능해집니다

따라서 이번 케이스에서는 총 네가지 경우가 가능한데,
역시 어느 왕자도 결혼하지 않은 상태를 가정하면
1번 왕자는 1번 소녀나 2번 소녀를 선택할 수 있습니다
2번 왕자는 2번 소녀나 3번 소녀를 선택할 수 있습니다
3번 왕자는 1번 소녀나 3번 소녀를 선택할 수 있습니다
4번 왕자는 4번 소녀나 5번 소녀를 선택할 수 있습니다
5번 왕자도 4번 소녀나 5번 소녀를 선택할 수 있습니다

따라서 이 케이스의 출력 예시는
2 1 2
2 2 3
2 1 3
2 4 5
2 4 5
가 아닐까 예상해봅니다



세번째 케이스입니다


이 케이스는 총 여섯가지 경우가 가능한데,
말로 풀어쓰면 길어지므로 직접 종이에 끄적여보세요 :)

(1, 1) - (2, 2) - (3, 3) - (4, 5) - (5, 6) - (6, 4)
(1, 1) - (2, 4) - (3, 3) - (4, 5) - (5, 6) - (6, 2)
(1, 1) - (2, 6) - (3, 4) - (4, 5) - (5, 3) - (6, 2)
(1, 2) - (2, 4) - (3, 3) - (4, 5) - (5, 6) - (6, 1)
(1, 2) - (2, 6) - (3, 4) - (4, 5) - (5, 3) - (6, 1)
(1, 3) - (2, 2) - (3, 4) - (4, 5) - (5, 6) - (6, 1)

그렇다면 이 케이스의 출력 예시는
3 1 2 3
3 2 4 6
2 3 4
1 5
2 3 6
3 1 2 4
가 되는 것이 아닐까 생각합니다


-만,

환타님의 WA 소스는 이 세번째 케이스의 답이 제 생각과 다릅니다 =_=

※ 처음에도 언급했지만, 이 풀이는 'sparking의 번역본'을 보고 나름대로 의미를 생각해서 풀었기 때문에 실제 답과 같다는 보장은 없습니다 :(
posted by Milkskin
2009.01.19 16:56 Solving process


In PKU judge system.
사용자 삽입 이미지


허 -_- 간만에 시도해 봤는데... 감이 안돌아왔는지. 해답을 못 찾겠군요 -_-;;
꽤나 자신있게 풀었는데 말이죠. 쩝.

일단 closed_interval 이라는 구조체를 선언하고, 이 구조체를 배열에 저장합니다.
그리고 나서 각 closed interval 의 initial point, final point 를 기록합니다.
이 다음엔 Bubble Sort 로 각 구조체 배열을 정렬하죠.

그 뒤, 우선 제일 첫번째 index 의 initial point, final point 를 각각 case_min, case_max 변수에 저장하고, 각 구간값을 비교해
나갑니다.

next index 의 final 값이 case_max 값보다 크다면 이는 구간의 확장이라 보면 될 것이므로, case_max 값에
next index 의 final 값을 대입하고 다음 루프로 넘어갑니다.

만약 next index 의 initial 값이 case_max 값보다 크다면 interval 이 분할된 것이므로, 현 탐색위치의 initial point, final point를
출력하고, next index 의 탐색을 시작합니다.
탐색시, initial point 와 final point 의 초기화는 당연히 해야 겠죠.

그래서 루프를 나올 때는, 가장 마지막의 initial, final point 역시 출력해 줘야겠죠. -_-...

알고리즘상 문제는 없다고 보여집니다만, TLE 로군요. 다른 방법을 찾아야 하나...





*덧)
차라리 closed interval 을 대수적인 면에서 보기 보단 집합으로 취급하는것도 한 방법일 수 있겠네요.
각 closed interval 의 합집합을 구하면 될 것 같긴 합니다만.

생각 좀 더 해봐야겠네요 -_-;
posted by 비회원
2008.12.28 16:01 Solving process

네, 논란이 많았죠, Matrix


류엔트군은 술마시고 코딩해서 기억이 안난다고 하질 않나

Dlbo군은 류엔트군의 풀이와 99% 같은 코드를 올리고는
미리 풀긴 했는데 정리를 못한 상태에서 류엔트군의 AC가 올라오니까 그걸 보고 자기 풀이의 군더더기를 뺐다고 하질 않나
(사실 물증이 없어서 아직도 1%정도 의심은 가지만, 여기선 그걸 추궁하는게 아니니까 그냥 믿고 넘어갑니다)


그것 때문에 제가 뭔가 납득이 갈 만한 풀이를 올려달라고 했고,
얼마 전에 Dlbo군이 솔루션을 올려주었지요

솔루션을 읽고나서 알고리즘을 직접 적용해보니 아주 정확히 답이 떨어집니다

알고리즘의 목적( M번째 작은 값을 K라 가정하고, K보다 작은 값을 가지는 행렬상의 원소의 개수를 counting하는 것 )도 꽤나 깔끔하고, 합리적이지요

결론부터 먼저 말하자면,
저 코드로 아주 정확히 답을 찾아낼 수 있으니까
Dlbo군의 솔루션이 이해가 되는 분들은 과감히 '뒤로가기'를 눌러주셔도 됩니다



----------------------------------------

이제 Dlbo군의 솔루션이 뭔소린고 하는 분들만 이 아래를 보시면 됩니다

문제가 되는 부분은 Dlbo군의 설명부분인데..


일단,
솔루션에서의 x와 코드상의 x가 다른 의미를 가지고 있는 상태에서 표기가 중복되므로 의미의 모호함을 가질 수 있습니다
솔루션의 본문을 잘 읽으면 그것에 대해 언급을 했지만, 처음 솔루션을 보는 사람들에게는 난감할 수 있지요

어차피 AC받은거 또 제출할 일은 없으니 코드의 일부를 솔루션에 맞춰서 수정했어도 좋았을거라는 생각은 들지만.. 뭐 그건 상관없습니다


하나 더,
행에 관한 변수 i를 x로 치환해놓고,
j에 대해 언급할 때 '열'이 아닌 '줄'이라고 표현을 했는데, 이것 역시 처음 솔루션을 보는 사람들에게 매우 난감할 수 있습니다


그리고 자기 코드에 대해 잘 설명하다가 중간중간 류엔트의 코드와의 차이점을 언급하는데,
이건 읽는 사람의 몰입도에 방해를 줄 수 있으니 참고하세요 -_-;


또,
외부 while문이 min < max인 동안 돌도록 설계된 것이 류엔트군의 실수라고 했는데,
그러는 너는 왜 while문이 min < max인 동안 돌도록 해놨나여 ㅇㅇ?


그리고
cal_1( 이하 α; 알파라고 하겠습니다 )과 cal_2( 이하 β; 베타라고 하겠습니다 )가 실수값이 나오는 것에 대해 좀 걱정을 해놨던데
K가 무슨 값을 갖든지 알파와 베타가 정수값이 안나오는 열이 존재합니다

알고리즘을 돌리면서 확인해보니 알파와 베타는 실수값이 나와도 상관없습니다 -_-;

알고리즘을 몇번 돌려본 것을 바탕으로 추측해보건대, 알파는 항상 음수가 나옵니다
베타는 음수가 나올 때도 있고 양수가 나올 때도 있는데,
베타가 음수일 때는 고려하지 않으니 패스하고, 베타가 양수가 되면 알파·베타 모두 integer형에 쑤셔넣듯이 truncate하면 됩니다


그리고 예전에 Dlbo군이 코드에 쓰인 j는 사실 j가 아니고 i다 라는 말을 했었는데
솔루션을 읽어보니 그건 그냥 j가 맞습니다, 패스


아 마지막으로,
Dlbo군은 변수 det가 음수가 될 때의 경우는 전혀 생각하지 않은 듯 한데 -_-
우리의 자비로운 sqrt함수는 input으로 음수가 들어오니 output으로 0을 반환해주더군요

하지만 det에 대한 처리는 류엔트군의 코드가 맞으니 참고하세요 -_-;



----------------------------------------

이제 태클은 대충 됐고,

제가 예전에 Solving Process에 올렸던 1/5000 사이즈의 문제에 대해서 이 알고리즘을 적용해보겠습니다


i행 j열의 원소의 값을 나타내는 식 a_ij는 i² + 100000i + j² - 100000j + ij 인데,

행렬의 최대 사이즈가 될 수 있는 50000에 대해 다루기가 힘들기 때문에,
크기를 1/5000로 줄여서 최대 사이즈를 10으로 고정합니다

이때 a_ij를 보면
작은 수로 취급될 법한 i, j에 비해 큰 수 100000이 있는데,
최대 사이즈 50000을 10으로 줄였으니 위의 100000은 20으로 줄여보도록 합시다

그러면 우리는 a_ij = i² + 20i + j² - 20j + ij 를 얻을 수 있고,
N을 10( 최대 사이즈 )으로 고정하면 다음과 같은 행렬을 얻을 수 있습니다

위에서 붉은색으로 강조된 부분은 각 행에서 최소값을 가지는 원소를 표시해놓은 것입니다만,
파일을 재활용한 것이므로 이 풀이에서는 별로 필요 없습니다


이렇게 5만과 10만에 대해 각각 1/5000을 적용한 위의 행렬은
기존 문제( PKU 3685 )에서 제시하는 최대 5만×5만짜리 행렬이 갖는 성질을 그대로 가집니다

이제 M을 적당히 하나 잡아서, M번째 작은 값을 솔루션의 알고리즘을 통해 위의 행렬에서 찾아보도록 합시다



( 엑셀 2007에서 작성한 문서입니다 )


사용자가 수동으로 바꿔줘야하는 값은 max, min, M 세가지 뿐이니

max의 초기값은 400으로, min의 초기값은 -400으로, M은 1 이상 100 이하로 적당히 잡고

소스의 아랫부분에 있는 if( sum < M ) … else … 부분의 statement에 대해서만 수동으로 바꿔주면 됩니다

그러다보면 언젠가 max와 min이 같아지는 때가 나오는데,

그 때가 되면 더이상 while문을 돌지 않으므로 그게 답이 됩니다

- End -
posted by Milkskin
2008.10.08 21:29 Solving process
http://ko.wikipedia.org/wiki/%EB%B0%80%EB%9F%AC-%EB%9D%BC%EB%B9%88_%EC%86%8C%EC%88%98%ED%8C%90%EB%B3%84%EB%B2%95

밀러-라빈 소수판정법에 관한 위키페디아의 링크입니다.

참 난감...한 소수판정법이긴 합니다.

"이건 일단 합성수다!"라고 판정은 할 수 있지만,

"이거 소수인거 같긴 한데..."라니 원 ㄱ-;;

우리가 풀었던 factovisor에서도 순수하게 그냥 소수로 쌩 때리면 풀기 힘든만큼,

테스트케이스에서 약간의 여유를 부려 밀러-라빈 소수판정법으로 풀 수 있게 해둔것 같습니다.

리턴군, 환타님, 저 세명의 코드에 대한 테스트케이스들의 결과로 보컨데 예상되는 형태의 테스트케이스들은

모두 밀러-라빈 소수판정법에 의해 걸러질 수 있는 형태입니다. -_-;
posted by Lonewolf dlbo
2008.09.19 18:43 Solving process

Reuent님의 소스로 행X행의 행렬에서 열(A,B,C...AX)번째 원소를 정리해봤습니다.

규칙이 보이시나요?
 
전 안보여요 ㅜㅜㅜㅜㅜㅜㅜ
posted by 지환태
2008.09.19 14:09 Solving process
우리가 문제에서 생각해야 하는 행렬의 최대 차수는 무려 5만차입니다
(여기서 말하는 차수는 행렬의 size를 의미합니다)

그리고 행렬 내의 i번째 행, j번째 열의 원소인 a_ij의 값은 i^2 + 100000*i + j^2 - 100000*j + i*j 이지요
(이하 a_ij는 (i, j)로 표기하겠습니다)

약간 고쳐서 간단히 만들면 (i+j)^2 - i*j + 100000*(i-j)가 됩니다


그런데 여태까지 ↘이 방향으로 오른쪽 위에서부터 왼쪽 아래까지 읽어내려오는 방식은
(즉, n차 행렬에 대해 (1, n), (1, n-1), (2, n), (1, n-2), (2, n-1), (3, n), (1, n-3), …, 이 순서로 읽어내려오는 )

행렬의 차원이 커지면 저 순서로 읽을 수 없게 되고 말아버립니다


그런데 최대 차수가 5만이니 차수를 하나하나 증가시키면서 검사하는 방법은 거의 불가능에 가깝다고 봅니다

그래서, 1/5000로 줄여서 최대 차수가 10차인 문제에 대해 생각해보도록 하겠습니다
단, 1/5000로 줄일 때
(i, j)의 값을 나타내는 식의 일부에 해당하는 '10만'에도 적용시켜서 (i, j) = (i+j)^2 - i*j + 20*(i-j)로 생각하도록 합니다

이렇게 계산해서 나타낸 10차 행렬은 다음과 같습니다



원소가 100개밖에 되지 않으니 다루기 훨씬 쉬워지긴 했지만

'원래 문제에서 발생하는 현상이 그대로' 위의 그림에도 존재합니다

이 행렬의 경우
'3차까지는' ↘이 방향으로 읽어내려오는 방식이 유효하지만 4차부터는 그렇지 않죠

게다가 차수가 더 커지면 각각의 행 안에서의 최소값이 오른쪽 끝에 있지 않습니다

붉은색으로 표시해둔 값이 각각 i번째 행 안에서의 최소값이 되는데, 이 최소값의 좌우로는 값이 커집니다



만약 이 행렬에 대해서 m번째로 작은 값을 '규칙적으로' 찾아낼 수 있다면

그것을 확장해서 원래 문제에 적용할 수 있지 않나 생각합니다만- 어떻게 생각하시는지?
posted by Milkskin
2008.09.19 02:04 Solving process
입력에 50000 1이랑 50000 2 넣어보세요.

기존 방식처럼 오른쪽 위에서부터 대각선 오른쪽 아래로 내려가는걸 반복하는 방식으로 풀었다면

두 입력에 대한 값이 같습니다.

ㅡ.,ㅡ...

아래는 i를 1부터 5까지, j는 49996부터 5만까지 연산한 결과값입니다.

-2499849987  -2499849993  -2499849997  (-2499849999  -2499849999)
-2499699988  -2499699993  -2499699996  -2499699997  -2499699996
-2499549987  -2499549991  -2499549993  -2499549993  -2499549991
-2499399984  -2499399987  -2499399988  -2499399987  -2499399984
-2499249979  -2499249981  -2499249981  -2499249979  -2499249975

괄호친부분 보세요.

같죠?-_-;

영 뭔가 이상하다 싶어서 구글링을 통해 AC받은 사람들의 평을 들었는데...

문제가 변태스럽다고, 수준이 심각하다고 하는 의견들을 입수했습니다.

학교서 수업도 안듣고 저거 계산하고 있었는데...

최초에 저 두부분 계산하려다가 그냥 말았거든요.

"설마 같겠냐"

-_-....;;

역시 설마가 사람잡는군요. 저걸 10만짜리 다음으로 시도할라 했었는데(10만짜리도 그냥 포기)

역시 정답률 18%는 그냥 18%가 아니군요.

저랑 같이 이시간에 수고한 Mr.K군에게 감사의 말 전합니다 -_-!

Reuent군은 정답률 최소 30%는 넘는걸로 앞으로 번역하도록 합시다 -_-;;



P.S.

이번 토요일 2시~ 5시에 algospot.com에서 ICPC 2008 Korea National 대비 모의고사가 있습니다.
참가할 분 있으면 지금 후딱 신청하시구요...
다들 메신져 쓰신다면 어느 메신저인지 달아주세요. 아이디는 일단 달지 마시구요. 비공개로 때리면 서로
못볼지도 모르니;;; 제가 한분 한분 찾아다 추가하겠습니다.
posted by Lonewolf dlbo
2008.09.18 20:20 Solving process

아직 AC 받은건 아닌듸요...

너무 피로해서 지금 죽을꺼 같아서 솔루션 만들어놓고도 코드로 못옮기고 있는데...

이거 확인해 보셨나요?

식이 i^2 + 100000i + j^2 - 100000j + ij 잖습니까...

i만 1 증가시켜 비교해 보면...

i^2 + 100000i + j^2 - 100000j +ij와 i^2 + 100000i + j^2 - 100000j +ij + 2i + j + 100001이 되어서

i 증가시 2i + j + 100001만큼 증가함을 알 수 있지요.

j만 증가시켜도 그렇겠지요?

(1,1)의 값이 3이니 굳이 저 연산 안하고 증감에 따른 차이만큼만 더해도 나와요.

-_-;
posted by Lonewolf dlbo
2008.09.17 16:30 Solving process

그냥 배열에 i*(i+100000)+j*(j-100000)+i*j 넣고 찾으면 되는건가요?

posted by 지환태
TAG 행렬
2008.09.14 16:16 Solving process

안친하던 재귀함수랑 좀 친해져보려고 재귀로 짜보긴 하는데요.........
어떤 처리를 더 해줘야 중간에서 안끝날까요?

하아...........


재귀랑은 안친해질 팔자인가
posted by 지환태
2008.09.04 10:56 Solving process
22 (5(4(11(7()())(2()()))()) (8(13()())(4()(1()()))))
20 (5(4(11(7()())(2()()))()) (8(13()())(4()(1()()))))
10 (3
     (2 (4 () () )
        (8 () () ) )
     (1 (6 () () )
        (4 () () ) ) )
5 ()

0 ()
-1 (-1()())
77 (77(1()())())
-77 (-77()())

-7 (1 (-6 (2 (1 ()()) (-4 ()(1 (1 ()())(-1 ()())
   ) ) )
      () ) () )

0 ()

3 (3 (4 (5 ()()) (8 (-3 (-7 ()())())(-4 ()(-8 ()()))))
(6 (6 (-5 ()())(-6 ()(-9 ()())))(7 ()())))

0 (1()
        (-2 () (1()())))

1 (1 () (0 ()()) )

0 (0 ()())

8(8(2(1()())())())
8(8(3(7()())())())
4(4(2(4()())())())
5(5(4()(1(7(3()())(4()()))(4(3()())())))())
21(7()(5()(5()(4(1(7()())())()))))
47(7(9()(1(4()(7()(5(9(3(4(10()())())())(5(9(5(6(3(1(9()(2(3()(9(1(3(7()())(9()()))(9(5()(2()()))()))(7()())))(5(2()(6()(2()())))())))())(7()(2()(3()()))))(9()(10(4()(3()(4(3()(5()()))())))())))(3()()))())()))(6(10()())()))))()))())
24(9()(6()(1(2(9(8(7()())(1(1(7()())())(8()())))())(6(5(9()())())()))())))
15(8()(3(7(4(4()(9(6(3(3()())(9(3(3(8()())(7()()))())()))(3()()))()))())())(3(1(8(5(4(2()(4()(3(1()(10()(9()())))())))())(2()()))())())())))
18(4(9()())(1()(4()(9(3(9()(7()(8(6()())(5()(5()())))))(8(4()(1()()))()))()))))
38

(5
  (6
    (4
      ()()
    )
    (3
      ()()
    )
  )
  (7
    (2
      (1
        ()()
      )
      (10
         ()
         (9
           (5
             ()()
           )
           (2
             ()()
           )
         )
      )
    )
    ()
  )
)
77 (77(1()())())
77 (77(1()())())
77 (77  (1 () ())  (0 () ()) )
77 (77 () ())
3
(1
  (1 (1 ()()) ())
  (2 ()       ())
)

3
(1
  (1 (2 ()()) ())
  (2 ()       ())
)


yes
no
yes
no
no
yes
no
yes
yes
no
yes
yes
yes
yes
no
no
no
no
no
no
no
no
no
yes
no
no
yes
yes
yes
yes


입력/출력 샘플입니다. -_-;
posted by Lonewolf dlbo
2008.09.04 01:24 Solving process


Mr.K의 솔루션입니다.

위 부분에서 첫번째 문제...

문제에는 "EOF까지 입력받아라~"라고 되어있습니다.

근데 이 처리가 없지요 -_-a;;

이 처리는 생각보다 단순합니다.



위와 같습니다.

scanf는 EOF를 만나면 데이터를 변수에 넣지 않고, EOF를 리턴합지요.

이 외의 경우 scanf는 읽어들이는데 성공한 변수의 갯수를 리턴합니다.

while문의 조건에 scanf가 EOF를 만나느냐 아니느냐를 가지고 처리하게 해 버리고

내부 처리 루틴을 이 안에 쑤셔넣음으로써 해결되지요.

UVa나 PKU에서 EOF를 만날때까지 입력받을때 항상 쓰이는 방법입니다.

일반적으로 UVa나 PKU는 입력이 남았는데도 프로그램이 종료될 경우

TLE(Time Limit Exceed)나 WA(Wrong Answer)중 자기 마음대로 나오는 경향이 있습니다.

UVa의 경우는 WA만 나오더군요.

-_-;

이후 45~ 53줄.

gets를 이용해 입력을 받고 있습니다.

이 경우 문제점이.....

자. 아래 입력 예시를 보세요.

3 (3()
())
4 (2(2()())
())

.....

첫 문장만 처리해야 하는데...

4 (2(2()()) 까지 gets가 먹어버립니다.

-_-;

로직상 문제 없지 않냐구요?

.....

문제 있어요 -_-;;

gets는 버퍼에 글을 쓴 후, 버퍼 내용을 지우지 않고 변수에 데이터를 넣고 끝냅니다.

고로.... 입력 버퍼와 변수에 저장할 버퍼 사이에서 gets 한번 더 호출시

'\0'의 위치가 엉킨다거나, 하는 문제가 발생합니다.

-_-;

한두번의 입력은 버텨내겠지만, 이후에는 RE(Runtime Error)나 WA(Wrong Answer)를

유도할 수 있습니다.

이 떄문에 제가 getchar로 하나하나 받아다 처리했다지요 -_-;;

제 경우는 scanf의 특성을 활용했습니다.

EOF를 만날 경우 EOF나 -1을 리턴하는것 외에도,

scanf("%d", &a);시 입력받은 부분이 숫자로 시작하지 않는다면 scanf는 1개중 1개를 읽는데 실패했으니

1 - 1 = 0, 즉, 0을 리턴합니다.

이리하여 제 경우는 처음 비교대상은 scanf로 받고, 이후 getchar로 (를 받을떄까지 달린 후, 바로 scanf

를 이용해 빈 노드인지 아닌지를 판별하고 넘어가는 방식을 썼습니다.

빈 노드가 아니라면 scanf가 1을 리턴함으로써 참이 될 테고, 이 경우 내부 노드를 추가 확인하는 작업,

빈 노드라면 scanf가 0을 리턴함으로써 거짓이 되니, 다시 한번 (를 찾아 getchar의 여행을 떠나는거지요.

-_-;;

이후 곽군 코드의 문제점.

스택에다가 아예 우르르 쌓아버린후 연산하는데...

TL 걸리기 딱 좋답니다.

WA 풀린다면 아마 TL이 또 한번 가로막을꺼에요.

-_-!;;;;

용호군은 현재 솔루션이 있으나, 다시 생각해 풀어 올린다 합니다.

용호군의 솔루션도 저와 비슷한데.... 전북대 ALPS의 솔루션과 매우 흡사합니다.

용호군이나 저나 getchar를 이용해 한글자씩 받으며 입력받음과 동시에 연산을 했습니다.

이리하여 만약 yes가 된다면, 이후에는 종료될때까지 입력만 받도록 처리되었지요.

특히 Mr.K의 솔루션에서는 구조체를 이용해 처리를 했는데,

구조체의 배열 크기를 300으로 잡았답지요.

gets를 썼다는 부분과 문자열로 처리했다는 부분, 노드 갯수를 300이라는 적은 숫자로 잡은 부분에서

큰 문제가 발생합니다.

문자열로 처리함으로써 만약 한 줄에 256자가 넘게 입력되거나, 한 입력문이 256자가 넘으면

바로 RE입죠.

-_-;

동시에, 노드 갯수(Mr.K는 카드)가 300개를 넘는 경우에도 RE가 발생합니다.

물론 저런 극악의 경우는 드물겠지만 말입니다. -_-;

이 부분에 대한 처리를 하고 나면 코드가 상당히 짧아짐과 동시에 안정성을 가질겁니다.
posted by Lonewolf dlbo
prev 1 next