[editorial] 2007년 서울 지역대회 인터넷 예선 C번 ACM UCPC

  • admin
    admin

    이런 문제들을 반 농담으로 'Implement-this-problem' 이라고 합니다. 아무 생각 할 필요 없이 문제에서
    준 조건대로 구현하면 되는 문제들이죠. 가끔은 곧이곧대로 푸는 것보다 더 쉬운 방법이 있기도 합니다만, 대개의 경우에는 문제에
    명시된 다양한 조건들을 꼼꼼히 살피고 빼먹지 않고 코딩하는 것이 갈 길입니다. 이 문제의 경우에는 전체 랭크리스트를 출력하는
    것이 아니라 마지막 한 팀을 출력하는 문제입니다만, 이 조건을 이용해 전체 선발된 팀을 구하지 않고 넘어가 보려다가는 더 큰
    고생을 하기 쉬우니 우직하게 문제에서 요구하는 대로 팀들을 선발해 보겠습니다.
    일단 입력으로
    주어지는 정보 중 solved 와 penalty 정보는 필요 없다는 것을 알 수 있습니다. 왜냐면 입력은 순위대로 정렬되어
    들어온다고 문제에 명시되어 있기 때문이죠. 따라서 각 팀명과 학교 이름만을 저장해 두면 됩니다. 그 후, 한 팀씩 고려해가며
    문제의 조건에 적합한가를 판단하면 됩니다. 이 과정에서 유용하게 사용되는 것이 C++ 의 map, Java 의
    TreeMap/HashMap, C# 의 Dictionary 등의 연관 자료구조(Associative Container) 입니다.
    이들을 이용해 각 학교에 몇 팀의 쿼터가 남아 있는지, 각 학교마다 선발된 팀의 수가 몇인지 등을 쉽게 저장해 둘 수 있습니다. 혹시 이와 같은 표준 라이브러리를 제대로 사용하는 법을 모르신다면 이번 기회에 꼭 익혀두시기 바랍니다! 이들을 잘 사용하는 것은 대회의 성패를 가를 수 있을 정도로 중요합니다. :)

    음 소스 코드는 이의 비교적 짧은 구현입니다. 물론 제대로 된 구조를 갖춘 것도 아니고 제대로 주석을 붙여둔 것도 아니지만,
    가능한한 빠른 시간 내에 맞는 코드를 생산해내야 하는 대회 환경 하에서는 이와 같은 구현이 최상이라고 생각합니다. 물론, 더
    좋은 구현이 있을지도 모르니 참고만 하세요~ ^^
    (이게 더 쉽겠는걸! 싶으신 분은 소스코드를 저희에게 보내주세요~)

    [spoiler="더 보기..."]#include
    #include
    #include
    #include
    using namespace std;
    int main()
    {
    int cases;
    cin >> cases;
    while(cases--)
    {
    int n; cin >> n;
    vector name(n), school(n); // 각 팀명, 학교명
    vector selected(n, false); // 각 팀이 선택되었는가 여부
    map quota; // 각 학교별 쿼터
    for(int i = 0; i < n; ++i) {
    int solved, penalty;
    cin >> name[i] >> school[i] >> solved >> penalty;
    quota[school[i]]++;
    }
    for(map::iterator it = quota.begin(); it != quota.end(); ++it) // M팀이면 (M+1)/2 가 해당 학교의 쿼터
    it->second = (it->second + 1) / 2;
    map selectedFrom; // 각 학교에서 선택된 팀의 수
    int selectedCount = 0;
    for(int i = 0; i < n; ++i) {
    int rank = i+1; // 0-based 인 i 를 1-based 인 등수로 바꾼다
    if(rank <= 10 && selectedFrom[school[i]] > 3) continue;
    if(11 <= rank && rank <= 20 && selectedFrom[school[i]] > 2) continue;
    if(21 <= rank && rank <= 30 && selectedFrom[school[i]] > 1) continue;
    if(31 <= rank && selectedFrom[school[i]] > 0) continue;
    if(quota[school[i]] == 0) continue;
    if(selectedCount == 60) continue;
    --quota[school[i]];
    ++selectedFrom[school[i]];
    ++selectedCount;
    selected[i] = true;
    }
    // 선발 팀수가 모자랄 때 채우기
    for(int i = 0; i < n; ++i)
    if(selectedCount < 60 && !selected[i]) {
    ++selectedCount;
    selected[i] = true;
    }
    for(int i = n-1; i >= 0; --i)
    if(selected[i]) {
    cout << name[i] << endl;
    break;
    }
    }
    }[/spoiler]

    • 구종만, algospot.com 운영진
      [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

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