[yukicoder] No.90 品物の並び替え

問題

No.90 品物の並び替え - yukicoder

全探索の問題で、順列を列挙して解くことができる問題です。

順列-permutation

1から9までの数字を並び替えてできる数字は 通りあります。これがまさに順列なんですが、Javaには残念ながら？permulationというメソッドはありません。第三者が提供しているライブラリにはあるそうですが、競技プログラミングでは使うことが難しいです。まあ、コピペすればいいば大丈夫なのかな？

したがって、順列を生成するプログラムを自分で用意する必要があります。順列は再帰で求めることができるようですが、僕には書けなかったので、コピペすることにしました。

下記のサイトで再帰ではなく、for文で順列を生成しているコードを参考にしました。 tails.hatenablog.jp

順列を表示

public class Test {
    public static void main(String[] args) {
        int l = 1;
        String s = "";
        int N = 4;
        for(int i = 0; i < N; i++) {
            l = l *(i + 1);
            s += Integer.toString(i);
        }
        String t = s;
        s += " ";

        for(int i = 1; i <= l; i++) {
            System.out.println(t);
            int a = i;
            int b = 2;
            while(a % b == 0) {
                a /= b++;
            }
            s = new StringBuffer(s.substring(0, b)).reverse() + s.substring(b);
            t = s.substring(0, N);
        }
    }
}

正直このコードをあまり理解できていないので、僕の中ではブラックボックス化されています。

順列を元に比較

この問題では、順列を元にアイテムの番号を比較するので、計算量が[tex : O(N!]以上になります。

コード

import java.util.Scanner;

public class Exec0090 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int M = scan.nextInt();
        String [][]item = new String[M][2];
        int []score = new int[M];
        for(int i = 0; i < M; i++) {
            for(int j = 0; j < 2; j++) {
                item[i][j] = scan.next();
            }
            score[i] = scan.nextInt();
        }
        scan.close();

        int l = 1;
        String s = "";
        for(int i = 0; i < N; i++) {
            l = l *(i + 1);
            s += Integer.toString(i);
        }
        s += " ";
        //String s = "012345678";
        int max = 0;
        for(int i = 1; i <= l; i++) {
            int p = 0;
            System.out.println(s);
            for(int j = 0; j < M; j++) {
                int k1 = s.indexOf(item[j][0]);
                int k2 = s.indexOf(item[j][1]);
                if(k1 < k2) {
                    p += score[j];
                }
            }
            if(max < p) {
                max = p;
            }
            int a = i;
            int b = 2;
            while(a % b == 0) {
                a /= b++;
            }
            s = new StringBuffer(s.substring(0, b)).reverse() + s.substring(b);
        }
        System.out.println(max);
    }
}

感想

順列のプログラムを自分で書けるようにならないといけませんね。再帰を使う方法からやってみます。