Hatena::Grouptopcoder

tsubosakaの日記

2009-12-23

SRM 456

13:02

250

将棋の銀の動きをするコマが(sx,sy)から(gx,gy)に移動するための最小移動回数を求めよという問題。盤面の大きさは2000000 * 2000000

もし、上に動くという動きを除くと斜めにみたマンハッタン距離になるので適当に上に何回動かした点からのマンハッタン距離を求めればよい。本番は上に1000000回まで動かすとか試したのですが実はy座標に2上がるのは(+1,+1)(-1,+1)の二つで代用できるので一個上に動かす場合とそうでない場合を比較すればよい。

public class SilverDistance {
  static final int INF = Integer.MAX_VALUE / 2;

  int bishopDistance(int sx, int sy, int gx, int gy) {
    int smark = (sx + sy) & 1;
    int gmark = (gx + gy) & 1;
    if (smark != gmark) {
      return INF;
    }
    int dx = sx - sy - (gx - gy);
    int dy = sx + sy - (gx + gy);
    int res = Math.abs(dx) / 2 + Math.abs(dy) / 2;
    return res;
  }

  public int minSteps(int sx, int sy, int gx, int gy) {
    int res = bishopDistance(sx, sy, gx, gy);
    res = Math.min(res, 1 + bishopDistance(sx, sy + 1, gx, gy));
    return res;
  }
}

500

K番目の値の長さに関して2分探索すればよい。本番では2分探索まで書いたけど、Cの条件をどう入れるかに混乱して間に合わなかった。あと最初大きいものから均等割するとかいろいろと考えてたせいで2分探索を思いつくのが遅かった。

import java.util.*;

public class CutSticks {
  boolean can(int[] sticks , int C , int K , double len){
    int tot = 0;
    for(int i = sticks.length - 1; i >= 0 ; --i){
      if(sticks[i] < len)continue;   
      int num = (int)(sticks[i] / len);
      if(num == 1 || C <= 0){
        tot++;
      }else{
        int p = Math.min(num , C + 1);
        tot += p;
        C -= p - 1;
      }
    }
    return K <= tot;
  }
  public double maxKth(int[] sticks, int C, int K) {
    Arrays.sort(sticks);
    int N = sticks.length;
    double low = 0.0;
    double high = sticks[N - 1];
    for(int r = 0 ; r < 1000 ; ++r){
      double mid = (low + high) / 2;
      if(can(sticks , C , K , mid)){
        low = mid;        
      }else{
        high = mid;
      }
    }
    return low;
  }
}

MargarettaMargaretta2011/08/29 22:12A bit surprised it seems to simple and yet usufel.

dkbmdrgpbevdkbmdrgpbev2011/08/30 23:29TNd0oa , [url=http://knsiidebacpw.com/]knsiidebacpw[/url], [link=http://mvozzloyqudx.com/]mvozzloyqudx[/link], http://fittodenelil.com/

sfixfbvumqesfixfbvumqe2011/08/31 17:153znoyq <a href="http://aidcupltouma.com/">aidcupltouma</a>

adzvgmadzvgm2011/09/03 23:27nQNetT , [url=http://bjnfmsqmjnay.com/]bjnfmsqmjnay[/url], [link=http://lkljpnktlbxe.com/]lkljpnktlbxe[/link], http://fnkganihhsrp.com/