AtCoder Beginner Contest 008

Submission #6904960

Source codeソースコード

import java.util.*;

/**
 * @author masayamatu
 * 
 */
public class Main {


  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    List<List<Integer>> a = getPermutations(n-1);
    int[] c = new int[n];
    int[][] allcase = new int[factorial(n)][n];
    coin[][] allcasebf = new coin[factorial(n)][n];
    double ans = 0;
    for(int i = 0; i < n; i++) {
      c[i] = sc.nextInt();
    }
    for(int i = 0; i < factorial(n) ; i++) {
      int count = 0;
      for(int j = 0; j < n; j++) {
        allcase[i][j] = c[a.get(i).get(j)]; 
        allcasebf[i][j] =new coin(allcase[i][j],true);
      }
     coin.reverse(i,n,allcasebf);
     for(int j=0; j < n; j++) {
       if(allcasebf[i][j].fb == true ) {
         count++;
       }
     }
     ans += (double)count/(double)factorial(n);
    }
    System.out.println(ans);
    
   
    
    
  }
  public static class coin {
    int coinnum = 0;
    boolean fb = true;
      public coin(int coinnum, boolean fb) {
        this.coinnum = coinnum;
        this.fb=fb;
      }
      public static void reverse(int facto,int n ,coin coin[][]) {
        for(int i = 0; i < coin.length-1; i++) {
          for(int j = i+1; j < n; j++) {
            if(coin[facto][j].coinnum % coin[facto][i].coinnum == 0) {
              if( coin[facto][j].fb == false) {
                coin[facto][j].fb = true;
              } else {
                coin[facto][j].fb = false;
              }
            }
          }
        }
        
      }
  }
  private static List<List<Integer>> getPermutations(Integer n){
    if(n == null || n<0) {
      return null;
    }
    List<List<Integer>> results = new ArrayList<List<Integer>>();
    
    if(n == 0) {
      results.add(new ArrayList<Integer>(Arrays.asList(0)));
      return results;
    }
    List<List<Integer>> prevResults = getPermutations(n-1);
    
    for(List<Integer> permutation : prevResults) {
      for(int i = 0; i <= n; i++) {
        permutation.add(i,n);
        results.add(new ArrayList<Integer>(permutation));
        permutation.remove(n);
      }
      permutation.clear();
    }
    prevResults.clear();
    
    return results;
  }
  public static int factorial(int b) {
    if(b == 1) {
      return 1;
    }else {
      return b*factorial(b-1);
    }
  }
}

Submission

Task問題 C - コイン
User nameユーザ名 masayamatu
Created time投稿日時
Language言語 Java8 (OpenJDK 1.8.0)
Status状態 TLE
Score得点 99
Source lengthソースコード長 2419 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_01.txt,sample_02.txt,sample_03.txt
Subtask1 99 / 99 subtask1_01.txt,subtask1_02.txt,subtask1_03.txt,subtask1_04.txt,subtask1_05.txt,subtask1_06.txt,subtask1_07.txt,subtask1_08.txt,subtask1_09.txt,subtask1_10.txt,subtask1_11.txt,subtask1_12.txt,subtask1_13.txt,subtask1_14.txt,subtask1_15.txt,subtask1_16.txt,subtask1_17.txt,subtask1_18.txt,subtask1_19.txt,subtask1_20.txt
Subtask2 0 / 1 subtask1_01.txt,subtask1_02.txt,subtask1_03.txt,subtask1_04.txt,subtask1_05.txt,subtask1_06.txt,subtask1_07.txt,subtask1_08.txt,subtask1_09.txt,subtask1_10.txt,subtask1_11.txt,subtask1_12.txt,subtask1_13.txt,subtask1_14.txt,subtask1_15.txt,subtask1_16.txt,subtask1_17.txt,subtask1_18.txt,subtask1_19.txt,subtask1_20.txt,subtask2_01.txt,subtask2_02.txt,subtask2_03.txt,subtask2_04.txt,subtask2_05.txt,subtask2_06.txt,subtask2_07.txt,subtask2_08.txt,subtask2_09.txt,subtask2_10.txt,subtask2_11.txt,subtask2_12.txt,subtask2_13.txt,subtask2_14.txt,subtask2_15.txt,subtask2_16.txt,subtask2_17.txt,subtask2_18.txt,subtask2_19.txt,subtask2_20.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample_01.txt AC 95 ms 20052 KB
sample_02.txt AC 97 ms 20692 KB
sample_03.txt AC 99 ms 19668 KB
subtask1_01.txt AC 98 ms 21716 KB
subtask1_02.txt AC 112 ms 21460 KB
subtask1_03.txt AC 95 ms 18768 KB
subtask1_04.txt AC 1253 ms 52524 KB
subtask1_05.txt AC 1253 ms 50856 KB
subtask1_06.txt AC 149 ms 21076 KB
subtask1_07.txt AC 1242 ms 53976 KB
subtask1_08.txt AC 111 ms 19924 KB
subtask1_09.txt AC 98 ms 19792 KB
subtask1_10.txt AC 1252 ms 51760 KB
subtask1_11.txt AC 112 ms 21204 KB
subtask1_12.txt AC 1245 ms 51928 KB
subtask1_13.txt AC 98 ms 19796 KB
subtask1_14.txt AC 150 ms 25556 KB
subtask1_15.txt AC 1254 ms 50476 KB
subtask1_16.txt AC 1243 ms 50776 KB
subtask1_17.txt AC 1255 ms 53040 KB
subtask1_18.txt AC 1256 ms 51760 KB
subtask1_19.txt AC 1261 ms 52456 KB
subtask1_20.txt AC 1255 ms 51632 KB
subtask2_01.txt TLE
subtask2_02.txt TLE
subtask2_03.txt TLE
subtask2_04.txt TLE
subtask2_05.txt TLE
subtask2_06.txt TLE
subtask2_07.txt TLE
subtask2_08.txt TLE
subtask2_09.txt TLE
subtask2_10.txt TLE
subtask2_11.txt TLE
subtask2_12.txt TLE
subtask2_13.txt TLE
subtask2_14.txt TLE
subtask2_15.txt TLE
subtask2_16.txt TLE
subtask2_17.txt TLE
subtask2_18.txt TLE
subtask2_19.txt TLE
subtask2_20.txt TLE