[editorial] astein주최 20071004 모의고사 에디토리얼

  • zizavino
    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 에요~

    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    17년 전
3개의 댓글이 있습니다.
  • zizavino
    zizavino

    오랜만에 MST 짜려다보니 당황했네요
    프림을 까먹어서 크루스컬로 =_ㅠ;


    17년 전 link
  • 정상인
    정상인

    우리팀은 D번 original problem을 풀었습니다.


    17년 전 link
  • @,.@
    @,.@

    D번 짝수거나 3보다 작거나 49보다 큰 데이터 셋이 있지 않았나요?ㅋㅋ


    17년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.