私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「サッカー選手を並べ替えて！」（CodeIQ）を参照してください。
Javaで解答しています。
import java.util.*;
public class Main {
/**
* 計算結果のメモ
*/
private List<byte[]>[] Results;
/**
* コンストラクタ
* Nのサイズで0埋めされた初期値を作成する
* @param N トータルの人数
*/
public Main(int N){
int M = N/2+1;
Results = new List[M];
for(int i=0; i<M; i++){
Results[i] = new ArrayList<>();
}
byte[] a = new byte[N];
Results[M-1].add(a);
}
/**
* 引数noに渡された背番号を配置した新たな配列を作成し、リストに追加する
* @param no 背番号
* @param b 一つ前の背番号まで配置された配列
*/
private void makeArray(byte no, byte[] b){
for(int p1=0, p2=p1+no+1; p2<b.length; p1++, p2++){
byte[] nb = Arrays.copyOf(b, b.length);
if( (nb[p1] == 0) && (nb[p2] == 0)){
nb[p1] = no;
nb[p2] = no;
Results[no-1].add(nb);
}
}
}
public void makeFootbollerArray(byte N){
byte M = (byte)(N/2);
for(byte i=M; i>0; i--){
List<byte[]> lst = Results[i];
for(byte[] b: lst){
makeArray(i, b);
}
}
}
public void printCount(int no){
System.out.println(Results[no].size());
}
/**
* @param args the command line arguments 1~11
*/
public static void main(String[] args) {
byte N = 22;
if(args.length != 0){
N = (byte) (Byte.parseByte(args[0].trim()) * 2);
}
Main fa = new Main(N);
fa.makeFootbollerArray(N);
fa.printCount(0);
}
}
組み合わせ数が膨大になるパターンの問題です。
私は動的計画法を用いて次の様に考えました。
数が大きいと説明が面倒なので1〜3で説明します。
まず、3の配置を考えます。人数は6なので背番号3の配置は次の様になります。
この時、2つの3の間のスペースは背番号の値なのでそれぞれを配置すべき場所は簡単に計算できます。
「3 _ _ _ 3 _」……(A)
「_ 3 _ _ _ 3」……(B)
これをメモしておきます。
次に2をメモしておいたパターンに対して配置します。配置できるのはすでに数字が割り当てられていない場所です
(A)のパターンに対して考えてみます。
「2 _ _ 2 _ _」は先頭の2の場所に3があるのでダメです。
「_ 2 _ _ 2 _」は後ろの2の場所に3があるのでダメです。
「_ _ 2 _ _ 2」は先頭の2も後ろの2も空いている場所に入るのでOKです。
OKになったパターン（「3 _ 2 _ 3 2」）をメモしておきます。
同様にパターン(B)についても処理します。
同様に1についても処理します。
「3 _ 2 _ 3 2」に対しては「_ 1 _ 1 _ _」だけがOKです。
この結果もメモに残しておきます。
背番号1まで処理した時点で背番号1が入ったメモの数が答えになります。
MainクラスのResultsがメモですが「バイト配列」の「リスト」の「配列」というややこしい構造になっています。
Results[背番号]は背番号を大きい方から処理した時の並び方のパターンを保持します。パターンの数はわからないので動的に追加できるようListになっていて、各パターンの並びはバイトの配列です。
例の様に背番号が1〜3の場合の具体的な構造を示すと次の様になります。
Results[0] = {[3,1,2,1,3,2], [2,3,1,2,1,3]}
Results[1] = {[3,0,2,0,3,2], [2,3,0,2,0,3]}
Results[2] = {[3,0,0,0,3,0], [0,3,0,0,0,3]}
Results[3] = {[0,0,0,0,0,0]}
選手の並びは背番号で表し、0の場所はまだ誰も配置されていないことを表します。
Resultsの様素数は背番号の数+1です。1多いのは1回も配置していない場合（全部0）を初期値として使用するためです。
Resultsの初期化をしています。
Resultsの要素数は先の説明の通り背番号の最大値+1です。
各要素は要素数0のリストで初期化してしまいます。
そして最大の要素番号のリストは[0,0,…,0]を初期値としてセットします。
このメソッドで背番号の大きい方から順に配置を決定します。大きい方からなので43行目のループはデクリメントです。
44行目で最後に確定したパターンの並びのリストを取得し、そのリストを1つずつmakeArray()に渡して次の背番号のパターンを作ります。
引数noに渡された背番号を引数bに配置します。そして配置可能なパターンを全てResultsに追加します。
30行目のループ条件が少々複雑です。ループが終わるのは「3 _ _ _ 3」のように並んでいる右側の選手が最後の位置に来た時なのでそれをチェックします。ループカウンタのp1は左側の選手の位置、p2は右側の選手の位置です。p1とp2の間にはnoに等しいスペースがあるのでp2=p1+no+1になります。
後はp1とp2の位置がすでに配置済みかをチェックし（33行目）、配置済みでなかったら配置してResultsに追加することを繰り返すだけです。
最終的にResults[0]が背番号1まで配置した時のパターンが列挙されたものになるのでその数をカウントすれば答えになります。
最初に書いた通り、問題が少し理解しにくく斜め読みした段階で問題を読み取れなかったため結構長い間放置してありました。解いていない問題がかなり少なくなってから改めて読み直したら問題を理解できたので挑戦しました。
やってみたら結構面白く、良い問題と思います。
ちなみに、これをJavaでやったのは30行目のループを書きたかった＆動的な配列（List）が欲しかったからです。このころメインに使っていたのはPythonでしたが、Pytonでは30行目のようなループが書けません。ちょっとわかりにくいしバッファオーバランの危険性があるのでPythonではこういう書き方はできないようになっているのでしょうが、たまにこういう書き方もできるといいのにと思います。