AtCoder Beginner Contest 226C TLEの原因を知りたい

Question

ABCの226C(こちら)で3問程度TLEになってしまうのですが、原因がわかりません。
どのあたりが計算量が多くなってしまっているのか、教えていただけないでしょうか。
以下、コードです。

import java.util.*;

public class Main {
  static long ans=0;
  static List<Integer> list=new ArrayList<Integer>();
  static Scanner sc=new Scanner(System.in);
  static int n=sc.nextInt();
  static int t[]=new int[n+1];
  static int a[][]=new int[n+1][];
  public static void main(String[]args){
    for(int i=0;i<n;i++){
      t[i+1]=sc.nextInt();
      int k=sc.nextInt();
      a[i+1]=new int[k];
      for(int j=0;j<k;j++){
        a[i+1][j]=sc.nextInt();
      }
    }
    calc(n);
    ans+=(long)t[n];
    System.out.println(ans);
  }
  static void calc(int nn){
    for(int i=0;i<a[nn].length;i++){
      if(list.contains(a[nn][i])==false){
        list.add(a[nn][i]);
        ans+=(long)t[a[nn][i]];
      }
      if(a[nn].length!=0){
        calc(a[nn][i]);
      }
    }
  }
}

Comments

[jimbe]

ご自身で最大数のデータを用意して各所にログ表示を入れて確認してみれば良いのではないでしょうか。

Answer 1

ArrayListのcontainsが遅いせいではないでしょうか。

こちらのリンク先を参照してみてください。
特集！知らないと損をする計算量の話 3-2. vector (C++), ArrayList (Java), list (Python) からの検索処理は遅い

Comments

[den7]

返信が遅くなって申し訳ございません。おっしゃる通りでした。ありがとうございます。
ArrayListからHashSetに変更することで少し時間を短縮することができました。
(それと、単純に私の再起の書き方がよくなかったようです、、)

Answer 2

２つ問題がありました。
まず1つ目はactorbugさんにご指摘いただいたArrayListのcontainsは計算量がO(N)だったので、HashSetのcontains(計算量はO(1))に変更しました。参考URLはこちら
2つ目は再起呼び出しを不必要にしていたことです。以下が修正後のコードです。

import java.util.*;

public class Main {
  static long ans=0;
  static HashSet hs = new HashSet();
  static Scanner sc=new Scanner(System.in);
  static int n=sc.nextInt();
  static int t[]=new int[n+1];
  static int a[][]=new int[n+1][];
  public static void main(String[]args){
    for(int i=0;i<n;i++){
      t[i+1]=sc.nextInt();
      int k=sc.nextInt();
      a[i+1]=new int[k];
      for(int j=0;j<k;j++){
        a[i+1][j]=sc.nextInt();
      }
    }
    calc(n);
    //ans+=(long)t[n];
    System.out.println(ans);
  }
  static void calc(int nn){
    if(hs.contains(nn)==true){
      return;
    }else if(a[nn].length==0){
      hs.add(nn);
      ans+=(long)t[nn];
      return;
    }else{
      hs.add(nn);
      ans+=(long)t[nn];
      for(int i=a[nn].length-1;i>=0;i--){
        calc(a[nn][i]);
      }
    }
  }
}