2012/03/06

Topcoder SRM 535(Div.2) 参戦記


狐と鰻の仲の良さがわかる回です。

250-Problem:連立方程式の問題です。対称式なので、足したり引いたりすれば答えがでます。3つの未知数に対して4つの式がありますから、そこだけ注意しました。久しぶりなので、カンを取り戻しつつ丁寧に回答して、208.97pts.

500-Problem: m*n=GCD(m,n)*LCM(m,n)の関係を使います。これと、ユークリッドの互除法、Lの約数の全探索で書けばOKでした。しかし、Lの約数のうち、Gの倍数であるもののリストを取得して確認していったほうが手早いかもしれません。284.88pts.

問題はこちら(英語).
得点は493.85, 順位は81/1412. Ratingは1125->1200. ついに青くなりました。次からはDiv.1ですので、少し心配です。

[Easy(C++),Accepted]


#include<cstdio>
#include<iostream>
#include<vector>


using namespace std;


class FoxAndIntegers{
public:
vector <int> get(int AminusB, int BminusC, int AplusB, int BplusC){
vector<int> ret(3);
vector<int> empty(0);
if((AplusB + AminusB)%2!=0) return empty;
if((BplusC - BminusC)%2!=0) return empty;
if((AplusB - AminusB)%2!=0) return empty;
if((AplusB - AminusB)!=(BplusC + BminusC)) return empty; 
ret[0]=(AplusB + AminusB)/2;
ret[1]=(AplusB - AminusB)/2;
ret[2]=(BplusC - BminusC)/2;
return ret;
}
};


[Medium(C++),Accepted]


#include<iostream>
#include<cmath>


using namespace std;


class FoxAndGCDLCM{
public:
long long get(long long G, long long L){
long long sum=-1,tmp;
for(long long i=1;i*i<=L;i++){
if(L%i!=0) continue;
tmp=L/i*G+i;
if(euclid(i,tmp-i)==G && (sum>tmp || sum==-1)) sum=tmp;
long long k=L/i;
tmp=L/k*G+k;
if(euclid(k,tmp-k)==G && (sum>tmp || sum==-1) ) sum=tmp;
}
return sum;
}

long long euclid(long long a,long long b){
if(b==0) return a;
return euclid(b,a%b);
}
};

3 件のコメント:

  1. 青、おめでとうございます。
    自分は、500点の問題で時間制限に引っかかってしまってダメでした。何が省けて、何が省けないかを早く判断できるようにしたいです。

    次はDiv1ですか。羨ましいです(笑)
    小さなミスに気をつけて、がんばってください。
    僕も次の大会で、せめて緑になれるようがんばります。

    返信削除
  2. >tanutarouさん
    ありがとうございます。と言っても、このコメントを書いているちょっと前のSRM536でまたDiv.2に戻ってしまいましたが(^^;

    私も何度かサボって、灰に落ちたことがありましたが、
    この記事:http://d.hatena.ne.jp/asi1024/20110831/1314777077
    および
    この記事:http://d.hatena.ne.jp/asi1024/20110901/1314868701
    を参考に緑になりました。

    Div.2に戻った最大の理由はC++に不慣れなことなので、C++をもっとしっかり練習することにします。

    返信削除
  3. ありがとうございます。
    参考にさせていただきます<(_ _)>

    Div1のハードルの高さが分かります。
    いつになったら、自分は辿り着けるのか。。。(ノω・、) ウゥ・・・

    返信削除