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

KennnataKennnata2017/06/19 09:38Order Acticin With Overnight Delivery <a href=http://via100mg.com>Buy Viagra</a> Levitra In Hamburg Letrozole <a href=http://cial40mg.com/buy-cheap-cialis.php>Buy Cheap Cialis</a> Brand Name Propecia Generic Onlineerertiledysfunctionpillss <a href=http://buy-priligy-30mg.priliorder.com>Buy Priligy 30mg</a> Unisom In Singapore

buy kamagra 100mgbuy kamagra 100mg2018/04/05 19:11kamagra shop erfahrungen 2015
<a href="http://kamagrabst.com/">buy kamagra online</a>
kamagra 100mg reviews
<a href="http://kamagrabst.com/">kamagra 100 mg</a>
kamagra kopen
http://kamagrabst.com/
kamagra shop erfahrungen 2017

kamagra 100mgkamagra 100mg2018/04/08 00:23kamagra jelly 100mg
<a href="http://kamagrabst.com/">http://kamagrabst.com/</a>
kamagra usa website
<a href="http://kamagrabst.com/">kamagra soft chewable tablets 100 mg</a>
kamagra oral jelly usage
http://kamagrabst.com/
kamagra cost

DustintofDustintof2018/04/08 19:26cialis 20mg price at walmart
<a href="http://justinpro.com/#">buy cialis</a>
compare cialis prices uk
<a href="http://justinpro.com/#">generic cialis online</a>
cialis generico precio argentina
<a href="http://airvietnamairline.com/#">cialis</a>
cialis prices at walmart
<a href="http://airvietnamairline.com/#">buy cialis</a>
coupons for cialis generic

WilliamFexWilliamFex2018/04/09 12:25buy cialis canada canadian drugstore
<a href="http://justinpro.com/#">buy cialis online</a>
brand cialis meaning in hindi
<a href="http://justinpro.com/#">cialis generic</a>
cialis vs viagra reviews
<a href="http://airvietnamairline.com/#">buy generic cialis online</a>
cialis dosage 40 mg
<a href="http://airvietnamairline.com/#">buy generic cialis online</a>
buy cialis canada canadian drugstore

WilliamFexWilliamFex2018/04/09 19:06generic cialis shipped fedex
<a href="http://coastalseaplanes.com/#">generic cialis online</a>
low cost viagra cialis 5mg
<a href="http://coastalseaplanes.com/#">generic cialis online</a>
maximum daily dose of cialis
<a href="http://northcoastgetaway.com/#">buy generic cialis online</a>
low cost viagra cialis
<a href="http://northcoastgetaway.com/#">buy cialis</a>
5 mg or 20 mg cialis after prostate surgery

WilliamFexWilliamFex2018/04/10 09:45viagra generico in farmacia italiana
<a href="http://amsboatyard.com/#">buy viagra</a>
max viagra dosage recommendations
<a href="http://amsboatyard.com/#">buy viagra</a>
best time to take viagra and cialis
<a href="http://viagrapillq.com/#">viagra</a>
viagra side effects skin rash
<a href="http://viagrapillq.com/#">buy generic viagra</a>
viagra vs cialis vs levitra 2013

WilliamFexWilliamFex2018/04/10 15:55viagra professional 100 mg pills kiwi
<a href="http://amsboatyard.com/#">generic viagra online</a>
viagra dosage
<a href="http://amsboatyard.com/#">buy generic viagra online</a>
generic name for viagra
<a href="http://viagrapillq.com/#">viagra generic</a>
effects of black viagra on blood pressure
<a href="http://viagrapillq.com/#">buy generic viagra</a>
viagra coupons printable cvs

WilliamFexWilliamFex2018/04/11 08:15viagra dosage for best results
<a href="http://amsboatyard.com/#">buy viagra online</a>
viagra cialis cost comparison
<a href="http://amsboatyard.com/#">viagra generic</a>
viagra coupons 2018
<a href="http://viagrapillq.com/#">viagra generic</a>
effects of viagra on blood pressure
<a href="http://viagrapillq.com/#">viagra generic</a>
viagra dosage for dogs

WilliamFexWilliamFex2018/04/11 14:12viagra over counter us
<a href="http://blessingsofbirth.com/#">generic viagra online</a>
viagra side effects low blood pressure
<a href="http://blessingsofbirth.com/#">viagra generic</a>
viagra time take effect
<a href="http://timmonssoftware.com/#">viagra generic</a>
generic viagra soft tabs 50mg
<a href="http://timmonssoftware.com/#">viagra generic</a>
viagra generic brands australia

WilliamFexWilliamFex2018/04/12 02:29taking viagra after prostatectomy
<a href="http://amsboatyard.com/#">generic viagra</a>
female viagra reviews
<a href="http://amsboatyard.com/#">buy generic viagra</a>
viagra dosage reddit
<a href="http://viagrapillq.com/#">buy generic viagra</a>
compare viagra cialis levitra side effects
<a href="http://viagrapillq.com/#">generic viagra online</a>
youtube viagra commercial 2015 actresses

WilliamFexWilliamFex2018/04/12 07:58cialis dosage 20mg or 10mg
<a href="http://coastalseaplanes.com/#">cialis generic</a>
cialis and viagra dosage
<a href="http://coastalseaplanes.com/#">cialis generic</a>
prices for cialis at walmart
<a href="http://northcoastgetaway.com/#">buy generic cialis online</a>
vidalista professional generic cialis 20mg
<a href="http://northcoastgetaway.com/#">generic cialis online</a>
cialis commercial female actors 2016

WilliamFexWilliamFex2018/04/12 17:18buy viagra online in usa
<a href="http://amsboatyard.com/#">viagra</a>
viagra generic walmart cost
<a href="http://amsboatyard.com/#">viagra</a>
como fazer viagra caseiro masculino
<a href="http://viagrapillq.com/#">generic viagra</a>
maximum daily dose of viagra
<a href="http://viagrapillq.com/#">viagra generic</a>
brand viagra without a doctor prescription uk

WilliamFexWilliamFex2018/04/12 22:20female viagra pills 100 mg each month
<a href="http://blessingsofbirth.com/#">buy generic viagra online</a>
youtube viagra commercial 2015 football
<a href="http://blessingsofbirth.com/#">buy viagra</a>
generic viagra professional (sildenafil) 100mg
<a href="http://timmonssoftware.com/#">buy viagra online</a>
viagra soft tab
<a href="http://timmonssoftware.com/#">generic viagra online</a>
woman in viagra commercial wearing jersey

WilliamFexWilliamFex2018/04/13 08:10viagra commercial black actress 2015
<a href="http://blessingsofbirth.com/#">buy generic viagra online</a>
viagra feminino onde comprar
<a href="http://blessingsofbirth.com/#">buy generic viagra online</a>
viagra for women commercial
<a href="http://timmonssoftware.com/#">generic viagra online</a>
natural viagra food list in tamil
<a href="http://timmonssoftware.com/#">buy generic viagra</a>
levitra or viagra forum

WilliamFexWilliamFex2018/04/13 12:43price of cialis 20 mg at cvs
<a href="http://justinpro.com/#">buy cialis online</a>
compare cialis and viagra side effects
<a href="http://justinpro.com/#">cialis</a>
generico do cialis no brasil
<a href="http://airvietnamairline.com/#">buy cialis online</a>
cialis 20 mg tablet price
<a href="http://airvietnamairline.com/#">cialis</a>
cialis levitra staxyn and viagra cost comparison

WilliamFexWilliamFex2018/04/13 22:20natural viagra alternatives foods
<a href="http://amsboatyard.com/#">viagra generic</a>
dosage for generic viagra
<a href="http://amsboatyard.com/#">buy generic viagra</a>
viagra professional chewable
<a href="http://viagrapillq.com/#">buy viagra</a>
generic viagra best
<a href="http://viagrapillq.com/#">buy generic viagra online</a>
generic viagra available walgreens

WilliamFexWilliamFex2018/04/14 03:29cialis coupon for costco
<a href="http://coastalseaplanes.com/#">generic cialis</a>
cialis coupon 2016
<a href="http://coastalseaplanes.com/#">buy generic cialis online</a>
cialis doses 10 mg
<a href="http://northcoastgetaway.com/#">buy generic cialis</a>
super active cialis reviews
<a href="http://northcoastgetaway.com/#">cialis</a>
cialis commercial bathtub

WilliamFexWilliamFex2018/04/14 12:51cialis vs viagra 100mg
<a href="http://coastalseaplanes.com/#">buy generic cialis online</a>
cialis generico precio espaГ±a
<a href="http://coastalseaplanes.com/#">buy cialis online</a>
cialis 20 mg dosage
<a href="http://northcoastgetaway.com/#">buy generic cialis</a>
cialis super active tadalafil
<a href="http://northcoastgetaway.com/#">buy cialis online</a>
side effects of generic cialis

WilliamFexWilliamFex2018/04/14 17:28cialis 5mg daily price in the united states
<a href="http://justinpro.com/#">cialis generic</a>
best price viagra and cialis
<a href="http://justinpro.com/#">buy cialis</a>
when is cialis going generic 2017
<a href="http://airvietnamairline.com/#">cialis</a>
cialis extra dosage 100mg capsules
<a href="http://airvietnamairline.com/#">generic cialis online</a>
generic cialis professional 20 mg

WilliamFexWilliamFex2018/04/15 02:41buy viagra cialis online canada
<a href="http://amsboatyard.com/#">buy viagra</a>
viagra coupons free samples
<a href="http://amsboatyard.com/#">buy viagra online</a>
generic viagra best
<a href="http://viagrapillq.com/#">buy generic viagra</a>
cost per pill for generic viagra in mexico
<a href="http://viagrapillq.com/#">buy viagra</a>
desi viagra price in india

WilliamFexWilliamFex2018/04/15 07:34side effects viagra cialis levitra
<a href="http://amsboatyard.com/#">generic viagra</a>
viagra prices us pharmacy
<a href="http://amsboatyard.com/#">generic viagra</a>
best price generic viagra
<a href="http://viagrapillq.com/#">viagra</a>
generic viagra super active (sildenafil citrate)
<a href="http://viagrapillq.com/#">buy generic viagra online</a>
reviews on female viagra

WilliamFexWilliamFex2018/04/15 16:24viagra generico brasil
<a href="http://blessingsofbirth.com/#">viagra generic</a>
viagra like natural foods
<a href="http://blessingsofbirth.com/#">generic viagra online</a>
female viagra pills walmart
<a href="http://timmonssoftware.com/#">generic viagra online</a>
cialis and viagra dosage
<a href="http://timmonssoftware.com/#">generic viagra online</a>
viagra generico in italia

WilliamFexWilliamFex2018/04/15 21:25viagra feminino onde comprar em bh
<a href="http://amsboatyard.com/#">viagra</a>
female viagra pill online
<a href="http://amsboatyard.com/#">generic viagra online</a>
viagra and cialis best price
<a href="http://viagrapillq.com/#">generic viagra</a>
viagra feminina no brasil
<a href="http://viagrapillq.com/#">viagra</a>
natural viagra foods in urdu

KatDyeluPKatDyeluP2018/04/15 22:43Oral Jelly Kamagra Congestion Nasale Levothyrox No Prescription Viagra Y Antibioticos <a href=http://cheapciali.com>cialis prices</a> Buy Flagyl Over The Counter Amoxicilline Teva 250mg 5ml My Alli Canada

WilliamFexWilliamFex2018/04/16 21:57best time to take viagra for best results
<a href="http://blessingsofbirth.com/#">buy viagra</a>
viagra and cialis dosage and cost comparison between
<a href="http://blessingsofbirth.com/#">generic viagra online</a>
viagra generico preço bh
<a href="http://timmonssoftware.com/#">viagra generic</a>
new viagra commercial asian actress name
<a href="http://timmonssoftware.com/#">buy generic viagra</a>
what is generic viagra professional

WilliamFexWilliamFex2018/04/17 03:07viagra levitra cialis cost comparison
<a href="http://justinpro.com/#">buy cialis</a>
cialis generic in us
<a href="http://justinpro.com/#">buy generic cialis</a>
purchase generic cialis online
<a href="http://airvietnamairline.com/#">buy generic cialis online</a>
buy generic cialis viagra online
<a href="http://airvietnamairline.com/#">cialis</a>
cialis vs viagra vs levitra

WilliamFexWilliamFex2018/04/17 12:15prices of cialis and viagra
<a href="http://amsboatyard.com/#">buy generic viagra online</a>
viagra cialis pharmacy
<a href="http://amsboatyard.com/#">generic viagra</a>
medicamento generico viagra mexico
<a href="http://viagrapillq.com/#">buy viagra</a>
cialis price vs viagra cost
<a href="http://viagrapillq.com/#">viagra</a>
other names for generic viagra

WilliamFexWilliamFex2018/04/17 16:35pfizer brand viagra online
<a href="http://amsboatyard.com/#">buy generic viagra online</a>
viagra medical use
<a href="http://amsboatyard.com/#">buy generic viagra</a>
viagra vs cialis generic
<a href="http://viagrapillq.com/#">buy generic viagra online</a>
what s the maximum dosage for viagra
<a href="http://viagrapillq.com/#">buy generic viagra</a>
viagra prices in us

WilliamFexWilliamFex2018/04/18 02:10comprar viagra generico en espaГ±a contrareembolso
<a href="http://blessingsofbirth.com/#">buy viagra</a>
viagra for women 2017
<a href="http://blessingsofbirth.com/#">buy generic viagra</a>
viagra car commercial youtube
<a href="http://timmonssoftware.com/#">buy generic viagra</a>
viagra coupons rite aid
<a href="http://timmonssoftware.com/#">viagra generic</a>
viagra side effects on women