半分全列挙による処理の高速化

Question

#半分全列挙について
ABCDから数を一つずつ選ぶとき、A+B+C+D/4 > A+B+C+D+k/5を満たす組み合わせの個数を数える問題を実装しましたが、nが大きくなるとタイムアウトエラーが起きます。(5秒以上処理にかかっている、処理結果は正常)
処理速度を高速化する方法を教えていただきたいです。

標準入力
n k
A1 A2 ... A_n
B1 B2 ... B_n
C1 C2 ... C_n
D1 D2 ... D_n

import java.util.*;
import java.util.LinkedList;
import java.util.List;

public class Main {
    public static int n;
    public static long p;
    public static String[][] a;
    public static String[][] b;
    public static List<Long> list = new LinkedList<>();
    public static List<Long> list2 = new LinkedList<>();
    public static int cnt = 0;

    public static void main(String args[] ) throws Exception {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        p = sc.nextInt();

        sc.skip("\n");
        a = new String[2][n];
        b = new String[2][n];
        for(int i = 0;i < 2;i++){
            a[i] = sc.nextLine().split(" ");
        }
        for(int i = 0;i < 2;i++){
            b[i] = sc.nextLine().split(" ");
        }

        containsBugWithDFS(0, 0);
        containsBugWithDFS2(0, 0);
        Collections.sort(list);
        Collections.sort(list2, Collections.reverseOrder());

        int j = 0;
        int i = 0;
       while(i < list.size()){
            if(j >= list2.size() || (list.get(i)+list2.get(j))/4.0 <= p){
                i++;
                j=0;
            }else{
                cnt++;
                j++;
            }    
       }
       System.out.println(cnt);
    }

    public static boolean containsBugWithDFS(long sum, int depth) {
		if (depth == 2) {
            list.add(sum);
            return true;
        }
		for (int i = 0; i < n; i++) {
			containsBugWithDFS(sum + Long.parseLong(a[depth][i]), depth + 1);
		}
		return true;
	}

    public static boolean containsBugWithDFS2(long sum, int depth) {
		if (depth == 2) {
            list2.add(sum);
            return true;
        }
		for (int i = 0; i < n; i++) {
			containsBugWithDFS2(sum + Long.parseLong(b[depth][i]), depth + 1);
		}
		return true;
	}
}

Comments

[m.ts10806]

＞タイムエラーが起きてしまします
実際のエラーログ提示してもらった方が良いかと

Answer 1

少なくとも2点挙げられます。
0. 入力をStringで保持し、計算のたびにlong変換していること
Stringから数値への変換はそれなりにコストがかかるのに、
a,bそれぞれの2段目は確実に2回変換を行う必要がある。
最初からlongに変換しておけば、計算するだけで済む。
0. LinkedListを使用していること
おそらくこちらが主原因。
LinkedListに対してgetを使う場合、必ずリストの端から番号を数えて要素を取得するため、時間がかかる。
LinkedListを使うことによるメリットがこのコードで見られないので、
素直にArrayListを使う方が良いと思われる。

Comments

[sayan]

ご回答ありがとうございます。おっしゃる通りLinkedListが原因でした。
リストでも種類によって処理速度に大きく差が出ることを知れたのはとても勉強になりました。
ありがとうございました！