kmjp's blog

競技プログラミング参加記です

NJPC 2017 : G - 交換法則

O(N^3)解法しか思いつかない…と思って本番あきらめたのに、O(N^3)解法でも通るの…?
http://njpc2017.contest.atcoder.jp/tasks/njpc2017_g

問題

文字列に対する2項演算子@を以下のように定義する。

  • X @ Y = min(X,Y) + max(X,Y)

文字列Sが与えられる。
Sの構成要素をバラしてそれぞれを1文字の文字列とする。
各文字列の並び順は任意とする場合、上記演算子と括弧を使い元の文字を構成できるか判定せよ。

解法

ある文字列Tを構成できるのは、下記の条件を満たす分割T=A+Bがある場合である。

  • A,Bはそれぞれ問題文の手順で構成可能
  • A≦B

Z-AlgorithmやSuffixArrayを使えばA,Bの大小判定は高速に求められるので、その場合O(|S|^3)解法になる。

それとは別に、maroonrk氏のSを構成法がわかりやすかったので紹介。
文字列のスタックを考える。
Sを構成する文字cを逆順に、以下の処理を行う。

  • c1文字からなる文字列をスタックに積む
  • スタックに2要素以上あり、(topから2番目の文字列)≦(topから1番目の文字列)なら、両者を取り除き(topから1番目の文字列)+(topから2番目の文字列)をスタックに積む、という処理を可能な限り繰り返す。
    • @は交換法則を満たすので、このような連結が可能である。

Sの全文字を処理したとき、スタックが1要素なら元のSが構成されている。
そうでないときはスタックの底から順に文字列が昇順に並んでおり、@演算子で順序を逆転できないので条件を満たせない。

string S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	vector<string> ST;
	for(i=S.size()-1;i>=0;i--) {
		ST.push_back(S.substr(i,1));
		while(ST.size()>=2) {
			x = ST.size();
			if(ST[x-1]<=ST[x-2]) {
				ST[x-2]=ST[x-1]+ST[x-2];
				ST.pop_back();
			}
			else break;
		}
	}
	
	if(ST.size()==1) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	
	
}

まとめ

本番スタックっぽい処理でうまくできないかなーと悩んではいたけど、こうも簡単に書けてしまうのね。