Hatena::Grouptopcoder

tsubosakaの日記

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

ゲスト



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