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