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-06-19

SRM 442 Div 1 Medium

| 06:44

ちょっと違うけど、大体規則的に並んだタイルの左上の座標と右下の座標が与えられた時に含まれるタイルの模様を求めよという問題。

基本的に真ん中の合計と四隅の合計をO(1)で求めて、残りの端の4箇所をループでまわして合計を求めればいい。ただし縦長と横長のときに場合分けを行ったり、mod 5が0のときに開始点を変えなければならないとか非常にめんどう。

さらに個数をちゃんと求められていても1*5のタイルが何個あるかを数え上げるルーチンを間違えると死亡する。

public class BedroomFloor {
  long num(long count[]) {
    long total = 0;
    total = count[5];
    total += count[4];
    count[1] -= count[4];
    total += count[3];
    if(count[2] >= count[3]){
      count[2] -= count[3];
    }else{
      count[1] -= 2 * (count[3] - count[2]);
      count[2] = 0;
    }    
    if(count[2] > 0){
      long n = (count[2] + 1) / 2;
      count[1] -= 5 * n - 2 * count[2];
      total += n;
    }    
    if(count[1] > 0){
      total += (count[1] + 4) / 5;
    }
    return total;
  }

  public long numberOfSticks(int x1, int y1, int x2, int y2) {
    long count[] = new long[6];
    long x1g = x1 / 5;
    long y1g = y1 / 5;
    long x2g = (x2 - 1) / 5;
    long y2g = (y2 - 1) / 5;
    if (x1g == x2g && y1g == y2g) {
      plus(x1, y1, x2, y2, count);
    } else if (x1g == x2g) {
      long ys = y1 % 5 == 0 ? y1 : (y1g + 1) * 5;
      long ye = y2 % 5 == 0 ? y2 : y2g * 5;
      for (long y = ys; y < ye; y += 5) {
        plus(x1, y, x2, y + 5, count);
      }
      plus(x1, y1, x2, ys, count);
      plus(x1, ye, x2, y2, count);
    } else if (y1g == y2g) {
      long xs = x1 % 5 == 0 ? x1 : (x1g + 1) * 5;
      long xe = x2 % 5 == 0 ? x2 : x2g * 5;
      for (long x = xs; x < xe; x += 5) {
        plus(x, y1, x + 5, y2, count);
      }
      plus(x1, y1, xs, y2, count);
      plus(xe, y1, x2, y2, count);
    } else {
      long xs = x1 % 5 == 0 ? x1 + 5 : (x1g + 1) * 5;
      long xe = x2 % 5 == 0 ? x2 - 5 : x2g * 5;
      long ys = y1 % 5 == 0 ? y1 + 5 : (y1g + 1) * 5;
      long ye = y2 % 5 == 0 ? y2 - 5 : y2g * 5;
      count[5] += (ye - ys) * (xe - xs) / 5;
      for (long x = xs; x < xe; x += 5) {
        plus(x, y1, x + 5, ys, count);
        plus(x, ye, x + 5, y2, count);
      }
      for (long y = ys; y < ye; y += 5) {
        plus(x1, y, xs, y + 5, count);
        plus(xe, y, x2, y + 5, count);
      }
      plus(x1, y1, xs, ys, count);
      plus(x1, ye, xs, y2, count);
      plus(xe, y1, x2, ys, count);
      plus(xe, ye, x2, y2, count);
    }
    return num(count);
  }

  void plus(long x1, long y1, long x2, long y2, long count[]) {
    if (x1 >= x2)
      return;
    if (y1 >= y2)
      return;
    long xs = x1 / 5;
    long ys = y1 / 5;
    int xd = (int) (x2 - x1);
    int yd = (int) (y2 - y1);
    if ((xs + ys) % 2 == 0) {
      count[xd] += yd;
    } else {
      count[yd] += xd;
    }
  }
}

2009-05-13

SRM440 Div1 Medium

| 05:59

一個ルートノードを決めて、探索していったときに(あるノードの期待値) = a * (親ノードの期待値) + bと書け(ノードが葉のときはa=1.0,b=1.0、チーズのときはa=b=0.0となる)再帰的に計算するとルートノードでの期待値となる。一回の計算にノード数分に比例する時間がかかり、それをすべてのノードに対して実行するのでO(N^2)となる。

また、cafelierさんによると期待値 = 親の期待値 + 子孫の数*2 + 1となるのでこれだとチーズから始めればO(N)で計算できるけどこの式を思いつくのは難しいと思う(証明は天下り的に子供の期待値がこの形で書けているとして代入していけば帰納法で示せる。)

import java.util.*;

class Vertex{
  List<Integer> adjoint;
  Vertex(){
    adjoint = new ArrayList<Integer>();
  }
  int size(){
    return adjoint.size();
  }
  void add(int e){
    adjoint.add(e);
  }  
}

public class MazeWandering {  
  int cheeseId;
  public double expectedTime(String[] maze) {
    Vertex[] vs = createGraph(maze);
    double res = 0.0;
    for(int i = 0 ; i < vs.length ; i++){
      res += rec(vs , -1 , i)[1];
    }
    return res / vs.length;
  }
  
  double[] rec(Vertex vs[] , int parent , int cp){
    if(cp == cheeseId)
      return new double[]{0.0 , 0.0};
    Vertex v = vs[cp];
    double res[] = new double[2];
    res[0] = 0.0;
    res[1] = 1.0;    
    for(int adj : v.adjoint){
      if(adj == parent)continue;
      double a[] = rec(vs , cp , adj);
      res[0] += a[0] / v.size();
      res[1] += a[1] / v.size();
    }
    res[1] /= (1 - res[0]);
    res[0] = 1.0 / (v.size() * (1.0 - res[0]));
    return res;
  }
  
  private Vertex[] createGraph(String[] maze) {
    int W = maze[0].length();
    int H = maze.length;
    int ids[][] = new int[H][W];
    int id = 0;
    for (int i = 0; i < H; i++) {
      Arrays.fill(ids[i], -1);
      for (int j = 0; j < W; j++) {
        char c = maze[i].charAt(j);
        if(c == 'X')continue;
        if(c == '*')
          cheeseId = id;
        ids[i][j] = id++;
      }
    }
    int n = id;
    Vertex vs[] = new Vertex[n];
    int dx[] = { 1, -1, 0, 0 };
    int dy[] = { 0, 0, 1, -1 };
    for (int i = 0; i < H; i++) {
      for (int j = 0; j < W; j++) {
        char c = maze[i].charAt(j);
        if (c == 'X') 
          continue;        
        int cid = ids[i][j];
        Vertex v = new Vertex();
        for (int k = 0; k < dx.length; k++) {
          int x = j + dx[k];
          int y = i + dy[k];
          if (x < 0 || y < 0 || x >= W || y >= H)
            continue;
          if (ids[y][x] < 0)
            continue;
          v.add(ids[y][x]);
        }
        vs[cid] = v;
      }
    }
    return vs;
  }  
}

2009-04-20

SRM 439 Div1 Medium

| 20:08

言われるとなるほどと思うのだが本番ではなかなか思いつかない。

まず、$の数が1つのときは A B B B ... という周期的な列になるため容易に求まる。また$の数が2つ以上のときは変数の長さが常に2倍以上になるため、s <= 32のときのみを考えればよい。

import java.util.*;
public class EndlessStringMachine {
  int cnt(String s) {
    int cnt = 0;
    for (char c : s.toCharArray())
      if (c == '$')cnt++;
    return cnt;
  }
  char rec(String in , String p , int s , int i , List<Long> ls){
    if(s == 0)return in.charAt(i);
    long plen = ls.get(s - 1);
    for(char c : p.toCharArray())
      if(c == '$')
        if(i < plen)return rec(in, p, s - 1, i, ls);
        else i -= plen;
      else if(i-- == 0)return c;
    return '-';
  }
  public String getFragment(String in, String p, int s, int L, int R) {
    L--; R--;
    long dn = cnt(p);
    StringBuilder sb = new StringBuilder();
    if (dn == 1) {
      int plen = p.length() - 1;
      long tlen = in.length() + plen * (long)s;
      for (int i = L; i <= R; i++)
        if (i < in.length())sb.append(in.charAt(i));
        else if(i >= tlen)sb.append('-');
        else sb.append( p.charAt(1 + (i - in.length()) % plen));      
    } else {
      List<Long> ls = new ArrayList<Long>();
      ls.add((long)in.length());
      for (int i = 1; i <= s; i++) {
        long li = (ls.get(i - 1) * dn) + (p.length() - dn);
        ls.add(li);
        if (li >= R)break;
      }
      for(int index = L ; index <= R ; index++)
        sb.append(rec(in, p, ls.size() - 1 , index, ls));      
    }
    return sb.toString();
  }
}

2009-03-08

TCO 09 Round 1 Medium

| 04:05

ネットで順序統計量とか調べると公式が載っているのでそれを実装しただけです。

public class KthProbableElement {
  double fact(int n){
    double res = 1.0;
    for(int i = 1 ; i <= n ; i++)
      res *= i;
    return res;
  }
  public double probability(int M, int lowerBound, int upperBound, int N, int K) {
    double res = 0.0;
    double pi = 1.0 * (N - lowerBound + 1) / (upperBound - lowerBound + 1);
    double pii = 1.0 * (N - lowerBound ) / (upperBound - lowerBound + 1);
    for(int k = K ; k <= M ; k++){
      double cmb = fact(M) / (fact(k) * fact(M - k)); 
      double r = Math.pow(pi , k) * Math.pow(1.0 - pi ,M - k);
      r -= Math.pow(pii , k) * Math.pow(1.0 - pii ,M - k);
      res += r * cmb;
    }
    return res;
  }
}