結果

問題 No.3015 アンチローリングハッシュ
ユーザー Lay_ecLay_ec
提出日時 2015-11-05 12:15:45
言語 Java21
(openjdk 21)
結果
AC  
実行時間 724 ms / 2,000 ms
コード長 6,871 bytes
コンパイル時間 4,110 ms
コンパイル使用メモリ 82,308 KB
実行使用メモリ 63,896 KB
最終ジャッジ日時 2024-09-13 12:38:08
合計ジャッジ時間 16,550 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 404 ms
59,848 KB
testcase_01 AC 411 ms
60,252 KB
testcase_02 AC 318 ms
58,164 KB
testcase_03 AC 320 ms
58,240 KB
testcase_04 AC 268 ms
58,296 KB
testcase_05 AC 304 ms
58,144 KB
testcase_06 AC 445 ms
60,428 KB
testcase_07 AC 266 ms
58,128 KB
testcase_08 AC 499 ms
62,968 KB
testcase_09 AC 606 ms
63,480 KB
testcase_10 AC 665 ms
63,452 KB
testcase_11 AC 673 ms
63,628 KB
testcase_12 AC 633 ms
63,436 KB
testcase_13 AC 655 ms
63,844 KB
testcase_14 AC 705 ms
63,532 KB
testcase_15 AC 610 ms
63,456 KB
testcase_16 AC 645 ms
63,896 KB
testcase_17 AC 724 ms
63,616 KB
testcase_18 AC 276 ms
58,184 KB
testcase_19 AC 277 ms
58,064 KB
testcase_20 AC 391 ms
59,316 KB
testcase_21 AC 461 ms
60,584 KB
testcase_22 AC 314 ms
58,288 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

    }
}
0