Topcoder SRM501 参戦記

3月30日はTopcoderSRMとCodeforcesの両方が開催される、忙しい一日でした。日が変わる頃に始まったCodeforcesを戦った後、20時からTopcoderのSRMに参加するというバタバタです。

最低限のレベルの確保という観点では、C++よりもJAVAの方が出来がいいので、JAVAで参加することにしました。初参加で、勝手がわからないままでしたので、問題をまず全部開いてしまうという失態を(^^;;。問題を開かない方が点数が高くなるのです。

ひとまず、250の問題に解答を与えます。内容としては
「引数として与えられる整数列に対し、次の1項を付け加える。付け加えられた整数列が等差数列または等比数列になるような「次の1項」は何通りあるか返却するメソッドを作成せよ。但し、無数にある場合は-1を返せ」
というものです。
配列等が使えれば苦もなく解ける問題なので、丁寧に処理を書いてaccepted。これで約30分が経過していました。問題を全部読むなどしなければもっと早かったのかもしれません。

次いで、500の問題を読みます。初めの一読ではよく意味がわからなかったのですが、再読してみるとそれほど難しい問題ではありませんでした。簡単には
「0に対して、AをnA回足し、BをnB回かけるとする。この順序を任意にとることができるとき、その最大値を返却するメソッドを作成せよ。A,Bは負の数もありうる」
というものでした。
A>0,B>=1ならば単純にAばかり全部足してからBを書ければよいのですが、それ以外の場合は少々処理に困ります。「初めが0」というのが味噌で、余分なBをここで使うことで、値を調整することができます。具体的には
・Bが0以上1未満の時は、A>0なら最初に、A<0なら和をとってからかける。
・Bが-1以上0未満の時は、A>0なら最初に、A<0なら和をとった後1回だけかける。←ここの実装を誤って、下の場合に含めてしまっていました。
・Bが-1未満の時には、A>0なら最初に、A<0なら和をとった後奇数の最大回数かける。
という形になりました。
これをJAVAで記し、残り時間はもう少し。

だったのですが、1000の問題を解けるほどの時間はなさそうだったので、そこで終了。チャレンジフェイズも特にみつけられずでした。もっと早く読む力が必要なのかもしれません。

結果、Division2において324/1003（とはいえ，半分以上は提出すら出来ていないようでした）、スコアは149.89（提出分のMAX:388.78)でした。不慣れなのもありますが、上のミスは大きいですね。
いつもどおり、答案を載せておきます。

250:これは確実に解けました。

public class FoxProgression{
    public static int theCount(int[] seq){
int g=0,a=0,def,ratio,gnext=0,anext=0;
if(seq.length==1) return -1;
def=seq[1]-seq[0];
ratio=seq[1]/seq[0];
if(ratio*seq[0]!=seq[1]) g=1;
for(int i=2;i<seq.length;i++){
   if(g==0){
if(ratio*seq[i-1]!=seq[i]) g=1;
   }
   if(a==0){
if(def+seq[i-1]!=seq[i]) a=1;
   }
}
if(g==1 && a==1) return 0;
if(g==0) gnext=ratio*seq[seq.length-1];
if(a==0) anext=def+seq[seq.length-1];
if(g==a && gnext==anext) return 1;
return 2-g-a;
    }
}

500：上の実装ミスに気づいたのはChallenge中。システムテストで落とされました。

public class FoxPlayingGame{
    public static double theMax(int nA,int nB,int paramA,int paramB){
double scoreA,scoreB,val;
scoreA=(double)paramA/1000.0;
scoreB=(double)paramB/1000.0;
if(scoreA>=0){
   if(Math.abs(scoreB)<1) return scoreA*nA;
   if(scoreB<=-1){
if(nB%2==0) return scoreA*nA*Math.pow(scoreB,(double)nB);
else return scoreA*nA*Math.pow(scoreB,(double)(nB-1));
   }
   return scoreA*nA*Math.pow(scoreB,(double)nB);
}else{
   if(scoreB>=1) return scoreA*nA;
   if(scoreB<1 && scoreB>=0) return scoreA*nA*Math.pow(scoreB,(double)nB);
   if(scoreB<0){
if(nB%2==0) return scoreA*nA*Math.pow(scoreB,(double)(nB-1));
else return scoreA*nA*Math.pow(scoreB,(double)nB);
   }
}
return 0;
    }
}