POJ 1349 - Coding of Permutations

http://poj.org/problem?id=1349

概要

1 .. n の順列である p が何番目の順列であるかを答える．

例えば n=4, p=(2,3,4,1) のとき，これはは10番目であり，p=(4,2,1,3) は21番目である．

制約

解法

「i 番目の数字が，残っている数の中で何番目か」を a[i] として，factorial(a[i]) を BigInteger で足していくだけ．

入力の形式が無意味に面倒．

 1 import java.util.*;
 2 import java.io.*;
 3 import java.math.*;
 4 
 5 public class Main {
 6   public static void main(String[] args) {
 7     BigInteger[] facts = new BigInteger[51];
 8     facts[0] = BigInteger.ONE;
 9     for (int i = 1; i <= 50; i++) {
10       facts[i] = facts[i-1].multiply(BigInteger.valueOf(i));
11     }
12 
13     Scanner cin = new Scanner(System.in);
14     String line;
15     ArrayList<BigInteger> ans = new ArrayList<BigInteger>();
16     while (!(line = cin.next()).equals("-1")) {
17       char[] s = line.toCharArray();
18       Pair p = readInt(s, 1);
19       int n = p.n;
20       int i = p.i+2;
21       int[] perm = new int[n];
22       for (int j = 0; j < n; j++) {
23         p = readInt(s, i);
24         perm[j] = p.n;
25         i = p.i+1;
26       }
27 
28       BigInteger m = BigInteger.ONE;
29       boolean[] used = new boolean[n];
30       for (int j = 0; j < n-1; j++) {
31         int c = 0;
32         for (int k = 0; k < perm[j]-1; k++) {
33           if (!used[k]) {
34             ++c;
35           }
36         }
37         m = m.add(facts[n-j-1].multiply(BigInteger.valueOf(c)));
38         used[perm[j]-1] = true;
39       }
40       ans.add(m);
41     }
42     int N = ans.size();
43     for (int i = 0; i < N; i++) {
44       if (i != 0) {
45         System.out.print(",");
46       }
47       System.out.print(ans.get(i));
48     }
49     System.out.println();
50   }
51 
52   static Pair readInt(char[] s, int i) {
53     int n = 0;
54     while ('0' <= s[i] && s[i] <= '9') {
55       n = 10*n + s[i]-'0';
56       i++;
57     }
58     return new Pair(n, i);
59   }
60 }
61 
62 class Pair {
63   public int n, i;
64   public Pair(int n, int i) {
65     this.n = n;
66     this.i = i;
67   }
68 }
poj/1349.java