Hatena::Grouptopcoder

tsubosakaの日記

2011-07-26

SRM 513

21:55

久々にまともに解けた回

250

英語が読みづらかったけど各platformに対して、おける配置の数を独立にもとめて掛けてやればよい。

50 * 10000 * 50の解法でも間に合う


public class YetAnotherIncredibleMachine {
  long count(int pm , int pl , int[] balls){
    long count = 0;
    for(int left = pm - pl ; left <= pm ; ++left){
      int right = left + pl;
      boolean f = false;
      for(int b : balls){
        if(left <= b && b <= right){
          f = true;
        }
      }
      if(!f)++count;
    }
    return count;
  }
  public int countWays(int[] platformMount, int[] platformLength, int[] balls) {
    long mod = 1000000009;
    long res = 1;
    for(int i = 0 ; i < platformMount.length ; ++i){
      int pmi = platformMount[i];
      int pli = platformLength[i];
      long count = count(pmi , pli , balls);
      res = (res * count) % mod;
    }
    return (int)(res % mod);
  }
}

500

残りのカード枚数と残りのうちすでに開いたものの数をkeyにしたdp


import java.util.*;

public class PerfectMemory {
  double[][] dp;
  double rec(int resCard , int memSymbol){
    if(resCard <= memSymbol * 2){
      return resCard / 2.0;
    }
    if(dp[resCard][memSymbol] >= 0.0){
      return dp[resCard][memSymbol];
    }
    double exp = 1.0;
    int notReveal = resCard - memSymbol;
    double r1 = memSymbol * 1.0 / (double)notReveal;
    if(memSymbol > 0){
      exp += r1 * rec(resCard - 2 , memSymbol - 1);      
    }
    double r2 = 1.0 - r1;
    double rinv = 1.0 / (double)(notReveal - 1);
    exp += r2 * rinv * rec(resCard - 2 , memSymbol);
    exp += r2 * memSymbol * rinv * (rec(resCard - 2 , memSymbol) + 1);
    exp += r2 * (notReveal - 2 - memSymbol) * rinv * rec(resCard , memSymbol + 2);
    return dp[resCard][memSymbol] = exp;
  }
  
  public double getExpectation(int N, int M) {
    dp = new double[N * M + 1][N * M + 1];
    for(int i = 0 ; i < dp.length ; ++i){
      Arrays.fill(dp[i], -1.0);
    }
    return rec(N * M , 0);
  }
}

ArnieArnie2011/08/30 04:49Life is short, and this airtcle saved valuable time on this Earth.

qctsvsirsqctsvsirs2011/08/30 17:05GHubQ8 <a href="http://tqsengcrklhz.com/">tqsengcrklhz</a>

vdbjtprvdbjtpr2011/09/01 16:56mfoJMg , [url=http://tkllhtysxufe.com/]tkllhtysxufe[/url], [link=http://zgmhmyswjjri.com/]zgmhmyswjjri[/link], http://gtccgdeialbq.com/

udkacsjhenjudkacsjhenj2011/09/03 18:14cmyPv6 <a href="http://qwwgebnzylel.com/">qwwgebnzylel</a>

xbsnexjozxbsnexjoz2011/09/04 02:127lBMVO , [url=http://yvnvymkgzodf.com/]yvnvymkgzodf[/url], [link=http://jqqfaxubcgjy.com/]jqqfaxubcgjy[/link], http://qoayefvelzpp.com/

2011-05-24

pku2104

23:32

http://poj.org/problem?id=2104

昨日書いたWavelet treeを使った解法

メモリ効率考えてないのでPOJのサーバだと通んないけど、judgeデータ落としてきて手元で通ることは確認した。

package pku2104;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;

class BitVector{
  int rank[];
  public BitVector(int[] arr) {
    rank = new int[arr.length];
    rank[0] = arr[0];
    for(int i = 1 ; i < arr.length ; ++i){
      rank[i] = rank[i - 1] + arr[i];
    }
  }
  int rank(int p , int b){
    if(b == 1){
      return rank[p];
    }else{
      return p + 1 - rank[p];
    }
  }
}

class Tree{
  int hbit;
  BitVector bvec;  
  Tree left;
  Tree right;
  Tree(int h , BitVector v){
    hbit = h;
    bvec = v;
  }
}

class WTree{
  Tree root;
  Tree gen(int hbit , int[] arr){
    if(hbit == 0){
      return new Tree(hbit , null);
    }
    int lsize = 0;
    int rsize = 0;
    int bv[] = new int[arr.length];
    for(int i = 0 ; i < arr.length ; ++i){
      if((arr[i] & hbit) != 0){
        bv[i] = 1;
        ++rsize;
      }else{
        bv[i] = 0;
        ++lsize;
      }
    }
    Tree ret = new Tree(hbit , new BitVector(bv));
    bv = null;
    int[] left = new int[lsize];
    int[] right = new int[rsize];
    int li = 0;
    int ri = 0;
    for(int i = 0 ; i < arr.length ; ++i){
      if((arr[i] & hbit) != 0){
        right[ri++] = arr[i];
      }else{
        left[li++] = arr[i];
      }
    }   
    if(lsize > 0){
      ret.left = gen(hbit / 2, left);
    }
    if(rsize > 0){
      ret.right = gen(hbit / 2 , right);
    }
    return ret;
  }
  public WTree(int[] arr) {
    int max = 0;
    for(int a : arr)
      max = Math.max(max, a);
    int h = Integer.highestOneBit(max);
    root = gen(h , arr);
  }
  int rank(int p , int k){
    Tree r = root;
    int ret = 0;
    while(p >= 0 && r != null){
      if(r.hbit == 0){
        ret += p + 1 ; 
        break;
      }
      int r0 = r.bvec.rank(p, 0);      
      if((k & r.hbit) != 0){
        ret += r0;
        p = p - r0;
        r = r.right;
      }else{
        p = r0 - 1;
        r = r.left;
      }
    }
    return ret;
  }
}
public class Main {
  public static void main(String[] args) throws Exception{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    Scanner cin = new Scanner(br);
    int n = cin.nextInt();
    int m = cin.nextInt();
    int arr[] = new int[n];
    int min = Integer.MAX_VALUE;
    for(int i = 0 ; i < n ; ++i){
      arr[i] = cin.nextInt();
      min = Math.min(min, arr[i]);
    }    
    for(int i = 0 ; i < n ; ++i){
      arr[i] = arr[i] - min;
    }
    int sarr[] = arr.clone();
    Arrays.sort(sarr);
    WTree wt = new WTree(arr);
    for(int query = 0 ; query < m ; ++query){
      int i = cin.nextInt() - 1;
      int j = cin.nextInt() - 1;
      int k = cin.nextInt();
      int low = 0;
      int high = n - 1;
      while(low < high){
        int mid = low + (high - low) / 2;
        int num = wt.rank(j, sarr[mid]);
        if(i > 0){
          num -= wt.rank(i - 1, sarr[mid]);
        }
        if(num >= k){
          high = mid;
        }else{
          low = mid + 1;
        }
      }
      System.out.println(sarr[low] + min);
    }
  }
}

UTPC 2011 L

01:09

UTPCの解説とデータが上がってた(http://www.utpc.jp/2011/)ので、勉強も兼ねてWavelet Tree(もどき)を使った解法を書いてみた。手元だと最大ケースに大して4秒かかるので、ちょっとaccpetもらえるかは微妙なコードになった。

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;
struct BitVec{
  int N;
  vector<int> rank0;
  vector<int> rank0sign;
  void update(int pos , int diff , vector<int> & vec){
    if(pos > 0){
      vec[pos] = vec[pos - 1] + diff;
    }else{
      vec[pos] = diff;
    }
  }

  BitVec(vector<int> & arr , vector<int> & sign) 
    :N(arr.size()),rank0(arr.size()) , rank0sign(arr.size()) 
  {
    for(int i = 0 ; i < N ; ++i){
      int ai = arr[i];
      int si = sign[i];
      if(ai){
        update(i , 0 , rank0);
        update(i , 0 , rank0sign);
      }else{
        update(i , 1 , rank0);
        update(i , si , rank0sign);
      }
    }
  }
  //a[0..p]の中のbの数を返す
  int rank(int p , int b){
    if(b){
      return p + 1 - rank0[p];
    }else{
      return rank0[p];
    }
  }

  int rank0Sign(int p){
    return rank0sign[p];
  }
};

struct Tree{
  int hbit;
  BitVec * bv;
  struct Tree * left;
  struct Tree * right;
};

struct WTree{
  Tree * root;
  void gen(Tree * t , vector<int> & arr , vector<int> & sign){
    int hb = t->hbit;
    vector<int> bv(arr.size());
    vector<int> left, left_sign, right, right_sign;
    for(int i = 0 ; i < arr.size() ; ++i){
      if(arr[i] & hb){
        bv[i] = 1;
        right.push_back(arr[i]);
        right_sign.push_back(sign[i]);
      }else{
        bv[i] = 0;
        left.push_back(arr[i]);
        left_sign.push_back(sign[i]);
      }
    }
    t->bv = new BitVec(bv , sign);
    if(left.size() > 0 && hb){
      Tree * ltree = new Tree();
      ltree->hbit = hb / 2;
      gen(ltree , left , left_sign);
      t->left = ltree;
    }else{
      t->left = NULL;
    }
    if(right.size() > 0 && hb){
      Tree * rtree = new Tree();
      rtree->hbit = hb / 2;
      gen(rtree, right, right_sign);
      t->right = rtree;
    }else{
      t->right = NULL;
    }

  }
  WTree(vector<int> & arr , vector<int> & sign)
  {
    int m = *max_element(arr.begin() , arr.end());
    int hb = 1 << (31 - __builtin_clz(m));
    root = new Tree();
    root->hbit = hb;
    gen(root , arr , sign);
  }
  //a[0..p]のk以下のものの個数を返す
  int rank(int p , int k){
    Tree * r = root;
    int ret = 0;
    while(p >= 0 && r){
      if(k & r->hbit){
        ret += r->bv->rank0Sign(p);
        p = r->bv->rank(p , 1) - 1;
        r = r->right;
      }else{
        if(r->hbit == 0){
          ret += r->bv->rank0Sign(p);
        }
        p = r->bv->rank(p , 0) - 1;
        r = r->left;
      }
    }
    return ret;
  }
};

int pos;
void dfs(
    int cur , int parent, int level,
    vector<int> & seq, vector<int> & signs,
    vector<int> & levels,
    vector<int> & parents,
    vector<int> & firstHits,
    const vector<int> & values,
    const vector<pair<int , int> > & edges , const vector<int> & vstart)
{
  seq[pos] = values[cur]; 
  signs[pos] = 1;
  firstHits[cur] = pos;
  levels[cur] = level;
  parents[cur] = parent;
  ++pos;
  for(int i = vstart[cur] ; i < edges.size() && edges[i].first == cur ; ++i){
    int v = edges[i].second;
    if(v == parent)continue;
    dfs(v , cur , level + 1 , seq ,signs , levels , parents , firstHits , values , edges , vstart);
  }
  seq[pos] = values[cur]; 
  signs[pos] = -1;
  ++pos;
}

void build_lca(vector< vector<int> > & P , const vector<int> & parents){
  for(int i = 0 ; i < P.size() ; ++i)
    for(int j = 0 ; (1 << j) < P.size() ; ++j)
      P[i][j] = -1;

  for(int i = 0 ; i < P.size() ; ++i)
    P[i][0] = parents[i];

  for (int j = 1; (1 << j) < P.size(); j++)
    for (int i = 0; i < P.size(); i++)
      if (P[i][j - 1] != -1)
        P[i][j] = P[P[i][j - 1]][j - 1];
}

int lca(int p , int q, const vector< vector<int> > & P , const vector<int> & parents , const vector<int> & L){
  if(L[p] < L[q]){
    swap(p , q);
  }
  int log = 1;
  for (; (1 << log) <= L[p]; log++);
  log--;
  for (int i = log; i >= 0; i--)
    if (L[p] - (1 << i) >= L[q])
      p = P[p][i];
  if (p == q)
    return p;
  for (int i = log; i >= 0; i--)
    if (P[p][i] != -1 && P[p][i] != P[q][i])
      p = P[p][i], q = P[q][i];

  return parents[p];
}
int main(){
  int N , Q;
  cin >> N >> Q;
  vector<int> values(N);
  vector< pair<int , int> > edges(2 * (N - 1) );
  for(int i = 0 ; i < N ; ++i){
    cin >> values[i];
  }
  for(int i = 0 ; i < N - 1 ; ++i){
    int u , v;
    cin >> u >> v;
    --u; --v;
    edges[i * 2] = make_pair(u , v);
    edges[i * 2 + 1] = make_pair(v , u);
  }
  sort(edges.begin() , edges.end());
  vector<int> vstart(N , -1);
  for(int i = 0 ; i < edges.size() ; ++i){
    int u = edges[i].first;
    if(vstart[u] < 0){
      vstart[u] = i;
    }
  }
  pos = 0;
  vector<int> seq(2 * N);
  vector<int> signs(2 * N);
  vector<int> levels(N);
  vector<int> parents(N);
  vector<int> firstHits(N);
  dfs(0 , 0 , 0 , seq , signs , levels , parents, firstHits, values, edges , vstart);
  vector< vector<int> > P(N , vector<int>(32));
  build_lca(P , parents);
  WTree wt(seq , signs);
  sort(values.begin() , values.end());
  for(int i = 0 ; i < Q ; ++i){
    int v , w , l;
    cin >> v >> w >> l;
    --v; --w;
    int lvw = lca(v, w , P , parents , levels);
    int low = 0;
    int high = values.size() - 1; 
    while(low < high){
      int mid = low + (high - low) / 2;
      int mv  = values[mid];
      int num = wt.rank(firstHits[v] , mv) + wt.rank(firstHits[w] , mv) - wt.rank(firstHits[lvw] , mv);
      if(lvw){
        num -= wt.rank(firstHits[parents[lvw]] , mv);
      }
      if(num >= l){
        high = mid;
      }else{
        low = mid + 1;
      }
    }
    cout << values[low] << endl;
  }
  return 0;
}

2011-03-25

GCJ Africa and Arabia 2011

| 00:14

GCJJの練習に同様のRegionalのコンテストであるGCJ Africa and Arabia 2011の問題を解いてみた。

http://code.google.com/codejam/contest/dashboard?c=842485#

問題のレベルとしてはSRMの500ぐらいの難易度かなと思った。

A. Vanishing Numbers

数字の消え方がカントール集合の構成方法そのままなので、あたえられた小数を三進小数に変換したときに1が初めに出現する桁の順で並べればよいことがわかる。

実数で計算すると精度の問題が出てくるので有理数クラスを使って計算する。

あと1が出現せず循環する場合だけど、100桁目までみて1がでてこなかったら出てこないと決め打ちで書いたら通ったw

import java.math.BigInteger;
import java.util.*;


public class A {
  static class Frac{
    BigInteger nume;
    BigInteger deno;
    Frac(BigInteger a , BigInteger b){
      nume = a;
      deno = b;
    }
    Frac sub(Frac o){
      return new Frac(nume.multiply(o.deno).subtract(deno.multiply(o.nume)) , deno.multiply(o.deno));
    }
    int comp(Frac o){
      return nume.multiply(o.deno).compareTo(deno.multiply(o.nume));
    }
  }
  //与えられた十進小数を三進小数に変換したときに1が初めに出現する位置を返す
  static int highestOneBit(String val){
    String vnume = val.substring(2);
    while(vnume.length() <= 10){
      vnume = vnume + "0";
    }
    Frac vf = new Frac(new BigInteger(vnume), BigInteger.TEN.pow(11));
    BigInteger two = new BigInteger("2");
    BigInteger three = new BigInteger("3");
    for(int i = 1 ; i <= 100 ; ++i){
      Frac divpow3 = new Frac(BigInteger.ONE , three.pow(i));
      Frac divpow32 = new Frac(two , three.pow(i));
      if(vf.comp(divpow3) >= 0){
        if(vf.comp(divpow32) > 0){
          vf = vf.sub(divpow32);          
        }else{
          return i;
        }
      }
    }
    return 101;
  }
  static class Pair implements Comparable<Pair>{
    int oneBitPos;
    double val;
    public Pair(int o , double v) {
      oneBitPos = o;
      val = v;
    }
    @Override
    public int compareTo(Pair o) {
      if(oneBitPos == o.oneBitPos){
        return Double.compare(val, o.val);
      }
      return oneBitPos - o.oneBitPos;
    }    
  }
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int T = sc.nextInt();
    for(int cn = 1 ; cn <= T ; ++cn){
      System.out.printf("Case #%d:\n" , cn);
      int N = sc.nextInt();
      Pair ps[] = new Pair[N];
      for(int i = 0 ; i < N ; ++i){
        String s = sc.next();
        ps[i] = new Pair(highestOneBit(s), Double.parseDouble(s));
      }
      Arrays.sort(ps);
      for(int i = 0 ; i < ps.length ; ++i){
        System.out.println(ps[i].val);
      }
    }
  }
}

B. Battlefield

オイラーの定理より、エッジを付け加えたあとの頂点の次数はすべて偶数である必要がある。

グラフが連結であれば、奇点の数/2が答えとなる。

連結でないときは奇点の数が多い連結成分同士をつなぎあわせるという処理を連結成分がひとつになるまで繰り返す。

import java.util.*;

public class B {
  static int dfs(int cp , boolean vis[] , int degree[] , boolean adj[][]){
    if(vis[cp])return 0;
    vis[cp] = true;
    int ret = degree[cp] % 2 == 0 ? 0 : 1;
    for(int i = 0 ; i < vis.length ; ++i){
      if(!adj[cp][i])continue;
      ret += dfs(i , vis , degree , adj);
    }
    return ret;
  }
  
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int T = sc.nextInt();
    for(int cn = 1 ; cn <= T ; ++cn){
      int N = sc.nextInt();
      int R = sc.nextInt();
      int degree[] = new int[N];
      boolean adj[][] = new boolean[N][N];              
      for(int i = 0 ; i < R ; ++i){
        int s = sc.nextInt();
        int t = sc.nextInt();
        degree[s]++;
        degree[t]++;
        adj[s][t] = adj[t][s] = true;
      }
      PriorityQueue<Integer> odds = new PriorityQueue<Integer>(10 , new Comparator<Integer>() {
        public int compare(Integer o1, Integer o2) {
          return o2 - o1;
        }
      });
      boolean vis[] = new boolean[N];
      for(int i = 0 ; i < N ; ++i){
        if(degree[i] == 0 || vis[i])continue;
        odds.add(dfs(i, vis, degree, adj));
      }
      int ret = 0;
      while(odds.size() > 1){
        int o0 = odds.poll();
        int o1 = odds.poll();
        if(o0 > 0 && o1 > 0){
          odds.add(o0 + o1 - 2);
        }else if(o0 == 0){
          odds.add(2);
        }else if(o1 == 0){
          odds.add(o0);
        }
        ++ret;
      }
      ret += odds.poll() / 2;
      System.out.printf("Case #%d: %d\n" , cn , ret);
    }
  }
}

C. Radio Receiver

ラジオの受信距離Dに関して二分探索.

Dを固定して、イベントを起きる時刻が早い順に処理していく。一つ前のイベントまでをすべて受信できる数直線上の位置の範囲を(left,right)とすると現在のイベントeを処理可能な範囲は(left - t , right + t)と(e.pos - D , e.pos + D)のintersectionとなる。(ここでtは現在のイベントと一つ前のイベントの間の時間)

import java.util.*;
public class C {
  static class Event implements Comparable<Event> {
    int pos;
    int time;
    Event(int p, int t) {
      pos = p;
      time = t;
    }
    @Override
    public int compareTo(Event o) {
      return time - o.time;
    }
  }

  static boolean can(double D, Event es[]) {
    double left = es[0].pos - D;
    double right = es[0].pos + D;
    for (int i = 1; i < es.length; ++i) {
      Event e = es[i];
      double t = e.time - es[i - 1].time;
      // intersect (left - t , right + t) and (e.pos - D , e.pos + D)
      left = Math.max(left - t, e.pos - D);
      right = Math.min(right + t, e.pos + D);
      if (left > right)
        return false;
    }
    return true;
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int C = sc.nextInt();
    for (int cn = 1; cn <= C; ++cn) {
      int N = sc.nextInt();
      Event es[] = new Event[N];
      for (int n = 0; n < N; ++n) {
        int p = sc.nextInt();
        int t = sc.nextInt();
        es[n] = new Event(p, t);
      }
      Arrays.sort(es);
      double low = 0.0;
      double high = 1.0E9;
      for (int rep = 0; rep < 100; ++rep) {
        double D = (low + high) * 0.5;
        if (can(D, es)) {
          high = D;
        } else {
          low = D;
        }
      }
      System.out.printf("Case #%d: %.9f\n", cn, low);
    }
  }
}

2010-12-16

ACM-ICPC 2010 Tokyo Regional Problem C

23:57

2010年のICPCアジア予選の問題Cを解いてみた。http://icpc2010.honiden.nii.ac.jp/regional-contest/problem

数直線上にN点が存在して、そのN点間の距離行列の値を降順にソートしたものが与えられる。このとき元の点の配置として考えられるものをすべて列挙せよという問題。

ここでN<=20である。

以下距離行列の値を降順に並べたものをD,各点の配置をPosと書く。

まず、一番長い距離が左端から右端までの点の距離となるのでPos[0]=0,Pos[N-1]=D[0]となる。

二番目に長い距離がどこに相当するかというと点1から点N-1までの距離か点0から点N-2までの距離のどちらかになる。

一般に点1から点Lおよび点Rから点N-1までの位置が決まってる時に今使える中で最も長い距離がどこに対応するかの候補としては点L+1から点N-1までの距離か点0から点R-1までの距離のどちらかである。

上のどちらかを選べば点L+1の位置もしくは点R-1のどちらかの位置は決定する。

以上の処理を再帰で書くと一回の再帰の中で2回の呼び出しがあり、深さは高々Nなので再帰関数は高々2^N回しか呼び出されず、再帰の中での計算量はO(N)より全体の計算量はO(N * 2^N)となりN<=20なので十分間に合う。

package icpc2010;

import java.io.File;
import java.util.*;

class Solver{
  Set<List<Integer>> result;
  int N;
  int D[] , pos[] , DCount[];
  boolean decr(int left , int right , int index){
    boolean f = true;
    for(int i = 0 ; i <= left ; ++i){
      int di = pos[index] - pos[i];
      DCount[di]--;
      if(DCount[di] < 0)
        f = false;
    }    
    for(int i = right ; i < N ; ++i){
      int di = pos[i] - pos[index];
      DCount[di]--;
      if(DCount[di] < 0)
        f = false;
    }    
    return f;
  }

  void incr(int left , int right , int index){
    for(int i = 0 ; i <= left ; ++i){
      int di = pos[index] - pos[i];
      DCount[di]++;
    }    
    for(int i = right ; i < N ; ++i){
      int di = pos[i] - pos[index];
      DCount[di]++;
    }    
  }
  void rec(int left , int right , int p){
    if(p >= D.length){
      List<Integer> list = new ArrayList<Integer>();
      for(int i = 1 ; i < pos.length ; ++i)
        list.add(pos[i] - pos[i - 1]);
      result.add(list);
      return ;
    }
    int d = D[p];
    if(DCount[d] == 0){
      rec(left , right , p + 1);
      return ;
    }
    // left + 1 を決定 
    pos[left + 1] = pos[N - 1] - d;
    if(decr(left, right, left + 1)){
      rec(left + 1 , right , p + 1);
    }
    incr(left, right, left + 1);
    // right - 1 を決定 
    pos[right - 1] = d;
    if(decr(left, right, right - 1)){
      rec(left , right - 1, p + 1);
    }
    incr(left, right, right - 1);
  }
  Set<List<Integer>> solve(int D[] , int N){
    result = new HashSet<List<Integer>>();
    this.D = D; this.N = N;    
    pos = new int[N];
    pos[0] = 0;
    pos[N - 1] = D[0];
    DCount = new int[401];
    for(int i = 1 ; i < D.length ; ++i)
      DCount[D[i]]++;
    rec(0 , N - 1 , 1);
    return result;
  }
}
public class C {
  public static void main(String[] args) throws Exception{
    Scanner sc = new Scanner(new File("C.in"));
    while(sc.hasNext()){
      int N = sc.nextInt();
      if(N == 0)break;
      int D[] = new int[N * (N - 1) / 2];
      for(int i = 0 ; i < D.length ; ++i){
        D[i] = sc.nextInt();
      }
      Solver solver = new Solver();
      Set<List<Integer>> set = solver.solve(D, N);
      List<List<Integer>> list = new ArrayList<List<Integer>>();
      for(List<Integer> l : set)
        list.add(l);
      Collections.sort(list, new Comparator<List<Integer>>(){
        @Override
        public int compare(List<Integer> o1, List<Integer> o2) {
          for(int i = 0 ; i < o1.size() ; ++i){
            int i1 = o1.get(i);
            int i2 = o2.get(i);
            if(i1 != i2)return i1 - i2;            
          }
          return 0;
        }
      });
      for(List<Integer> l : list){
        System.out.print(l.get(0));
        for(int i = 1 ; i < l.size() ; ++i){
          System.out.print(" " + l.get(i));
        }
        System.out.println();
      }
      System.out.println("-----");
    }
  }
}

2010-10-27

SRM 486 500

02:09

終了2分後に式があった。

i番目の要素とj番目の要素を考えたときにこれらのどちらかがpivotとして選ばれ、もう一方が逆側に移動する確率はL[i] > L[j]のとき2 / |k : L[i] <= L[k] && L[k] <= L[j]|となる、期待値の線形性を利用してあとは足すだけ

  public double getEval(int[] L) {
    double expected = 0.0;
    for(int i = 0 ; i < L.length ; ++i){
      for(int j = i + 1 ; j < L.length ; ++j){
        if(L[i] <= L[j])continue;        
        int cnt = 0;
        for(int k = 0 ; k < L.length ; ++k)
          if(L[j] <= L[k] && L[k] <= L[i])
            ++cnt;        
        expected += 2.0 / cnt; 
      }
    }
    return expected;
  }