2012 ACM USA southeast 문제 질문입니다.

  • canuyes
    canuyes

    안녕하세요.
    혼자 알고리즘을 공부중인 학생입니다.
    문제를 풀던 도중 막히는 부분이 생겨 질문 올립니다.
    질문에 답해주시는 것이
    감사한 일이고, 어려운 일임을 알기에 최대한 상세하게 올려봅니다.

    제가 풀고있는 문제는
    2012 ACM USA southeast D번 문제 : Do it Wrong, Get it Right
    입니다.
    (원 문제의 링크 대신 제가 이용하는 온라인 저지의 링크를 올립니다.)

    저는 이문제를 다음과 같이 풀이 하였습니다.

    주어진 식

    a/m-b/n=(a-b)/(m-n)

    의 결과가

    (an-bm)/mn

    이 나와야 하므로
    위의 두식의 결과가 같다고 식을 세워

    a=(-bm^2+2nbm)/n^2

    을 얻습니다.

    이는, 주어진 b,n에 대하여
    우리가 구하고자하는 자연수 순서쌍 a,m이 포물선위에 있음을
    의미 합니다.

    따라서, m을 1부터 2m까지 증가시켜가면서,
    자연수가 되는 a값을 찾아 답안에 저장합니다.
    (추후 정렬이 필요없도록 set을 사용했습니다.)

    제가 계산하기로는
    제 알고리즘의 반복문 수행횟수가 2000000회로서, 1억 미만입니다.
    1초 이내에 답안이 나오기에 충분해 보입니다.
    하지만 제출을하면 1초 시간 초과가 뜨고 맙니다.

    아래는 제 코드 입니다.

    #include<iostream>
#include<set>
using namespace std;

class FRACTION{
      public:
             long long son,mother;
};

template<typename T>
struct user_defined{
       bool operator()(const T& A,const T& B){
            bool ret;
            if(A.son*B.mother<B.son*A.mother){ret=true;}
            else if(A.son*B.mother>B.son*A.mother){ret=false;}
            else{
                 if(A.son<B.son){ret=true;}
                 else{ret=false;}
            }
            return ret;
       }
};

long long B,N,nT,fT,cT,i;
set<FRACTION,user_defined<FRACTION> > answer;
FRACTION fraction;

int main(void){
    while(1){
             cin>>B>>N;
             if(B==0&&N==0){break;}
             answer.clear();
             nT=N*N;
             fT=2*N;
             for(i=1;i<=fT;i++){
                                if(i==N){continue;}
                                else{
                                     cT=-1*i*i*B+2*N*B*i;
                                     if(cT%nT==0){
                                                  fraction.mother=i;
                                                  fraction.son=cT/nT;
                                                  answer.insert(fraction);
                                     }
                                }
             }
             set<FRACTION,user_defined<FRACTION> >::iterator itr;
             for(itr=answer.begin();itr!=answer.end();itr++){cout<<itr->son<<'/'<<itr->mother<<' ';}                      
             cout<<endl;
    }
    return 0;
}


    2000000회 이하의 반복문 수행이 1초를 넘어가는 이유가 뭘까요?
    그리고 만약 극복할 수 있는 방법이 있다면 어떤것들이 있을까요?

    답변 기다립니다.

    p.s. 아래는 ACM judging blog의 링크입니다.
    네번째 타래에
    2012 Division I Problem Set
    라는 이름으로 D번 섹션에 있습니다.
    인풋샘플과 아웃풋 샘플, 예제 답변코드가 업로드되어 있습니다.
    (솔루션 코드조차도 TLE가 뜨더군요...)
    저징블로그


    10년 전
5개의 댓글이 있습니다.
  • wookayin
    wookayin
    • set 보단 vector에 넣고 정렬하는게 보통 더 실행속도는 빠릅니다. (이 문제는 실제로 정렬하고자 하는 원소의 개수는 적기 때문에 거의 영향은 없습니다)
    • BOJ 에서는 오피셜 솔루션보다 시간 제한이 빡빡한것 같긴 합니다..만 줄일 여지는 있습니다.
      • 일단 답을 잘 관찰해보면 모든 분모는 다 어떤 정수(=K)의 배수임을 알 수 있습니다.
      • 따라서 1씩 증가시키는게 아니라 K씩 증가시키면서 탐색하면 후보군을 많이 줄일 수 있습니다.
      • 이 K를 구하는 방법은 한번 고민해 보세요..^^
    • 그 외 1~2n 범위를 탐색하지 않고 수식을 풀어서 할 수 있는 방법도 있을것 같은데 (아마 100ms 이하로 나오신 분들은 그렇게 푸셨겠죠?) 이건 아래 분이..

    10년 전 link
  • Baekjoon
    Baekjoon

    저 문제 오피셜 솔루션이 두 갠데 밑에 소스를 제출해보니 32MS로 TLE가 뜨지 않고 통과합니다.


    10년 전 link
  • wookayin
    wookayin

    위에껀 TLE인가여 @_@


    10년 전 link
  • Baekjoon
    Baekjoon

    위에껀 TLE네요


    10년 전 link
  • canuyes
    canuyes

    감사합니다! 답변덕에 잘 해결했습니다.
    휴학하고 혼자 공부하려니 막막하네요 ;; ㅎㅎ
    @wookayin
    조언덕에 K를 구해서 K씩 띄어가며 풀었습니다만,
    K를 미리 어떤 식으로 구해내지는 못했습니다.
    아래와 같이 몇번 시도는 해보았는데...

    a=(-bm^2+2nbm)/n^2

    에서,

    (-bm^2+2nbm)

    의 값이 n^2의 배수로 나와야 하므로,

    -bm^2+2nbm=n^2k

    (k는 음이아닌 정수)
    로 놓고, 분모 m에 대해서 풀면(근의 공식이용)

    m=(2bn±2n*root(b^2-bk))/2b

    로 나오더군요.
    그리고 이이후로는 진전이 없습니다 ㅠㅠ
    직접 for문을 돌면서 K를 찾아내기 이전에,
    계산으로서 K값을 찾는 건 어떻게 해야하나요?


    10년 전 link

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