懸賞問題

q<=17の素数までは正しいことを確認。
しかし17で10分弱かかってO(4^q)のアルゴリズム使ってるからq=19の２時間半が限界だなあ。q=23は一ヶ月かかる。こういう技術によって計算量に大幅に差がつくプラグラミングは理情に勝てないから嫌い。

import java.util.*;
class Check{
  public int q;
  public GF gf;
  public static void main(String args[]){
    Check temp=new Check();
    System.out.println("19");temp.roop(19);
  }
  public int check(ArrayList x,boolean[] y){//xがAでyがB。|C|を返す。
    int size=0;
    roop:
    for(int i=0;i<q;i++){
      for(int j=0;j<x.size();j++){
        if(y[gf.sub[i][(Integer)x.get(j)]]){
          size++;
          continue roop;
        }
      }
    }
    return size;
  }
  public void roop(int q0){
    q=q0;
    gf=new GF(q);
    ArrayList x=new ArrayList();
    boolean[] y=new boolean[q];
    x.add(1);//AもBも0は持っておらず1を持っていることに固定。
    y[0]=false;
    y[1]=true;
    saiki(2,true,x,y,1,1);
  }
  public void saiki(int i,boolean even,ArrayList x,boolean[] y,int sx,int sy){
    if(i==q){
      int c=check(x,y);
      if(c<q&&c<sx+sy-1)System.out.println("ダメでした大佐！");
      //printArray(x);printArray(y);System.out.println(sx+" "+sy+" "+c+"\n");//動作確認用
    }else{
      if(even){//evenはxで先に出たやつがyに入ってこないようにするためのフラグ。
        y[i]=false;
        saiki(i+1,true,x,y,sx,sy);
        y[i]=true;
        saiki(i+1,false,x,y,sx,sy+1);
        x.add(i);
        y[i]=true;
        saiki(i+1,true,x,y,sx+1,sy+1);
        x.remove(x.size()-1);
      }else{
        y[i]=false;
        saiki(i+1,false,x,y,sx,sy);
        y[i]=true;
        saiki(i+1,false,x,y,sx,sy+1);
        x.add(i);
        y[i]=false;
        saiki(i+1,false,x,y,sx+1,sy);
        y[i]=true;
        saiki(i+1,false,x,y,sx+1,sy+1);
        x.remove(x.size()-1);
      }
    }
  }
  public void printArray(ArrayList x){//動作確認用
    for(int i=0;i<x.size();i++){
      System.out.print((Integer)x.get(i)+" ");
    }
    System.out.println();
  }
  public void printArray(boolean[] x){//動作確認用
    for(int i=0;i<q;i++){
      if(x[i])System.out.print(i+" ");
    }
    System.out.println();
  }
  public class GF{//有限体上引き算の演算結果を保持。
  public int q;
  public int[][] sub;
    public GF(int q0) {
      q=q0;
      sub=new int[q][q];
      for(int i=0;i<q;i++){
        for(int j=0;j<q;j++){
          sub[i][j]=(i-j+q)%q;
        }
      }
    }
  }
}

おおマウンテンって大須から地下鉄で一本だ！しかし試合が正午開始となるといつ行くかが問題だ。