問題まとめ

DP

多次元DP

☆☆☆☆☆(20190819)
D - We Like AGC

☆☆☆☆(20190820)
D - パスタ (Pasta)

数え上げ

☆☆☆☆☆☆(20190820)
https://atcoder.jp/contests/abc104/tasks/abc104_d

二分探索

高速化

☆☆☆☆(20190820)

D - Lazy Faith

決め打ち

★★★★★★★★★

D - Widespread

☆☆☆

Sign In - AtCoder

優先探索

DFS

☆☆☆

A - 深さ優先探索

LIS

★★★★★★★★★★★
LISの応用: 前処理とLIS作成時に+αの処理を挟む D - プレゼント

BFS

☆☆☆☆

E - チーズ (Cheese)

bit全探索

累積和

剰余

★★★★★★★★★★★
D - Candy Distribution

数学

最大公約数

★★★★★★★

D - Factorization

解けるようになりたい問題

最小全域木

D - Built?

木(prioryty Queue)

C - 木

順列取得 next_permutation java

javaにはnext_permutationが実装されていないので自前で実装する.

目的

今回やりたいことはの集合が与えられた時に順列を全列挙する

{ 1 , 2 , 3 , 4 }

上の集合に対して以下を出力する

( 1 , 2 , 3 , 4 )
( 1 , 2 , 4 , 3 )
( 1 , 3 , 2 , 4 )
( 1 , 3 , 4 , 2 )
( 1 , 4 , 2 , 3 )
( 1 , 4 , 3 , 2 )
( 2 , 1 , 3 , 4 )
( 2 , 1 , 4 , 3 )
( 2 , 3 , 1 , 4 )
( 2 , 3 , 4 , 1 )
( 2 , 4 , 1 , 3 )
( 2 , 4 , 3 , 1 )
( 3 , 1 , 2 , 4 )
( 3 , 1 , 4 , 2 )
( 3 , 2 , 1 , 4 )
( 3 , 2 , 4 , 1 )
( 3 , 4 , 1 , 2 )
( 3 , 4 , 2 , 1 )
( 4 , 1 , 2 , 3 )
( 4 , 1 , 3 , 2 )
( 4 , 2 , 1 , 3 )
( 4 , 2 , 3 , 1 )
( 4 , 3 , 1 , 2 )
( 4 , 3 , 2 , 1 )

条件

• 全て列挙する
• 被ってはいけない
• 順番はよしなに(考えなくて良い)

実装方針

順列の並びを考えるときにはじめの文字から決定していき使ってない文字を後に追加していきます.
今までで使用した文字を記録しておくことと元の集合配列{ 1 , 2 , 3 , 4 }は崩さないようにしなければならないことが重要になってきます.
具体的には新しく構成する配列を別に持っておきこの配列に追加していく操作をします.

class MainA {
    public final static int[] elements = { 1, 2, 3, 4 };

    public static void main(String[] args) {
        int[] tmp = new int[4];     // 最終的に出力される配列
        boolean[] used = new boolean[4];  //  使用したか判定用に使う
        permutation(elements, tmp, used, 0);
    }

    static void permutation(int[] elements, int[] tmp, boolean[] used, int index) {
        if (index == 4) {
            // 出力処理を行う
            ShowArray(tmp);
            return;
        }
        ///////////////////////// main部分////////////////////////////
        for (int i = 0; i < 4; i++) {
            if (used[i])
                continue;
            used[i] = true;
            tmp[index] = elements[i];
            permutation(elements, tmp, used, index + 1);
            used[i] = false;
        }
    }

    // 出力関数
    static void ShowArray(int[] array) {
        System.out.print("(");
        for (int i = 0; i < 4; i++) {
            System.out.print(" " + array[i] + " ");
            if (i != 3) {
                System.out.print(",");
            }
        }
        System.out.println(")");
    }
}