山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

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

問題

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

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

順列-permutation

1から9までの数字を並び替えてできる数字は  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);
    }
}

感想

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