TopCoder SRM 314 DIV 1 Easy 練習

問題

1〜ある数まで、自身より左にある自身より大きい数の個数が与えられるので、条件を満たすように数列を復元しなさい。

解

深さ優先＆枝刈り。

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

public class StandInLine {
    int[] L, D, B;
    int N;
    public int[] reconstruct(int[] left) {
        L = left;
        N = left.Length;
        D = new int[N];
        B = new int[N];

        srch(0);
        return B;
    }

    private void srch(int p)
    {
        if (p == N)
        {
            D.CopyTo(B, 0);
            return;
        }

        for (int i = 0; i < N; ++i)
        {
            if (L[i] >= 0)
            {
                int h = i + 1, ct = 0;
                for (int j = 0; j < p; ++j)
                    if (D[j] > h)
                        ct++;
                if (ct != L[i]) // 関係がおかしい
                    continue;
                int tmp = L[i];
                L[i] = -1;
                D[p] = h;
                srch(p + 1);
                L[i] = tmp;
            }
        }
    }
}