Hatena::Grouptopcoder

tsubosakaの日記

2012-10-20

SRM 558 275

19:40

重ね塗りとかを考えるのが、結構面倒で時間内に解けなかったので

http://topcoder.g.hatena.ne.jp/cafelier/20121020/1350662225

みたいにすれば良かったなと思った


import java.util.*;

public class Stamp {
  
  int getMinimum(int[] arr){
    int mi = 0;
    for(int i = 1 ; i < arr.length ; ++i)
      if(arr[i] < arr[mi])
        mi = i;
    return arr[mi];
  }

  boolean canColor(int index , int L , char c , char arr[]){
    for(int i = index ; i < index + L ; ++i){
      if(arr[i] == '*' || arr[i] == c)continue;
      return false;
    }
    return true;
  }
  // [0,current)までが塗られている状況で[current,current+L)をcolorで塗るための最小コストを返す
  int getMinCost(int[][] dp, int L , int current , int color){
    int min = 10000;
    if(current - L >= 0){ //[current-L, current)までが塗られている
      min = getMinimum(dp[current - L]) + 1;
    }
    for (int j = 0; j < current; ++j) {
      if (j + L < current)
        continue;
      min = Math.min(dp[j][color] + 1, min);
    }
    return min;
  }
    
  int minPush(char[] desiredColor, int L) {
    if(L == 1)return desiredColor.length;
    int len = desiredColor.length;
    char[] colors = {'R' , 'G' , 'B'};
    int dp[][] = new int[len][3];
    for (int i = 0; i < len; ++i) {
      Arrays.fill(dp[i], 10000);
    }
    for(int c = 0 ; c < 3 ; ++c){
      if(canColor(0, L, colors[c], desiredColor)){
        dp[0][c] = 1;
      }
    }
    for (int i = 1; i + L <= len; ++i) {
      for(int c = 0; c < 3 ; ++c){
        if(canColor(i, L, colors[c], desiredColor)){
          dp[i][c] = getMinCost(dp, L, i, c);
        }
      }
    }
    return getMinimum(dp[len - L]);
  }

  public int getMinimumCost(String desiredColor, int stampCost, int pushCost) {
    int res = Integer.MAX_VALUE;
    int L = desiredColor.length();
    for (int l = 1; l <= L; ++l) {
      int sc = l * stampCost;
      int pc = minPush(desiredColor.toCharArray(), l) * pushCost;
      res = Math.min(res, sc + pc);
    }
    return res;
  }
}

2012-01-30

FHC Round 1

21:09

Checkpoint

Sをa * bの形に分解したときに、両方がnCmの形になってることを確認する。


import java.util.HashMap;
import java.util.Scanner;

public class Checkpoint {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int maxS = 10000000;
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    int comb[][] = new int[4500][4500];
    comb[0][0] = 1; // 0C0 = 1
    for(int s = 1 ; s < comb.length ; ++s){
      comb[s][0] = 1;
      for(int k = 1 ; k < s ; ++k){
        if(comb[s-1][k-1] < 0 || comb[s-1][k] < 0){
          comb[s][k] = -1;
          continue;
        }
        comb[s][k] = comb[s-1][k-1] + comb[s - 1][k];        
        if(comb[s][k] >= maxS){
          comb[s][k] = -1;
        }
      }
      comb[s][s] = 1;
      for(int k = 2 ; k < s - 1 ; ++k){
        if(comb[s][k] < 0)continue;
        if(!map.containsKey(comb[s][k])){
          map.put(comb[s][k], s);          
        }
      }
    }
    int R = sc.nextInt();
    for(int r = 1 ; r <= R ; ++r){
      int S = sc.nextInt();
      int cand = solve(map, S);
      System.out.printf("Case #%d: %d\n" , r , cand);
    }
  }
  private static int solve(HashMap<Integer, Integer> map, int S) {
    int cand = get(S , map) + 1;      
    for(int div = 2 ; div * div <= S ; ++div){
      if(S % div != 0)continue;
      int m1 = get(div, map);
      int m2 = get(S / div, map);
      cand = Math.min(cand, m1 + m2);
    }
    return cand;
  }
  static int get(int div , HashMap<Integer, Integer> map){
    if(map.containsKey(div)){
      return map.get(div);
    }
    return div;
  }
}

Recover the sequence

コードにある通りの順でmerge sortを実行しつつ、debug sequenceを使ってoriginalの列を復元する

import java.util.Scanner;

public class Recover {
  static long checkSum(int[] arr){
    long result = 1;
    for(int i = 0 ; i < arr.length ; ++i){
      result = (31 * result + arr[i]) % 1000003;
    }
    return result;
  }
  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();
      String debug = sc.next();
      Recover rec = new Recover(N, debug);
      int arr[] = rec.recover();
      System.out.printf("Case #%d: %d\n" , cn , checkSum(arr));
    }
  }
  char darr[];
  int index;
  int N;
  public Recover(int N , String debug) {
    darr = debug.toCharArray();
    this.N = N;
  }
    
  void merge_sort_recover(int arr[] , int left , int right){
    int len = right - left;
    if(len == 1){
      arr[left] = 0;      
      return ;
    }
    int mid = left + len / 2;
    merge_sort_recover(arr, left, mid);
    merge_sort_recover(arr, mid, right);
    merge_recover(arr, left, right, mid);
  }
  private void merge_recover(int[] arr, int left, int right, int mid) {
    int larr[] = new int[mid - left];
    int rarr[] = new int[right - mid];
    int li = 0;
    int ri = 0;
    int v = 0;
    while(li < larr.length && ri < rarr.length){
      char d = darr[index++];
      if(d == '1'){
        larr[li++] = v++;
      }else{
        rarr[ri++] = v++;        
      }
    }
    while(li < larr.length){
      larr[li++] = v++;      
    }
    while(ri < rarr.length){
      rarr[ri++] = v++;
    }
    for(int i = left ; i < mid ; ++i){
      arr[i] = larr[arr[i]];
    }
    for(int i = mid ; i < right ; ++i){
      arr[i] = rarr[arr[i]];
    }
  }
  int[] recover(){
    int arr[] = new int[N];
    index = 0;
    merge_sort_recover(arr, 0, N);
    int result[] = new int[N];
    for(int i = 0 ; i < N ; ++i){
      result[i] = arr[i] + 1;
    }
    return result;
  }
}

Squished Status

DP

import java.util.Scanner;

public class SquishedStatus {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    long mod = 4207849484L;
    for(int cn = 1 ; cn <= N ; ++cn){
      int M = sc.nextInt();
      String message = sc.next();
      int L = message.length();
      long[] dp = new long[L + 1];
      dp[0] = 1;
      for(int s = 0 ; s < dp.length ; ++s){
        for(int n = s + 1 ; n <= s + 3 ; ++n){
          if(n > L)continue;
          String sub = message.substring(s, n);
          System.out.println(sub);
          if(sub.charAt(0) == '0')continue;
          int val = Integer.parseInt(sub);
          if(val > M)continue;
          dp[n] = (dp[n] + dp[s]) % mod;
        }
      }
      System.out.printf("Case #%d: %d\n", cn , dp[L]);
    }
  }
}

2011-12-27

SRM 526.5 Div1 500

23:02

二項分布の期待値と分散の式を使えばすごい簡単だった

各rangeにおけるgridごとのbeautyの期待値を計算する。10000 * 50 * 50なので間に合う。rangeの10000のところは値が変わるところだけ計算すればいいので工夫すれば50^3でいける。


public class MagicBlizzard {
  class Snow{
    long range , amount;
    double exp , exp2;
    Snow(long r , long a){
      range = r;
      amount = a;
      double prob = 1.0 / (2.0 * range + 1.0) / (2.0 * range + 1.0);
      // Binom(prob,amount)に従う確率変数Xに関してE[X],E[X^2]を計算する
      exp = amount * prob;
      // 分散の公式 E[X^2] = E[X]^2 + Var[X]を利用
      exp2 = exp * exp + amount * prob * (1 - prob);
    }
  }
  // 距離rangeにあるgridにおけるbeautyの期待値を返す
  private double calcExp(Snow[] ss, long range) {
    double expect = 0;
    for(int i = 0 ; i < ss.length ; ++i){
      if(ss[i].range < range)continue;
      expect += ss[i].exp2;
    }
    for(int i = 0 ; i < ss.length ; ++i){
      if(ss[i].range < range)continue;
      for(int j = i + 1 ; j < ss.length ; ++j){
        if(ss[j].range < range)continue;
        expect += 2 * ss[i].exp * ss[j].exp;
      }
    }
    return expect;
  }

  public double expectation(int[] range, int[] amount) {
    Snow ss[] = new Snow[range.length];
    for(int i = 0 ; i < ss.length ; ++i){
      ss[i] = new Snow(range[i] , amount[i]);
    }
    int rmax = 0;
    for(int r : range)
      rmax = Math.max(r, rmax);
    double expect = calcExp(ss, 0);
    for(long r = 1 ; r <= rmax ; ++r){
      expect += 8 * r * calcExp(ss, r);
    }    
    return expect;
  }
}

2011-10-01

GCJ Japan qual

19:30

A

W枚目のカードの初手での位置が分かればいいので逆からシミュレーションする

import java.util.Scanner;

public class A {
  static long rev(long M , long W , long A , long B){
    if(W <= B){
      return A + W - 1;
    }else if(W <= B + A - 1){
      return W - B;
    }else{
      return W;
    }
  }
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int T = sc.nextInt();
    for(int cn = 1 ; cn <= T ; ++cn){
      long M = sc.nextLong();
      int C = sc.nextInt();
      long W = sc.nextLong();
      long A[] = new long[C];
      long B[] = new long[C];
      for(int i = 0 ; i < C ; ++i){
        A[i] = sc.nextLong();
        B[i] = sc.nextLong();
      }      
      for(int i = C - 1 ; i >= 0 ; --i){
        W = rev(M , W , A[i] , B[i]);
      }
      System.out.printf("Case #%d: %d\n" , cn , W);
    }
  }
}

B

満足度の高いものから選んで行って、現在選んだものの賞味期限が切れないような条件でできるだけ選ぶ。とる個数は式考えるのがだったので二分探索で求めた。

import java.util.ArrayList;

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class B {
  static class S implements Comparable<S>{
    long c , t , s;
    S(long c , long t , long s){
      this.c = c;
      this.t = t;
      this.s = s;
    }
    @Override
    public int compareTo(S o) {
      if(s == o.s){
        return (int)Math.signum(t - o.t);
      }
      return (int)Math.signum(o.s - s);
    }
  }
  static boolean can(S s , List<S> list , long c){
    list.add(new S(c , s.t , s.s));
    Collections.sort(list, new Comparator<S>() {
      @Override        
      public int compare(S o1, S o2) { return (int)Math.signum(o1.t - o2.t);}
    });
    long day = 0;
    for(S x : list){
      if(day + x.c > x.t){
        return false;
      }
      day += x.c;
    }
    return true;
  }
  static long solve(int N , long K , S cs[]){    
    Arrays.sort(cs);
    long ret = 0;
    List<S> list = new ArrayList<S>();
    for(S s : cs){
      long low = 0;
      long high = s.c + 1;
      while(low < high){
        long mid = low + (high - low + 1) / 2;
        List<S> tmp = new ArrayList<S>(list);
        if(!can(s , tmp , mid)){
          high = mid - 1;
        }else{
          low = mid;
        }
      }
      low = Math.min(s.c, low);
      if(low > 0){
        ret += low * s.s;
        list.add(new S(low , s.t , s.s));
      }
    }
    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();
      long K = sc.nextLong();
      S cs[] = new S[N];
      for(int i = 0 ; i < N ; ++i){
        long c = sc.nextLong();
        long t = sc.nextLong();
        long s = sc.nextLong();
        cs[i] = new S(c , t , s);
      }
      long ret = solve(N , K , cs);
      System.out.printf("Case #%d: %d\n" , cn , ret);
    }
  }
}

C

下の桁からキャリーがある場合とない場合でDP

import java.util.Scanner;

public class C {
  static long solve(long N){
    long d0 = 0;
    long d1 = 0;
    for(long x = 1 ; x <= N ; x *= 2){
      boolean b = ((N & x) != 0);
      if(b){
        d0 = Math.max(d1 , d0 + 1);
        d1 = d1 > 0 ? d1 + 2 : 0;
      }else{
        d1 = Math.max(d0 + 2, d1 > 0 ? d1 + 1 : 0);
      }
    }
    return d0;
  }
  
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int T = sc.nextInt();
    for(int cn = 1 ; cn <= T ; ++cn){
      long N = sc.nextLong();
      System.out.printf("Case #%d: %d\n" , cn , solve(N));
    }
  }
}

2011-08-21

SRM 515

07:37

前に出たSRM 513と同様500が確率+メモ化で割と得意な問題だったので解けた。

250

愚直に0:00-23:59までを全通り試す。

public class RotatedClock {
  boolean eq(int h , int m , int h2 , int m2){
    for(int i = 0 ; i <= 12 ; ++i){
      if(h == h2 && m == m2)return true;
      h = (h + 30) % 360;
      m = (m + 30) % 360;
    }
    return false;
  }
  public String getEarliest(int hourHand, int minuteHand) {
    for(int h = 0 ; h < 12 ; ++h){
      for(int m = 0 ; m < 60 ; m += 2){
        int hd = (h * 60 + m) / 2;
        int md = m * 6;
        if(eq(hd , md , hourHand , minuteHand)){
          String ret = String.format("%02d:%02d", h , m);
          return ret;
        }
      }
    }
    return "";
  }
}

550

訪れたユーザの集合+残りの剣の数+現在時刻をキーにしたメモ化再帰。単純にユーザの集合を考えると2^24通りあるけど、一回しか訪れないユーザは訪れたというフラグを使う必要がないので2^12まで落ちる。あと再帰の手順のところで確率がその時点での条件付き確率になっているように前もって確率値を補正してやる。

import java.util.*;

public class NewItemShop {
  class Event implements Comparable<Event>{
    int u , t, c;
    double p;
    Event(int u , int t , int c , double p){
      this.u = u; this.t = t; this.c = c; this.p = p;
    }
    public int compareTo(Event o) {
      return t - o.t;
    }
  }
  
  long hashcode(long pat ,int s , int p){
    return (pat << 20L) | s * 32 | p;
  }
  Map<Long, Double> memo;
  double rec(int pattern , int sword , int p , Event[] es){
    if(sword == 0.0)return 0;
    if(p == es.length)return 0;
    long key = hashcode(pattern, sword, p);
    if(memo.containsKey(key)){
      return memo.get(key);
    }
    Event e = es[p];
    if((pattern & (1 << e.u)) != 0){
      double exp = rec(pattern , sword , p + 1 , es);
      memo.put(key, exp);
      return exp;
    }
    double prob = e.p;
    double exp = rec(pattern, sword, p + 1, es) * (1 - prob);
    if(freqs[e.u] == 1){
      double p1 = rec(pattern , sword - 1 , p + 1 , es) + e.c;
      double p2 = rec(pattern , sword , p + 1 , es);
      exp += Math.max(p1, p2) * prob;            
    }else{
      double p1 = rec(pattern | (1 << e.u) , sword - 1 , p + 1 , es) + e.c;
      double p2 = rec(pattern | (1 << e.u) , sword , p + 1 , es);
      exp += Math.max(p1, p2) * prob;      
    }
    memo.put(key, exp);
    return exp;
  }
  
  int freqs[];
  public double getMaximum(int swords, String[] customers) {
    List<Event> elist = new ArrayList<Event>();
    freqs = new int[customers.length];
    for(int i = 0 ; i < customers.length ; ++i){
      double T = 1.0;
      int cnt = 0;
      for(String e : customers[i].split("\\s+")){
        String[] sep = e.split(",");
        Event ev = new Event(i, Integer.parseInt(sep[0]), Integer.parseInt(sep[1]), Integer.parseInt(sep[2]));
        double p = ev.p * 0.01;
        ev.p = p / T;
        T -= p;
        elist.add(ev);
        ++cnt;
      }
      freqs[i] = cnt;
    }
    memo = new HashMap<Long, Double>();
    Collections.sort(elist);
    Event[] es = elist.toArray(new Event[0]);
    double res = rec(0, swords, 0, es);
    return res;
  }
}