Hatena::Grouptopcoder

tsubosakaの日記

2009-02-25

*[TCO]TCO 09 Qualification Round 1 Hard

| 00:21

与えられる数がすべて異なるために作れる素数は最小でも3ですべて奇数である。このため和が素数となりえるペアは奇数+偶数の形に限られて、それぞれの数をノードとしてみると二部グラフの最大マッチングをとけばよいことがわかる。


import java.util.*;

public class PrimePairs {
  public int[] matches(int[] numbers) {
    boolean ps[] = new boolean[2001];
    Arrays.fill(ps, true);
    ps[0] = ps[1] = false;
    for(int i = 2 ; i < ps.length ; i++){
      if(!ps[i])continue;
      for(int j = i + i ; j < ps.length ; j += i)
        ps[j] = false;
    }
    int n0 = numbers[0];
    int N = numbers.length;
    List<Integer> left = new ArrayList<Integer>();
    List<Integer> right = new ArrayList<Integer>();
    for(int i = 0 ; i < N ; i++){
      if((n0 % 2) == (numbers[i] % 2))left.add(numbers[i]);
      else right.add(numbers[i]);      
    }
    if(left.size() != right.size()){
      return new int[0];
    }
    boolean adj[][] = new boolean[N][N];
    int ls = left.size();
    for(int i = 0 ; i < left.size() ; i++){
      for(int j = 0 ; j < right.size() ; j++){
        int l = left.get(i);
        int r = right.get(j);
        if(ps[l + r])adj[i][j + ls] = true;        
      }
    }
    List<Integer> lst = new ArrayList<Integer>();
    for(int i = 0 ; i < right.size() ; i++){      
      if(adj[0][i + ls]){
        boolean tmp[][] = new boolean[N][N];
        for(int j = 0 ; j < N ; j++)
          tmp[j] = adj[j].clone();
        for(int j = 0 ; j < N ; j++){
          tmp[0][j] = false;
          tmp[j][i + ls] = false;
        }
        if(bipartite_matching(tmp, ls) + 1 == ls)
          lst.add(right.get(i));        
      }
    }
    Collections.sort(lst);
    int[] res = new int[lst.size()];
    for(int i = 0 ; i < res.length ; i++)
      res[i] = lst.get(i);    
    return res;
  }

  int bipartite_matching(boolean adj[][], int leftSize) {
    int match = 0;
    int matchTo[] = new int[adj.length];
    Arrays.fill(matchTo, -1);
    boolean visited[] = new boolean[adj.length];
    for (int u = 0; u < leftSize; u++) {
      Arrays.fill(visited, false);
      if (augment(adj, u, matchTo, visited))
        match++;
    }
    return match;
  }

  boolean augment(boolean adj[][], int u, int matchTo[], boolean visited[]) {
    if (u < 0)
      return true;
    for(int i = 0 ; i < adj[u].length ; i++){
      if(adj[u][i] && !visited[i]){
        visited[i] = true;
        if (augment(adj, matchTo[i], matchTo, visited)) {
          matchTo[u] = i;
          matchTo[i] = u;
          return true;
        }        
      }
    }
    return false;
  }
}

TCO 09 Qualification Round 1 Medium

| 00:19

1 <= min <= 10^12, min <= max <= min + 10^6のときに自乗数(4,9,16...)で割り切れない数が[min,max]にいくつあるか答えよという問題.

素因数の候補としてはsqrt(min) <= 10^6までの数の自乗した値に関して調べればよい。調べ方としては[min,max]の中で自乗数を素因数としてもつ最小の値から素因数おきにふるっていけばよい。

import java.util.*;

public class SquareFreeNumbers {
  public int getCount(long min, long max) {
    int N =(int)(max - min + 1);
    boolean memo[] = new boolean[N];
    Arrays.fill(memo, true);
    for(long p = 2 ; p * p <= max ; p++){
      long p2 = p * p;
      long s = ((min + p2 - 1)/ p2) * p2;
      for(; s <= max ; s += p2)
        memo[(int)(s - min)] = false;      
    }
    int res = 0;
    for(int i = 0 ; i < memo.length ; i++)
      if(memo[i])res++;    
    return res;
  }
}

TCO 09 Qualification Round 1 Easy

| 00:10

各数に関して自分より大きいものが何個あるかを数えるだけ。同じ場合は前にあるもののみを数える


public class SortingWithPermutation {
  public int[] getPermutation(int[] a) {
    int N = a.length;
    int[] res = new int[N];
    for(int i = 0 ; i < N ; i++){
      int cnt = 0;
      for(int j = 0 ; j < N ; j++)
        if((a[i] > a[j]) ||
           (a[i] == a[j] && i > j))
          cnt++;      
      res[i] = cnt;
    }
    return res;
  }
}

TCO 09 Qualification Round 1

| 00:07

全完.

250はN^2だと簡単に書ける.

500はmax < 2^40より高々2から2^20までの自乗に関して割り切れるかを調べればよい

1000は二部マッチング