Hatena::Grouptopcoder

tsubosakaの日記

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