Aizu Online Judge 1201 Lattice Practices

■1201 Lattice Practices

まず，10枚の板から5枚を選び，その5枚で構成出来るパターンを全て列挙．列挙の際，反転させても変わらない板がある場合があるので，重複を考慮する必要がある．それぞれのパターンに対応するパターンを残りの5枚で構成できうるかを判定する． 10個から5個選ぶ…₁₀P₅=30240 反転の種類…2⁵=32

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.   
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  int INF=1<<28;  
14.  double EPS=1e-9;  
15.   
16.  int[] a, rev;  
17.  int n, m;  
18.   
19.  void run(){  
20.   n=10;  
21.   m=n/2;  
22.   a=new int[n];  
23.   rev=new int[1<<m];  
24.   for(int i=0; i<1<<m; i++){  
25.    int x=i;  
26.    x=(x&0x55555555)<<1|(x>>1)&0x55555555;  
27.    x=(x&0x33333333)<<2|(x>>2)&0x33333333;  
28.    x=(x&0x0f0f0f0f)<<4|(x>>4)&0x0f0f0f0f;  
29.    x=(x<<24)|((x&0xff00)<<8)|((x>>8)&0xff00)|(x>>24);  
30.    rev[i]=(int)(x>>(32-m))&((1<<m)-1);  
31.   }  
32.   
33.   for(;;){  
34.    for(int i=0; i<n; i++){  
35.     String s=sc.next();  
36.     if(s.equals("END")){  
37.      return;  
38.     }  
39.     a[i]=Integer.parseInt(s, 2);  
40.    }  
41.    solve();  
42.   }  
43.  }  
44.   
45.  void solve(){  
46.   int ans=0;  
47.   int[] b=new int[m];  
48.   int[] c=new int[m];  
49.   int comb=(1<<m)-1;  
50.   boolean[] used=new boolean[m];  
51.   
52.   for(; comb<1<<n;){  
53.    // 2^(反転させても同じものの個数)で割る  
54.    int div=1;  
55.    for(int i=0, j=0, k=0; k<10; k++){  
56.     if((comb>>k&1)==1){  
57.      b[i++]=a[k];  
58.      if(rev[a[k]]==a[k]){  
59.       div*=2;  
60.      }  
61.     }else{  
62.      c[j++]=a[k];  
63.     }  
64.    }  
65.   
66.    Arrays.sort(b);  
67.    int sum=0;  
68.    for(;;){  
69.     // 2^n通り反転させる  
70.     for(int sup=0; sup<1<<m; sup++){  
71.      for(int i=0; i<m; i++){  
72.       if((sup>>i&1)==1){  
73.        b[i]=rev[b[i]];  
74.       }  
75.      }  
76.      // bの並びをcで構築できるか  
77.      Arrays.fill(used, false);  
78.      sum++;  
79.      for(int i=0; i<m; i++){  
80.       int bits=0;  
81.       for(int j=0; j<m; j++){  
82.        bits=(bits<<1)|(b[j]>>i&1);  
83.       }  
84.       int k=-1;  
85.       for(int j=0; j<m; j++){  
86.        if(!used[j]  
87.          &&((c[j]^bits)==(1<<m)-1||(rev[c[j]]^bits)==(1<<m)-1)){  
88.         k=j;  
89.        }  
90.       }  
91.       if(k>=0){  
92.        used[k]=true;  
93.       }else{  
94.        sum--;  
95.        break;  
96.       }  
97.      }  
98.      for(int i=0; i<m; i++){  
99.       if((sup>>i&1)==1){  
100.        b[i]=rev[b[i]];  
101.       }  
102.      }  
103.     }  
104.     if(!nextPermutation(b)){  
105.      break;  
106.     }  
107.    }  
108.    ans+=sum/div;  
109.   
110.    int x=comb&-comb, y=comb+x;  
111.    comb=((comb&~y)/x>>1)|y;  
112.   }  
113.   ans/=8; // 鏡像反転*回転  
114.   println(""+ans);  
115.  }  
116.   
117.  boolean nextPermutation(int[] is){  
118.   int n=is.length;  
119.   for(int i=n-1; i>0; i--){  
120.    if(is[i-1]<is[i]){  
121.     int j=n;  
122.     while(is[i-1]>=is[--j]);  
123.     swap(is, i-1, j);  
124.     rev(is, i, n);  
125.     return true;  
126.    }  
127.   }  
128.   rev(is, 0, n);  
129.   return false;  
130.  }  
131.   
132.  void swap(int[] is, int i, int j){  
133.   int t=is[i];  
134.   is[i]=is[j];  
135.   is[j]=t;  
136.  }  
137.   
138.  void rev(int[] is, int i, int j){  
139.   for(j--; i<j; i++, j--){  
140.    int t=is[i];  
141.    is[i]=is[j];  
142.    is[j]=t;  
143.   }  
144.  }  
145.   
146.  void debug(Object... os){  
147.   System.err.println(Arrays.deepToString(os));  
148.  }  
149.   
150.  void print(String s){  
151.   System.out.print(s);  
152.  }  
153.   
154.  void println(String s){  
155.   System.out.println(s);  
156.  }  
157.   
158.  public static void main(String[] args){  
159.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
160.   new Main().run();  
161.  }  
162. }  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int[] a, rev;
 int n, m;

 void run(){
  n=10;
  m=n/2;
  a=new int[n];
  rev=new int[1<<m];
  for(int i=0; i<1<<m; i++){
   int x=i;
   x=(x&0x55555555)<<1|(x>>1)&0x55555555;
   x=(x&0x33333333)<<2|(x>>2)&0x33333333;
   x=(x&0x0f0f0f0f)<<4|(x>>4)&0x0f0f0f0f;
   x=(x<<24)|((x&0xff00)<<8)|((x>>8)&0xff00)|(x>>24);
   rev[i]=(int)(x>>(32-m))&((1<<m)-1);
  }

  for(;;){
   for(int i=0; i<n; i++){
    String s=sc.next();
    if(s.equals("END")){
     return;
    }
    a[i]=Integer.parseInt(s, 2);
   }
   solve();
  }
 }

 void solve(){
  int ans=0;
  int[] b=new int[m];
  int[] c=new int[m];
  int comb=(1<<m)-1;
  boolean[] used=new boolean[m];

  for(; comb<1<<n;){
   // 2^(反転させても同じものの個数)で割る
   int div=1;
   for(int i=0, j=0, k=0; k<10; k++){
    if((comb>>k&1)==1){
     b[i++]=a[k];
     if(rev[a[k]]==a[k]){
      div*=2;
     }
    }else{
     c[j++]=a[k];
    }
   }

   Arrays.sort(b);
   int sum=0;
   for(;;){
    // 2^n通り反転させる
    for(int sup=0; sup<1<<m; sup++){
     for(int i=0; i<m; i++){
      if((sup>>i&1)==1){
       b[i]=rev[b[i]];
      }
     }
     // bの並びをcで構築できるか
     Arrays.fill(used, false);
     sum++;
     for(int i=0; i<m; i++){
      int bits=0;
      for(int j=0; j<m; j++){
       bits=(bits<<1)|(b[j]>>i&1);
      }
      int k=-1;
      for(int j=0; j<m; j++){
       if(!used[j]
         &&((c[j]^bits)==(1<<m)-1||(rev[c[j]]^bits)==(1<<m)-1)){
        k=j;
       }
      }
      if(k>=0){
       used[k]=true;
      }else{
       sum--;
       break;
      }
     }
     for(int i=0; i<m; i++){
      if((sup>>i&1)==1){
       b[i]=rev[b[i]];
      }
     }
    }
    if(!nextPermutation(b)){
     break;
    }
   }
   ans+=sum/div;

   int x=comb&-comb, y=comb+x;
   comb=((comb&~y)/x>>1)|y;
  }
  ans/=8; // 鏡像反転*回転
  println(""+ans);
 }

 boolean nextPermutation(int[] is){
  int n=is.length;
  for(int i=n-1; i>0; i--){
   if(is[i-1]<is[i]){
    int j=n;
    while(is[i-1]>=is[--j]);
    swap(is, i-1, j);
    rev(is, i, n);
    return true;
   }
  }
  rev(is, 0, n);
  return false;
 }

 void swap(int[] is, int i, int j){
  int t=is[i];
  is[i]=is[j];
  is[j]=t;
 }

 void rev(int[] is, int i, int j){
  for(j--; i<j; i++, j--){
   int t=is[i];
   is[i]=is[j];
   is[j]=t;
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}