Hatena::Grouptopcoder

反省会。

 | 

2012-08-17 Friday

SRM546 Division I 00:33

Level One - KleofasTail (250)

  • 偶数なら半分、奇数なら1引く」という操作で無限数列を考える
  • 初項がA~Bの場合に、Kを途中の項に含むものの数を求める
  • 何か聞いたことあるけど気のせいかも
  • とりあえずいくつか手計算
  • 二進で考えればいい
  • 末尾0ならshift、末尾1なら0にする
  • Kを通る数は、二進で上の方の桁がKに一致する
  • 下の方の桁が0, 1, 2,… で数えて合計すれば早い
  • 最初に桁が増えない奇数と、0付近は別扱い
  • 50分程度

Level Two - FavouriteDigits (500)

  • N以上で、ある2つの数字を指定個数以上含む最小の数を求める
  • 0の扱いが厄介そう
  • 下から順に書き換えてみる
  • 間に合わず

Challenge

  • 早々に撃ち落される
  • 0付近の扱いが間違ってることに気づく
  • Level Twoで打ってみるが失敗

結果

  • -25.00
  • 1506 → 1222
  • 一気にDiv2が見えてきた

http://community.topcoder.com/stat?c=coder_room_stats&rd=14738&rm=313402&cr=23072275

その後

  • Level One は「任意の数は0,1を通る」と思って間違い。
  if (K==0) return B-A+1; // 初項0は1を通らない
  • Level Two は方針そのままに書いてみるも分岐が煩雑すぎて読めなくなってきた
public class FavouriteDigits {
 public long findNext(long N, int digit1, int count1, int digit2, int count2) {
  long n=N;
  long[] tp = new long[17];
  tp[0] = 1L;
  for (int tpI=1; tpI<tp.length; tpI++) tp[tpI]=tp[tpI-1]*10;
  
  int d1,c1,d2,c2;
  if (digit1 == 0 || (digit1 > digit2 && digit2 != 0)) {
   d1=digit1; c1=count1;
   d2=digit2; c2=count2;
  } else {
   d1=digit2; c1=count2;
   d2=digit1; c2=count1;
  }
  
  int tpI=0;
  while (count(n, d1) < c1) {
   int x = (int)((n % tp[tpI+1]) / tp[tpI]);
   n += (d1-x) * tp[tpI];
   if (n<N) {
    n += tp[tpI+1] - (d1*tp[tpI]);
    continue;
   }
   tpI++;
  }
  int mk = tpI;
  
  while (count(n, d2) < c2) {
   int x = (int)((n % tp[tpI+1]) / tp[tpI]);
   boolean next=true;
   if (x != d1) {
    n += (d2-x) * tp[tpI];
    if (n<N) {
     n += tp[tpI+1] - (d2*tp[tpI]);
     next = false;
    }
    if (count(n, d1) < c1) {
     n -= tp[tpI+1] - (d2*tp[tpI]);
     tpI = mk;
     while (count(n, d1) < c1) {
      int y = (int)((n % tp[tpI+1]) / tp[tpI]);
      n += (d1-y) * tp[tpI];
      if (n<N) {
       n += tp[tpI+1] - (d1*tp[tpI]);
       continue;
      }
      tpI++;
     }
     mk = tpI;
     next = true;
    }
   }
   if (next)tpI++;
  }
  
  return n;
 }
 
 private int count(long n, int digit) {
  int c=0;
  long l=n;
  while (l>0) {
   if (l%10==digit) c++;
   l=l/10;
  }
  return c;
 }
}
  • 戦略が間違ってるのでまた考える

反省

  • 次は頑張ると思ってたらPCご臨終
  • 1ヶ月足掻いたがだめだったので新PC購入
  • 環境も整ったので次は頑張る

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/sankondenai/20120817
 |