Hatena::Grouptopcoder

tsubosakaの日記

2009-09-11SRM 448

SRM 448 Medium

| 00:03

1からnまでのカードが順番に並んでいる。これを複雑な手順でシャッフルを繰り返すことによって最終的に一番上にあるカードを求めよという問題。

nは10^6まであるのでシミュレーションを愚直にするとn^2で間に合わない。

着目点は

  • 各手順において手札からは2枚ずつ減っていく
  • n-2枚目をシャッフルし終わったときに一番上にあるカードがk番目のカードであれば、n番目をシャッフルし終わったときに一番上にあるカードは1回のシャッフル手順を繰り返した時の状態でのk番目のカードである

よって1枚or2枚のときの状態から逆算してn枚目の状態を求めればよい。

コードは以下のようになる

public class TheCardShufflingDivOne {
  int rotate(int idx , int len , int move){
    return (idx + len - (move % len)) % len;
  }
  int shuffle_once(int n , int idx , int left , int right){
    int lnum = (n + 1) / 2;
    int rnum = n / 2;
    if(idx < rnum - 1){
      int i = rotate(idx, rnum, right);
      return i * 2 + 1;
    }else{
      idx -= rnum - 1;
      int i = rotate(idx, lnum, left);
      return i * 2;
    }
  }
  public int shuffle(int n, int left, int right) {
    boolean iseven = n % 2 == 0;
    int mdeck = iseven ? 2 : 1;
    int k = iseven ? 1 : 0;
    while(mdeck < n){
      mdeck += 2;
      k = shuffle_once(mdeck , k, left, right);
    }
    return k + 1  ;
  }
}

2009-02-25

TCO 09 Qualification Round 1 Easy

| 00:10

各数に関して自分より大きいものが何個あるかを数えるだけ。同じ場合は前にあるもののみを数える


public class SortingWithPermutation {
  public int[] getPermutation(int[] a) {
    int N = a.length;
    int[] res = new int[N];
    for(int i = 0 ; i < N ; i++){
      int cnt = 0;
      for(int j = 0 ; j < N ; j++)
        if((a[i] > a[j]) ||
           (a[i] == a[j] && i > j))
          cnt++;      
      res[i] = cnt;
    }
    return res;
  }
}

2009-01-14

SRM 173 Div1 Medium

| 19:25

すべての開始点の候補から命令列を実行してみて終点を求める.複数ある場合は条件に書いてある通りに選択する.

public class TreasureHunt {
  int[] findX(char map[][]){
    int res[] = new int[2];
    for(int i = 0 ; i < map.length ; i++){
      for(int j = 0 ; j < map[i].length ; j++){
        if(map[i][j] == 'X'){
          res[0] = j;
          res[1] = i;
        }
      }
    }
    return res;
  }
  int[] endPoint(char map[][] , String[] instructions , int sx , int sy){
    int H = map.length;
    int W = map[0].length;
    int x = sx;
    int y = sy;
    for(String instruction : instructions){
      char dir = instruction.charAt(0);
      int paces = instruction.charAt(2) - '0';
      int dx = 0 , dy = 0;
      if(dir == 'N')dy = -1;
      else if(dir == 'S')dy = 1;
      else if(dir == 'E')dx = 1;
      else dx = -1;
      for(int i = 0 ; i < paces ; i++){
        x += dx;
        y += dy;
        if(x < 0 || x >= W)return null;
        if(y < 0 || y >= H)return null;
        if(map[y][x] == '.')return null;        
      }
    }
    return new int[]{x,y};
  }
  boolean isBeach(char map[][] , int x , int y){
    if(map[y][x] == '.')return false;
    int dx[] = {0 , 0 , -1 , 1};
    int dy[] = {1 , -1 , 0 , 0};
    for(int i = 0 ; i < dx.length ; i++){
      int nx = x + dx[i];
      int ny = y + dy[i];
      if(nx < 0 || nx >= map[0].length)return true;
      if(ny < 0 || ny >= map.length)return true;
      if(map[ny][nx] == '.')return true;
    }
    return false;
  }
  public int[] findTreasure(String[] island, String[] instructions) {
    int H = island.length;
    int W = island[0].length();
    char map[][] = new char[H][W];
    for(int i = 0 ; i < H ; i++)
      map[i] = island[i].toCharArray();
    int X[] = findX(map);
    int[] res = new int[2];
    int mindist = Integer.MAX_VALUE;
    for(int y = 0 ; y < H ; y++){
      for(int x = 0 ; x < W ; x++){
        if(!isBeach(map, x, y))continue;
        int ep[] = endPoint(map, instructions, x, y);        
        if(ep == null)continue;
        int dist = (ep[0] - X[0]) * (ep[0] - X[0]) + (ep[1] - X[1]) * (ep[1] - X[1]);
        if(dist > mindist)continue;
        if(dist < mindist){
          res[0] = ep[0];
          res[1] = ep[1];          
        }else{
          if(ep[1] < res[1]){
            res[0] = ep[0];
            res[1] = ep[1];            
          }else if(ep[1] == res[1]){
            if(ep[0] < res[0]){
              res[0] = ep[0];
              res[1] = ep[1];                          
            }
          }
        }
        mindist = dist;
      }
    }
    if(mindist == Integer.MAX_VALUE)return new int[0];
    return res;
  }
}

RoberGrotlyRoberGrotly2017/05/08 23:31Amoxicilina Internet Where To Buy Levitra Deezer <a href=http://byuvaigranonile.com>viagra</a> Malegra Amoxicillin Trihydrate 250 Dosage Propecia Zwanger Worden