안녕하세요~ zizavino입니다 >_<
Introduction to Andromeda라는 필명으로 참가했었구요, 막판에 페널티로 간신히 Girls' Generation을 이겼습니당 >_< 유키형 죄송해요오
자 각설 에디토리얼 시작
A. Magic Sticks Again
음 이문젠 사실 그다지 어렵지 않습니다. 가장 조금 막대를 남기려면 가장 많이 막대를 붙여야 겠죠. 최대한 많이 붙이면 되는겁니다. 먼저 알고리즘을 설명하자면,,,
일단 i번째 막대가 [a_i, b_i]라고 합시다. 그럼 a_i에 대한 비내림차순으로 정렬하구요,
i번째 막대를 고려할 때에는, 1~i-1번째 막대중에서 이미 다른 막대 앞에 붙여진거 외의 것 중에서 b_j<=a_i인 j번째 막대가 존재하는지 살핍니다. 만일 존재한다면 붙이고, 존재 안하면 걍 놔둡니다.
정렬한 후에는 뭘 붙이든 뒤에 애들은 별 관심이 없기 때문에, 걍 붙일 수 있으면 붙이는 알고리즘이 최적의 결과를 냅니당
B. Number Sequence Again
음
일단 a0를 요상한 방법으로 찾습니다.. 저는 a/b-2부터 for문 돌려가면서 찾았네요-_-;
그리고부터는
while true {
swap a, b
if a equals b -> append 1 and break
if b divides a -> append b/a - 1, 1 and break
append a / b
}
하믄 됩니다. 그냥 정의에 따라 귀납적으로 푼다고 보면 될지 싶습니다. a0만 예외처리로 보고..
C. Qiushi Bookstore Again
걍 -1 무시하고 good인 애들은 가중치 0인 것으로 보고 Min Spanning Tree 구하면 됩니다 =_=;
D. Special Judge Again
악 문제읽기 짜증 ㅠ
얘 답이 무조건 n choose 2여야 하구요, 모든 조합이 다 나오는지 brute-force하게 구하면 됩니다
n choose 2가 답인 이유는, 답이 n choose 2임과 노드가 n개인 완전그래프의 오일러싸이클이 존재하는지 여부는 동치이기 때문입니다.(n이 홀수이므로 각 노드당 인접에지는 짝수개이고, 따라서 오일러싸이클 존재)
E. Checker Game
다이나믹 문제입니다.
S(i, j)를 (i, j)의 값이라고 보구요
D(i, j) = (i, j)에 도달했을 때 그때까지의 최대값이라고 합시다.
if i = 1; D(i, j) = S(i, j)
else; D(i, j) = S(i, j) + max(D(i - 1, j - 1), D(i - 1, j), D(i - 1, j + 1))
단 범위 벗어난건 걍 무시합니다.
으로 풀립니다. 이제 max(for j, D(n, j))가 답이 되겠네요.
그리고 제 코드 올립니다 >_< zizavino_20071004.zip 에요~
zizavino
안녕하세요~ zizavino입니다 >_<
Introduction to Andromeda라는 필명으로 참가했었구요, 막판에 페널티로 간신히 Girls' Generation을 이겼습니당 >_< 유키형 죄송해요오
자 각설 에디토리얼 시작
A. Magic Sticks Again
음 이문젠 사실 그다지 어렵지 않습니다. 가장 조금 막대를 남기려면 가장 많이 막대를 붙여야 겠죠. 최대한 많이 붙이면 되는겁니다. 먼저 알고리즘을 설명하자면,,,
일단 i번째 막대가 [a_i, b_i]라고 합시다. 그럼 a_i에 대한 비내림차순으로 정렬하구요,
i번째 막대를 고려할 때에는, 1~i-1번째 막대중에서 이미 다른 막대 앞에 붙여진거 외의 것 중에서 b_j<=a_i인 j번째 막대가 존재하는지 살핍니다. 만일 존재한다면 붙이고, 존재 안하면 걍 놔둡니다.
정렬한 후에는 뭘 붙이든 뒤에 애들은 별 관심이 없기 때문에, 걍 붙일 수 있으면 붙이는 알고리즘이 최적의 결과를 냅니당
B. Number Sequence Again
음
일단 a0를 요상한 방법으로 찾습니다.. 저는 a/b-2부터 for문 돌려가면서 찾았네요-_-;
그리고부터는
while true {
swap a, b
if a equals b -> append 1 and break
if b divides a -> append b/a - 1, 1 and break
append a / b
}
하믄 됩니다. 그냥 정의에 따라 귀납적으로 푼다고 보면 될지 싶습니다. a0만 예외처리로 보고..
C. Qiushi Bookstore Again
걍 -1 무시하고 good인 애들은 가중치 0인 것으로 보고 Min Spanning Tree 구하면 됩니다 =_=;
D. Special Judge Again
악 문제읽기 짜증 ㅠ
얘 답이 무조건 n choose 2여야 하구요, 모든 조합이 다 나오는지 brute-force하게 구하면 됩니다
n choose 2가 답인 이유는, 답이 n choose 2임과 노드가 n개인 완전그래프의 오일러싸이클이 존재하는지 여부는 동치이기 때문입니다.(n이 홀수이므로 각 노드당 인접에지는 짝수개이고, 따라서 오일러싸이클 존재)
E. Checker Game
다이나믹 문제입니다.
S(i, j)를 (i, j)의 값이라고 보구요
D(i, j) = (i, j)에 도달했을 때 그때까지의 최대값이라고 합시다.
if i = 1; D(i, j) = S(i, j)
else; D(i, j) = S(i, j) + max(D(i - 1, j - 1), D(i - 1, j), D(i - 1, j + 1))
단 범위 벗어난건 걍 무시합니다.
으로 풀립니다. 이제 max(for j, D(n, j))가 답이 되겠네요.
그리고 제 코드 올립니다 >_< zizavino_20071004.zip 에요~
16년 전