結果
問題 | No.452 横着者のビンゴゲーム |
ユーザー |
![]() |
提出日時 | 2016-12-04 01:26:56 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 787 ms / 3,000 ms |
コード長 | 1,460 bytes |
コンパイル時間 | 2,599 ms |
コンパイル使用メモリ | 78,304 KB |
実行使用メモリ | 52,716 KB |
最終ジャッジ日時 | 2024-11-29 00:06:20 |
合計ジャッジ時間 | 20,636 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
package src; import java.util.*; class B{ static Scanner s = new Scanner(System.in); public static void main(String[] args) { int size = s.nextInt(); int[][] in = new int[size][size]; Card[] cards = new Card[s.nextInt()]; for (int i=0;i<cards.length;i++) { for(int j=0;j<size;j++) for(int k=0;k<size;k++) in[j][k] = Integer.parseInt(s.next()); cards[i] = new Card(in,size*size*cards.length); } int v=0; for(int i=0;i<cards.length;i++) { for(int j=i+1;j<cards.length;j++) { v=Math.max(v, cards[i].match(cards[j])); } } System.out.println(size*2-1-v); } } class Card{ ArrayList<BitSet> edge; Card(int[][] in,int max) { int size = in.length; edge = new ArrayList<>(in.length*2+2); BitSet h =new BitSet(max), v =new BitSet(max), t1=new BitSet(max), t2=new BitSet(max); for(int i=0;i<size;++i) { h.clear(); v.clear(); for(int j=0;j<size;++j) { h.set(in[i][j]); v.set(in[j][i]); } edge.add((BitSet)h.clone()); edge.add((BitSet)v.clone()); t1.set(in[i][i]); t2.set(in[i][size-i-1]); } edge.add(t1); edge.add(t2); } public int match(Card card) { int r=0,max=edge.get(0).cardinality(); roop: for(int i=0;i<edge.size();i++) { BitSet b = card.edge.get(i); for(int j=0;j<edge.size();j++) { BitSet bb = ((BitSet) b.clone()); bb.and(edge.get(j)); r=Math.max(r, bb.cardinality()); if(r==max) break roop; } } return r; } }