Topcoder SRM509(Div.2) 参戦記

前に用事があったので、10分ほど遅れての開始。

まず、250を見ます。回文数は再帰関数で組むことが多いので、久しぶりにJavaで再帰関数を組みました。今考えたら文字列化したほうが早かった気がします。Javaで文字列化する方法を調べるのが面倒だったので、ゆっくりやってしまいました。やはり、JavaやC++を鍛える必要がありそうです。Submitは151.78。ちょっと遅すぎです。

その後、500に移ります。今回は少し遅目の参加だったので後回しにしたのですが、ほとんど問題なく、アルゴリズムも悩まずに立ちました。Submitして、419.42。部屋内では2番目で、かなりありがたいスピードでした。

1000は解けず。1000を解けるように、もっと精進しないといけません。

結果、120/1204で、かなり良い成績。571.2でした。

250：ちょっと遅すぎました。

public class PalindromizationDiv2{
public static int getMinimumCost(int X){
if(palind(X)==0) return 0;
int i=1;
while(true){
if(palind(X+i)==0){
  break;
  }
if(palind(X-i)==0){
break;
}
i++;
}
return i;
}

public static int palind(int n){
int keta=0,tens=1,tmp=n;
for(keta=0;tmp!=0;tmp/=10,keta++);
if(keta<=1) return 0;
if(keta==2){
if(n%10==n/10) return 0;
else return 1;
}
for(int i=0;i<keta-1;i++) tens*=10;
if(n/tens!=n%10) return 1;
tmp=n%10;
n-=tmp*tens;
n/=10;
return palindk(n,keta-2);
}

public static int palindk(int n,int keta){
int tens=1,tmp;
if(keta<=1) return 0;
if(keta==2){
if(n%10==n/10) return 0;
else return 1;
}
for(int i=0;i<keta-1;i++) tens*=10;
if(n/tens!=n%10) return 1;
tmp=n%10;
n-=tmp*tens;
n/=10;
return palindk(n,keta-2);
}
}


500：やはり、９の倍数の性質は有効利用するに限ります。

public class LuckyRemainder{
public static int getLuckyRemainder(String X){
int bin=1;
for(int i=0;i<X.length()-1;i++){
bin*=2;
bin%=9;
}
int sum=0;
for(int i=0;i<X.length();i++){
sum+=(X.charAt(i)-'0')*bin%9;
sum%=9;
}
return sum;
}
}