Codeforces Round #288 DIV2 E問題 - Arthur and Brackets

Source

Codeforces Round #288 DIV2 E問題 (2500pt)
Problem description

問題概要

長さ $2N$ の対応関係がちゃんと付いている $N$ 組のカッコからなる文字列を考える.
開くカッコ $\verb|(|$ の位置が左の方から,カッコ $1,2,\ldots,N$ と番号を付ける.
カッコ $k$ は,開くカッコと閉じるカッコの位置の差は $L_k$ 以上 $R_k$ 以下である.
$L_k, R_k$ が与えられるので,条件を満たす $2N$ 文字のカッコの列を $1$ つ求める問題.
条件を満たす文字列が存在しないならそれを指摘する.

解法

貪欲法.
カッコ $N,N-1,N-2,\ldots$ という順番(内側から)で考えていく.
開くカッコは,今までの文字列の一番左にくっつけなければいけないとして,閉じるカッコはできるだけ開くカッコに近い位置にくっつけるのが良い.
なぜなら,新しくくっつけた開くカッコと閉じるカッコを両端とする区間はグループ化され,その間にはもう閉じるカッコを追加することができないから.
よって,できるだけ距離を近くにした方が,後々に多くの選択肢を残すことができるから.
時間計算量は,愚直にグループ化などを実装して $O(N^2)$ 程度.
区間DPをすれば $O(N^3)$ 程度で,更にうまくGreedyすれば $O(N)$ で求めることもできるらしい.

C++のスパゲッティなコード

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar()
#define mypc(c) putchar(c)

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);}
void writer(const char x[], char c){int i;for(i=0;x[i]!='\0';i++)mypc(x[i]);mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}

int N, L[666], R[666];
string str[1577], tmp;

int main(){
  int i, j, k, x;
  int dame = 0, st, ed;
  string res;

  reader(&N);
  rep(i,N) reader(L+i,R+i);

  st = ed = 777;
  for(k=N-1;k>=0;k--){
    if(L[k]==1){ st--; str[st] = "()"; continue; }
    j = 1;
    REP(i,st,ed){
      j += str[i].size();
      if(L[k] <= j && j <= R[k]){
        tmp = "(";
        while(st <= i) tmp += str[st], st++;
        tmp += ")";
        st--;
        str[st] = tmp;
        break;
      }
    }
    if(i==ed){dame=1; break;}
  }
  if(dame){
    writerLn("IMPOSSIBLE");
  } else {
    res = "";
    REP(i,st,ed) res += str[i];
    writerLn(res.c_str());
  }


  return 0;
}

Current time: 2017年07月23日15時40分43秒
Last modified: 2015年01月28日23時11分54秒 (by laycrs)
Tags: Competitive_Programming Codeforces CF288 CF_Div2_E
トップページに戻る

Logged in as: unknown user (not login)

ログイン: