明日の今日: 12月 2010

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のときにも使ったビットを使った方法で解いてます。この問題は解き方いくつかありそう。

2010年12月14日火曜日

TopCoder練習 SRM424 DIV2

250問題文

public class MagicSpell {
 public String fixTheSpell(String spell) {
  String magic = new String();
  for(int i = 0; i < spell.length(); i++) {
   if(spell.charAt(i) == 'A' || spell.charAt(i) == 'Z') {
    magic += spell.charAt(i);
   }
  }
  String magicSpell = new String();
  int count = 0;
  for(int i = 0; i < spell.length(); i++) {
   if(spell.charAt(i) == 'A' || spell.charAt(i) == 'Z') {
    magicSpell += magic.charAt(magic.length()-1-count);
    count++;
   } else {
    magicSpell += spell.charAt(i);
   }
  }
  return magicSpell;
 }
}

問題文が読めれば解ける。コードは汚い。

500

import java.util.ArrayList;

public class ProductOfDigits {
 public int smallestNumber(int N) {
  if(N < 10) return 1;
  
  ArrayList<Integer> list = new ArrayList<Integer>();
  for(int i = 9; i > 1; i--) {
   if(N % i == 0) {
    list.add(i);
   }
  }
  if(list.size() < 1) return -1;
  
  int index = 0;
  int a = 0;
  while(N > 1) {
   if(N % list.get(index) == 0) {
    a++;
    N /= list.get(index);
   } else {
    if(index < list.size() -1) {
     index++;
    } else {
     return -1;
    }
   }
  }
  return a;
 }
}

問題文の意味よく分からなくて1文字もかけなかった。

2010年12月13日月曜日

TopCoder練習 SRM 423 DIV2

250問題文

public class TheSimpleGame {
 public int count(int n, int[] x, int[] y) {
  int a = (n+1)/2;
  int b = 0;
  for(int i = 0; i < x.length; i++) {
   b += (x[i] <= a) ? x[i] - 1 : n - x[i];
   b += (y[i] <= a) ? y[i] - 1 : n - y[i];
  }
  return b;
 }
}

簡単。

600

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class TheTower {
 public int[] count(int[] x, int[] y) {
  int[] a = new int[x.length];
  a[0] = 0;
  if(x.length == 1) {
   return a;
  }
  ArrayList<Integer> xList = new ArrayList<Integer>();
  ArrayList<Integer> yList = new ArrayList<Integer>();
  for(int i = 0; i < x.length; i++) {
   boolean flag1 = false;
   boolean flag2 = false;
   for(int j = 0; j < xList.size(); j++) {
    if(x[i] == xList.get(j)) {
     flag1 = true;
     break;
    }
   }
   if(!flag1) {
    xList.add(x[i]);
   }
   for(int j = 0; j < yList.size(); j++) {
    if(y[i] == yList.get(j)) {
     flag2 = true;
     break;
    }
   }
   if(!flag2) {
    yList.add(y[i]);
   }
  }
  for(int i = 1; i < x.length; i++) {
   ArrayList<Integer> list = new ArrayList<Integer>();
   for(int j = 0; j < xList.size(); j++) {
    for(int k = 0; k < yList.size(); k++) {
     list.add(checkCell(xList.get(j), yList.get(k), i+1, x, y));
    }
   }
   Collections.sort(list);
   a[i] = list.get(0);
  }
  return a;
 }
 
 private int checkCell(int x, int y, int n, int[] arrayX, int[] arrayY) {
  int[] array = new int[arrayX.length];
  for(int i = 0; i < array.length; i++) {
   array[i] = (int)Math.abs((double)(x - arrayX[i])) + (int)Math.abs((double)(y - arrayY[i]));
  }
  Arrays.sort(array);
  int move = 0;
  for(int i = 0; i < n; i++) {
   move += array[i];
  }
  return move;
 }
}

間違えたので後で修正した解答。
問題文は読めても結構難しい問題だと思う。これが600か。
おそらく、移動先のx,yはそれぞれのメジアン（中央値）になる。（ただしチェッカーが偶数のときは中央2つの平均ではなく、その2つのどちらかになる
そう考えると、x座標のリストと、y座標のリストの組み合わせ分だけ考慮すればいいので、その中で一番移動数が少ないものを選ぶ。

TopCoder SRM490 DIV2

2回目。落ち込む。チャレンジやってみたくてやったけど失敗した。
250　○
500　未提出
1000　未提出
Rate 955 -> 789

TopCoder SRM489 DIV2

初めてのTopCoder本番ってわけだったんですが、結果は何とも言えないものにｗ
250　チャレンジ
500　未提出
1000　未提出

1問も解けなく、点数はもちろん0なわけですが、レートは955というそれなりに高いという結果に。いきなり緑。
どうやら250の正解率が低かったみたい。