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  ;
  }
}

WilliamTagWilliamTag2019/02/02 11:26cialis without a rx
kjop cialis online
<a href=https://kellyannehulme.com>buy Cialis 20 mg</a>
acheter cialis france
cialis tyskland
https://greatwinesgrandhouses.com
low cost cialis 2.5mg daily
expired cialis side effects
<a href=https://kellyannehulme.com>20 mg cialis buy</a>
generic cialis in germany drug store
buy cialis us pharmacy
https://kellyannehulme.com

ArnoldNizArnoldNiz2019/02/05 20:50order female cialis side effects
buying cialis in malaysia
<a href="http://xcialisxx.com">Cheap Cialis buy</a>
cialis back pain
cialis review recreational
<a href="http://xcialisxx.com">Buy Cheap Cialis</a>
cialis strips online
about cialis
<a href="http://xcialisxx.com">Buy Cheap Cialis Online</a>

LukeEvifeLukeEvife2019/06/05 08:55Luke Bryan is my favourite US contry singer. His strong voice takes me away from all issues of this planet so I can enjoy my life and listen songs created by his voice. Now the singer is going on a tour in 2019. The concerts scheduled for this year, up to the 12th of October. Ticket prices are moderate and available for all men and women with different income. If you love contry music, then you must visit at least one of his concert. All tour dates are available at the <a href=https://lukebryantourdates.com>Luke Bryan concert list</a>. Visit the website and make yourself familiar with all Luke Bryan concerts in 2020!

LukeEvifeLukeEvife2019/06/08 00:46Luke Bryan is my favourite country singer. His strong voice takes me away from all problems of this planet so I start enjoy my life and listen songs created by his. Now the singer is going on a tour in 2020. The concerts scheduled for the whole 2019, up to the mid-October. Tickets are available for everyone. If you are a country music lover as me, then you must visit at least one Luke's concert. All tour dates are available at the <a href=https://lukebryantourdates.com>Luke Bryan concert list</a>. Open the website and make yourself familiar with all powerful Luke Bryan concerts in 2020!

FlorluptFlorlupt2019/06/10 12:34Florida Georgia Line is my favourite country music band. Headliners Brian Kelley and Tyler Hubbard are those people that could make anyone sing along with them. That's why I like to visit their shows. And - that's surprisingly wonderful - in 2019 they have CAN'T SAY IT AIN'T COUNTRY TOUR which covers all the US towns and cities. For concert dates list visit <a href=https://fgltour.com>Florida Georgia Line Concert Tour</a>.

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;
  }
}