Hatena::Grouptopcoder

tsubosakaの日記

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