結果

問題 No.3015 アンチローリングハッシュ
ユーザー Lay_ecLay_ec
提出日時 2015-11-05 02:01:18
言語 Java21
(openjdk 21)
結果
AC  
実行時間 163 ms / 2,000 ms
コード長 5,887 bytes
コンパイル時間 4,199 ms
コンパイル使用メモリ 80,996 KB
実行使用メモリ 54,588 KB
最終ジャッジ日時 2024-09-13 12:31:58
合計ジャッジ時間 8,784 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 155 ms
54,372 KB
testcase_01 AC 152 ms
54,296 KB
testcase_02 AC 149 ms
54,048 KB
testcase_03 AC 151 ms
54,296 KB
testcase_04 AC 137 ms
53,696 KB
testcase_05 AC 151 ms
54,380 KB
testcase_06 AC 152 ms
54,332 KB
testcase_07 AC 151 ms
54,128 KB
testcase_08 AC 161 ms
54,180 KB
testcase_09 AC 161 ms
54,404 KB
testcase_10 AC 162 ms
54,400 KB
testcase_11 AC 163 ms
54,288 KB
testcase_12 AC 157 ms
54,300 KB
testcase_13 AC 161 ms
54,588 KB
testcase_14 AC 162 ms
54,136 KB
testcase_15 AC 160 ms
54,116 KB
testcase_16 AC 162 ms
54,276 KB
testcase_17 AC 161 ms
54,132 KB
testcase_18 AC 146 ms
54,196 KB
testcase_19 AC 148 ms
54,364 KB
testcase_20 AC 152 ms
54,144 KB
testcase_21 AC 154 ms
54,292 KB
testcase_22 AC 153 ms
54,068 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

public class LLL {
    static double IP(ArrayList<ArrayList<Double>> B1,int x,ArrayList<ArrayList<Double>> B2,int y){
        double res=0;
        int n=B1.size();
        for(int i=0;i<n;i++){
            res+=B1.get(i).get(x)*B2.get(i).get(y);
        }
        
        return res;
        
        
    }
    
    static ArrayList<ArrayList<Double>> GS(ArrayList<ArrayList<Double>> Basis){
        int n=Basis.size();
        ArrayList<ArrayList<Double>> Basis_ = new ArrayList<ArrayList<Double>>();
        for(int i=0;i<n;i++){
            Basis_.add(new ArrayList<Double>());
            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++){
                double ip=IP(Basis,i,Basis_,j);
                double ip2=IP(Basis_,j,Basis_,j);
                for(int k=0;k<n;k++){
                    double val=Basis_.get(k).get(i);
                    val-=ip/ip2*Basis_.get(k).get(j);
                    Basis_.get(k).set(i,val);
                }
            }
        }
        
        return Basis_;
    }
    
    static double PI2(ArrayList<ArrayList<Double>> Basis,ArrayList<ArrayList<Double>> Basis_, int i, int x){
        int n=Basis.size();
        ArrayList<Double> pi = new ArrayList<Double>();
        for(int j=0;j<n;j++) pi.add(0.0);
        
        for(int j=i;j<n;j++){
            double ip=IP(Basis,x,Basis_,j);
            double ip2=IP(Basis_,j,Basis_,j);
            
            for(int k=0;k<n;k++){
                double val=pi.get(k);
                val+=ip/ip2*Basis_.get(k).get(j);
                pi.set(k,val);
            }
        }
        
        double res=0;
        for(int j=0;j<n;j++) res+=pi.get(j)*pi.get(j);
        return res;
        
    }
    
    static ArrayList<Double> LLL(ArrayList<ArrayList<Double>> Basis){
        int n=Basis.size();
        double delta=(1.0/4.0)+Math.pow(3.0/4.0,(double)n/(double)(n-1));
        ArrayList<Double> svp = new ArrayList<Double>();
        for(int j=0;j<n;j++) svp.add(0.0);
        ArrayList<ArrayList<Double>> 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--){
                    double c=(IP(Basis,i,Basis_,j)/IP(Basis_,j,Basis_,j));
                    //System.out.println(c+" "+Math.round(c));
                    for(int k=0;k<n;k++){
                        double val=Basis.get(k).get(i);
                        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++){
                double p=PI2(Basis,Basis_,i,i);
                double p2=PI2(Basis,Basis_,i,i+1);
                if(delta*p>p2){
                    for(int j=0;j<n;j++){
                        double val=Basis.get(j).get(i);
                        double 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;
        double b=sc.nextDouble(),p=sc.nextDouble();
        for(n=4;;n+=4){
            ArrayList<ArrayList<Double>> Basis = new ArrayList<ArrayList<Double>>();
            for(int i=0;i<n;i++) Basis.add(new ArrayList<Double>());
            
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    Basis.get(i).add(0.0);
                }
            }
            
            for(int i=0;i<n-1;i++){
                Basis.get(i).set(i,-b);
                Basis.get(i+1).set(i,1.0);
            }
            Basis.get(0).set(n-1,p);
            
            ArrayList<Double> 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(Math.abs(coe.get(i))>25){
                    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