Hatena::Grouptopcoder

tsubosakaの日記

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

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

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/tsubosaka/20090420