TCHS08 Championship Round Easy 練習

問題

ある数列Xに対して、Xの各要素がふたつずつ出現し、ある数nふたつの位置がちょうどn+1離れている(間にn個の要素が挟まれている)ような数列(Langford sequence)を考える。

数列が与えられるので、その数列に対するLangford sequenceのうち辞書順で最小のものを求めなさい。

解

元の数列の要素数が8以下と死ぬほど小さいので全探索の方向で。

さらにある数nとnの間にn個の要素があるっていう素晴らしい枝刈り条件が与えられているので使う。

using System;
using System.Text;
using System.Text.RegularExpressions;
using System.Collections;
using System.Collections.Generic;

public class LangfordSequence {
    int[] D, X, F, B;
    int N;
    bool S;

    public int[] getFirst(int[] a) {
        N = a.Length * 2;
        X = a;
        F = new int[a.Length];
        D = new int[N];
        B = new int[N];
        S = false;

        for (int i = 0; i < F.Length; ++i) F[i] = 2;

        srch(0);
        if (S)
            return B;
        else
            return new int[0];
    }

    private void srch(int p)
    {
        if (p == N)
        {
            if (!S)
            {
                D.CopyTo(B, 0);
                S = true;
                return;
            }
            for (int i = 0; i < N; ++i)
            {
                if (B[i] != D[i])
                {
                    if (B[i] > D[i])
                        D.CopyTo(B, 0);
                    return;
                }
            }
            return;
        }

        for (int i = 0; i < X.Length; ++i)
        {
            if (F[i] > 0) 
            {
                if (F[i] == 1) 
                {
                    int pos = p - 1;
                    if (pos - X[i] < 0) continue;
                    if (D[pos - X[i]] != X[i]) continue;
                }
                D[p] = X[i];
                F[i]--;
                srch(p + 1);
                F[i]++;
            }
        }
    }
}