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-08-09

SRM 446 Div1

| 03:22

2か月ぶりのSRM. アサインされたのがRoom 4でACRushを筆頭にRedCoderが5人いる部屋に割り当てられる。

250

ルービックキューブとは何の関係のない問題。結局ロボットが歩く空間がドラクエのマップみたいにつながっていると思ってシミュレーションすればよい。

500

問題を把握するのに手間取る。timeout < 10^9だから行列のべき乗に直してlog(10^9)で計算する解法であることは分かったけど、作成する行列の形をちゃんと確定できなかった。

チャレンジ

一人250で"RED"とかではなくなぜか"R"とかを返している人を見つけてチャレンジ。

CodeProcessor使っているみたいだったのに不思議。

250はそんなにはまりどころはないと思ったけど、手動で遷移表を書いて間違えてたりチャレンジのしようはあったようだ。

Rating : 1897->1973

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-12

SRM 440 Div1

| 22:32

前回は平日の昼に行われたため出れなかったので、一か月ぶりの参加。

250

斜面の上からボールを転がすことを考える。ゴールにたどり着くまでの時間が与えられるので重力加速度gを求めよという問題。

gに関して2分探索する。

他の人の回答で y / sqrt(x^2 + y^2)みたいのがあったから何かと思ったらsinの定義だった。普通にMath.sin(Math.atan2(y,x))とか書いていた。

500

グラフ上のランダムウォークでの目的地までの到着期待値を求めよという問題。計算量を勘違いしていて普通に連立方程式を解いてTLEした。問題をよく読むとグラフが木なのでdfsするだけでよかった。

2009-04-20

SRM 438 Div1

| 02:57

ネットがつながらなかったり、実家に帰省したりしていたので久々に自宅でやるSRM

Easyと1 challengeのみだけど全体的に難しかったので順位はそこそこよかった。

Easyの方針としてはluckySetの付近のn個の数について全て調べるという方法をとるとあまりバグなくかける。最初はnに比例するオーダーでもできるかなと思ったけどちゃんと書ける気がしなかったので少々愚直に書いた。

あと、[1..n]の範囲で数aを含む区間の数はすべての区間の数からaより左のすべての区間の数と右のすべての区間の数を引いてやればよい。

import java.util.*;

public class UnluckyIntervals {
  class S implements Comparable<S>{
    int num;
    long val;
    S(int n , long v){
      num = n;
      val = v;
    }
    public int compareTo(S o) {
      if(val == o.val){
        return num - o.num;
      }
      return val > o.val ? 1 : -1;
    }
  }
  long calc(int val , int right){
    long r = right - 1;
    long tot = r * (r - 1) / 2;
    long ln = (val - 1);
    long rn = (r - val);
    tot -= ln * (ln - 1) / 2;
    tot -= rn * (rn - 1) / 2;
    return tot;
  }
  long calc(int ls[] , int val){
    int n = ls.length;
    if(ls[n - 1] < val)return Long.MAX_VALUE;
    if(ls[0] > val)return calc(val , ls[0]);
    for(int i = 0 ; i < n ; i++)
      if(ls[i] == val)return 0;
      else if(ls[i] < val && val < ls[i + 1])
        return calc(val - ls[i], ls[i + 1] - ls[i]);    
    return -1;
  }
  public int[] getLuckiest(int[] luckySet, int n) {
    Arrays.sort(luckySet);
    HashSet<Integer> cand = new HashSet<Integer>();
    for(int i = 1 ; i <= n ; i++)
      cand.add(i);
    for(int l : luckySet){
      cand.add(l);
      for(int i = 1 ; i <= n ;i++){
        if(l - i >= 1)cand.add(l - i);
        cand.add(l + i);
      }
    }
    PriorityQueue<S> q = new PriorityQueue<S>();
    for(int c : cand){
      q.add(new S(c , calc(luckySet , c)));
    }
    int[] res = new int[n];
    for(int i = 0 ; i < n ; i++){
      S s = q.poll();
      res[i] = s.num;
    }
    return res;
  }
}