結果
問題 | No.3015 アンチローリングハッシュ |
ユーザー | Lay_ec |
提出日時 | 2015-11-05 12:15:45 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 631 ms / 2,000 ms |
コード長 | 6,871 bytes |
コンパイル時間 | 6,354 ms |
コンパイル使用メモリ | 78,288 KB |
実行使用メモリ | 66,080 KB |
最終ジャッジ日時 | 2023-10-11 13:54:55 |
合計ジャッジ時間 | 18,057 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 361 ms
59,988 KB |
testcase_01 | AC | 364 ms
61,292 KB |
testcase_02 | AC | 280 ms
59,876 KB |
testcase_03 | AC | 280 ms
59,828 KB |
testcase_04 | AC | 244 ms
59,372 KB |
testcase_05 | AC | 274 ms
61,608 KB |
testcase_06 | AC | 396 ms
60,960 KB |
testcase_07 | AC | 243 ms
57,292 KB |
testcase_08 | AC | 460 ms
63,400 KB |
testcase_09 | AC | 525 ms
64,380 KB |
testcase_10 | AC | 593 ms
64,828 KB |
testcase_11 | AC | 595 ms
64,420 KB |
testcase_12 | AC | 557 ms
64,736 KB |
testcase_13 | AC | 592 ms
64,620 KB |
testcase_14 | AC | 631 ms
66,080 KB |
testcase_15 | AC | 542 ms
64,560 KB |
testcase_16 | AC | 571 ms
64,724 KB |
testcase_17 | AC | 628 ms
64,516 KB |
testcase_18 | AC | 248 ms
59,956 KB |
testcase_19 | AC | 249 ms
59,444 KB |
testcase_20 | AC | 362 ms
59,964 KB |
testcase_21 | AC | 415 ms
60,104 KB |
testcase_22 | AC | 292 ms
59,664 KB |
ソースコード
import java.io.*; import java.math.*; import java.util.*; public class LLL_BigDecimal { static final int digit=50; static BigDecimal IP(ArrayList<ArrayList<BigDecimal>> B1,int x,ArrayList<ArrayList<BigDecimal>> B2,int y){ BigDecimal res=BigDecimal.ZERO; int n=B1.size(); for(int i=0;i<n;i++){ res=res.add(B1.get(i).get(x).multiply(B2.get(i).get(y))); } return res; } static ArrayList<ArrayList<BigDecimal>> GS(ArrayList<ArrayList<BigDecimal>> Basis){ int n=Basis.size(); ArrayList<ArrayList<BigDecimal>> Basis_ = new ArrayList<ArrayList<BigDecimal>>(); for(int i=0;i<n;i++){ Basis_.add(new ArrayList<BigDecimal>()); for(int j=0;j<n;j++){ Basis_.get(i).add(Basis.get(i).get(j)); } } for(int i=1;i<n;i++){ for(int j=0;j<i;j++){ BigDecimal ip=IP(Basis,i,Basis_,j); BigDecimal ip2=IP(Basis_,j,Basis_,j); for(int k=0;k<n;k++){ BigDecimal val=Basis_.get(k).get(i); val=val.subtract( ip.divide(ip2,BigDecimal.ROUND_HALF_EVEN).multiply(Basis_.get(k).get(j)) ); //val-=ip/ip2*Basis_.get(k).get(j); Basis_.get(k).set(i,val); } } } return Basis_; } static BigDecimal PI2(ArrayList<ArrayList<BigDecimal>> Basis,ArrayList<ArrayList<BigDecimal>> Basis_, int i, int x){ int n=Basis.size(); ArrayList<BigDecimal> pi = new ArrayList<BigDecimal>(); for(int j=0;j<n;j++) pi.add(BigDecimal.ZERO.setScale(digit)); for(int j=i;j<n;j++){ BigDecimal ip=IP(Basis,x,Basis_,j); BigDecimal ip2=IP(Basis_,j,Basis_,j); for(int k=0;k<n;k++){ BigDecimal val=pi.get(k); val = val.add(ip.divide(ip2,BigDecimal.ROUND_HALF_EVEN).multiply(Basis_.get(k).get(j))); //val+=ip/ip2*Basis_.get(k).get(j); pi.set(k,val); } } BigDecimal res=BigDecimal.ZERO; for(int j=0;j<n;j++) res=res.add(pi.get(j).multiply(pi.get(j))); return res; } static ArrayList<BigDecimal> LLL(ArrayList<ArrayList<BigDecimal>> Basis){ int n=Basis.size(); BigDecimal delta= new BigDecimal((1.0/4.0)+Math.pow(3.0/4.0,(double)n/(double)(n-1))).setScale(digit,BigDecimal.ROUND_HALF_EVEN); ArrayList<BigDecimal> svp = new ArrayList<BigDecimal>(); for(int j=0;j<n;j++) svp.add(BigDecimal.ZERO); ArrayList<ArrayList<BigDecimal>> Basis_=GS(Basis); while(true){ /* for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ System.out.print(Basis.get(i).get(j)+" "); } System.out.println(); } System.out.println(); */ for(int i=0;i<n;i++){ for(int j=i-1;j>=0;j--){ BigDecimal c=IP(Basis,i,Basis_,j).divide(IP(Basis_,j,Basis_,j),BigDecimal.ROUND_HALF_EVEN).setScale(0,BigDecimal.ROUND_HALF_EVEN); //System.out.println(c+" "+Math.round(c)); for(int k=0;k<n;k++){ BigDecimal val=Basis.get(k).get(i); val = val.subtract(c.multiply(Basis.get(k).get(j))); //val-=Math.round(c)*Basis.get(k).get(j); Basis.get(k).set(i,val); Basis_=GS(Basis); } } } boolean cont=false; for(int i=0;i<n-1;i++){ BigDecimal p=PI2(Basis,Basis_,i,i); BigDecimal p2=PI2(Basis,Basis_,i,i+1); if(delta.multiply(p).compareTo(p2)==1){ for(int j=0;j<n;j++){ BigDecimal val=Basis.get(j).get(i); BigDecimal val2=Basis.get(j).get(i+1); Basis.get(j).set(i,val2); Basis.get(j).set(i+1,val); } Basis_=GS(Basis); cont=true; } if(cont) break; } if(cont) continue; else{ /* System.out.println("result"); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ System.out.print(Basis.get(i).get(j)+" "); } System.out.println(); } */ for(int i=0;i<n;i++){ svp.set(i,Basis.get(i).get(0)); } return svp; } } } public static void main(String args[]) throws IOException{ Scanner sc = new Scanner(System.in); int n; ArrayList<Integer> coe; String b=sc.next(),p=sc.next(); BigDecimal P=new BigDecimal(p).setScale(digit); BigDecimal B=new BigDecimal(b).setScale(digit); BigDecimal ONE = new BigDecimal(1).setScale(digit); BigDecimal TF = new BigDecimal(25).setScale(digit); for(n=4;;n+=4){ ArrayList<ArrayList<BigDecimal>> Basis = new ArrayList<ArrayList<BigDecimal>>(); for(int i=0;i<n;i++) Basis.add(new ArrayList<BigDecimal>()); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ Basis.get(i).add(BigDecimal.ZERO.setScale(digit)); } } for(int i=0;i<n-1;i++){ Basis.get(i).set(i,B.negate()); Basis.get(i+1).set(i,ONE); } Basis.get(0).set(n-1,P); ArrayList<BigDecimal> tmp=LLL(Basis); Collections.reverse(tmp); coe=new ArrayList<Integer>(); for(int i=0;i<n;i++){ coe.add(tmp.get(i).intValue()); } boolean ok=true; for(int i=0;i<n;i++){ if( tmp.get(i).abs().compareTo(TF)==1 ){ ok=false; } } if(ok){ break; } } char[] s = new char[n]; char[] t = new char[n]; for(int i=0;i<n;i++){ int smt=coe.get(i).intValue(); if(smt>=0){ s[i]=(char)('a'+smt); t[i]='a'; }else{ s[i]='a'; t[i]=(char)('a'-smt); } } String S = new String(s); String T = new String(t); System.out.println(S); System.out.println(T); } }