TCO2016R3AEasy ParenthesesAndPermutation

• July 24, 2016
• TopCoder, Interesting

想定解が賢すぎる．

問題概要(原文)

以下の制約を満たす $2N$ 文字の(validな)括弧列 $s,t$ は存在するか？存在するなら一例を示せ．

• $s_i = t_{p_i}$ を満たす

考察

validな括弧列 $x$ の条件とは以下を満たす

• '(' を $1$ ，')' を $-1$ に置き換える．
• $x_1 + x_2 + \ldots + x_i \geq 0$
• $x_1+ x_2 + \ldots + x_{2N} = 0$

これは以下のように言い換えられる

• $i$ 文字目までに少なくとも '(' が $\frac{i+1}{2}$ 個ある
• $2N$ 文字目の時点で '(' と ')' がそれぞれ $N$ 個ある

条件を満たす $s$ を一つ構築することにする． 初め，全ての文字を ')' ということにする．$2k + 1 (0 \leq k)$ 文字目の時点で $s_i = $ ')' $(1 \leq i \leq 2k+1)$ であるような $i$ を一つ選んで， '(' を ')' に置換できる． これをやるだけで，validな $s$ を構築できる．

このとき，どのような $i$ を選ぶのが最適かを考える． $p_i$ が最小のものを選ぶのが良いことが分かる(何故なら括弧列を作る際になるべく '(' を左側に寄せて損することはないので)．

こうしてできた $t$ がvalidかどうか判定すればよい．計算量は $O(NlogN)$

ソースコード

using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
public class ParenthesesAndPermutation
{
    public string getSequence(int[] p)
    {
        var n = p.Length;
        var s = new char[n];
        var t = new char[n];
        for (int i = 0; i < n; i++)
            s[i] = t[i] = ')';
        var set = new SortedSet<int>();
        for (int i = 0; i < n; i++)
        {
            set.Add(p[i] * n + i);
            if (i % 2 == 0)
            {
                var min = set.Min;
                set.Remove(min);
                var ii = min % n;
                var jj = min / n;
                s[ii] = t[jj] = '(';
            }
        }
        var v = 0;
        foreach (var x in t)
        {
            if (x == '(') v++;
            else v--;
            if (v < 0) return "Impossible";
        }
        return new string(s);
    }
}

コメント

• 想定解，言われると当たり前なのに気づけないし，面白い問題だと思う

• greedy

• Twitter
•