SRM497 Div2 Medium

Div2 Medium

問題の分析
数列の大小関係を表す文字列が渡されるので、その大小関係を満たすよう１〜Nの数字を並べなさい。
複数答えがある場合は、辞書順で最も小さいものを返しなさい。
方針
１からNまで順に並べた状態から処理をスタートする。
頭からsignatureを見ていき、Dがあったら数字の順序を入れ替えることでsignatureを満たす数列を作成する。
バブルソートの逆バージョンのようなイメージ？

ソースコード
最初はsignatureの位置iにDがあったら、i番目〜1番目までを調べてDがあったら順序を入れ替えるようにしていました。

using System;
using System.Collections.Generic;
using System.Text;
 
 
public class PermutationSignature
{
    public int[] reconstruct(string signature)
    {
        string sig = "I" + signature;
        int[] ans = new int[sig.Length];
        for (int i = 0; i < ans.Length; i++)
            ans[i] = i + 1;
 
 
        for (int i = 1; i < sig.Length; i++)
        {
            if (sig[i].Equals('D'))
            {
                for (int j = i; j >= 1; j--)
                {
                    if (sig[j].Equals('D'))
                    {
                        int swap = ans[j - 1];
                        ans[j - 1] = ans[j];
                        ans[j] = swap;
                    }
                }
            }
        }
        return ans;
    }
}

が、これは間違いでDが連続している場合のみi番目からさかのぼって順序を入れ替えていくのが正しいようです。

using System;
using System.Collections.Generic;
using System.Text;
 
 
public class PermutationSignature
{
    public int[] reconstruct(string signature)
    {
        string sig = "I" + signature;
        int[] ans = new int[sig.Length];
        for (int i = 0; i < ans.Length; i++)
            ans[i] = i + 1;
 
 
        for (int i = 1; i < sig.Length; i++)
        {
            if (sig[i].Equals('D'))
            {
                for (int j = i; j >= 1; j--)
                {
                    if (sig[j].Equals('I')) break;
                    int swap = ans[j - 1];
                    ans[j - 1] = ans[j];
                    ans[j] = swap;
                }
            }
        }
        return ans;
    }
}