2010年12月25日土曜日

BottomCoder SRM403 DIV2

これからは本番はTopCoderってタイトルで、練習はBottomCoderってタイトルにします。
最近TopCoderの記事が多いのでもっとほかの記事も書きたいです。

250
public class TheLargestLuckyNumber {
 public int find(int n) {
  outer: for(int i = n; i >= 4; i--) {
   for(int j = 0; j < Integer.toString(i).length(); j++) {
    if(Integer.toString(i).charAt(j) != '7' && Integer.toString(i).charAt(j) != '4') {
     continue outer;
    }
   }
   return i;
  }
  
  return 0;
 }
}
早く解けた。2重ループだとラベル便利。

500
public class TheLuckyNumbers {
 public int count(int a, int b) {
  int count = 0;
  String sa = Integer.toString(a);
  String sb = Integer.toString(b);
  int len = sb.length();
  for(int j = 1; j <= len; j++) {
   for(int mask = 0; mask < (1 << j); mask++) {
    String str = "";
    for(int i = 0; i < j; i++) {
     if((mask & (1 << i)) > 0) {
      str += "7";
     } else {
      str += "4";
     }
    }
    if((str.length() > sa.length() || (str.length() == sa.length() && str.compareTo(sa) >= 0)) && (str.length() < sb.length() || str.compareTo(sb) <= 0)) {
     count++;
    }
   }
  }
  return count;
 }
}
250のように全探索すると、2秒以内に終わらないので計算量を減らす必要がある問題。
いろいろな解き方でアプローチしてて時間内に終わらなかった。
自力で解くことはできたけど、これぐらいの問題を解けないと緑安定はしないし、解けるようになりたい。
roseとlilyのときにも使ったビットを使った方法で解いてます。この問題は解き方いくつかありそう。

0 件のコメント:

コメントを投稿