2.1 POJ-1068

整数ナンバリング2は、蟻本関連にしようかなぁ、と思う。

蟻本に載ってた、POJ(http://poj.org/)っていうオンラインジャッジシステムのあるプログラミングコンテスト練習サイトに、ちょっと足を運んでいる。

Solvedは今の所、1000、1001、1068の3問。1000は「a,b2つの入力が与えられる。a+bの結果を出力せよ」っていう練習用問題で、1001は「R(0 < R < 99.9)とn(0 < n <= 25)が与えられる。R^nを「正確に」出力せよ」っていうちょっと骨のある問題。問題文が英語ってのもあって、R^nを見た時は「いきなりn次元ユークリッド空間の問題か…ヤバ」って思ってしまった。

で、これを解くのに色々と疲れたので、次は正答率の最も高い奴を解くことにした。それが1068だった。

ID.1068
Description
Let S = s1 s2...s2n be a well-formed string of parentheses. S can be encoded in two different ways:
q By an integer sequence P = p1 p2...pn where pi is the number of left parentheses before the ith right parenthesis in S (P-sequence).
q By an integer sequence W = w1 w2...wn where for each right parenthesis, say a in S, we associate an integer which is the number of right parentheses counting from the matched left parenthesis of a up to a. (W-sequence).

Following is an example of the above encodings:

　　S　　(((()()())))
　　P-sequence　　4 5 6666
　　W-sequence　　1 1 1456

Write a program to convert P-sequence of a well-formed string to the W-sequence of the same string.

Input
The first line of the input contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case is an integer n (1 <= n <= 20), and the second line is the P-sequence of a well-formed string. It contains n positive integers, separated with blanks, representing the P-sequence.

Output
The output file consists of exactly t lines corresponding to test cases. For each test case, the output line should contain n integers describing the W-sequence of the string corresponding to its given P-sequence.

Sample Input

2
6
4 5 6 6 6 6
9
4 6 6 6 6 8 9 9 9

Sample Output

1 1 1 4 5 6
1 1 2 4 5 1 1 3 9

Source
Tehran 2001

要は、カッコ(parentheses)で表現された文字列があって、その数列での表し方が2通りあるんだけど、一方の表現方法をもう一方の表現方法に変換してね、っていう問題。

アルゴリズムはいろいろあると思うけど、まずはカッコを用いた文字列に変換して、それを基にもう一方の表現方法に変換するようにした。
そんなに面白い問題ではないし、これ以上解説しても無意味っぽいので、練習問題がてらコードを載せてこの記事を締める。

#include <iostream>

using namespace std;

const int MAX_N = 20;
const int MAX_STRING = 64;

int main(){
	int t;
	cin >> t;
	for(int i=0; i<t; ++i){
		int n;
		cin >> n;
		int p[MAX_N];
		for(int j=0; j<n; ++j)	cin >> p[j];
		
		//()に変換
		char st[MAX_STRING];
		for(int j=0,k=0,left_num=0; j<2*n; ++j){
			if(left_num == p[k]){
				st[j] = ')';
				if(k < n-1)	++k;
			}
			else{
				st[j] = '(';
				++left_num;
			}
		}
		
		//W-sequenceに変換
		int w[MAX_N];
		for(int j=0,check_num=0; j<2*n; ++j){
			if(st[j] == ')'){
				for(int k=j-1,ok=0,left_num=0; k>=0; --k){
					if(st[k]=='(' && ok==0){
						++left_num;
						w[check_num] = left_num;
						break;
					}
					else if(st[k]=='('){
						--ok;
						++left_num;
					}
					else	++ok;
				}
				cout << w[check_num] << " ";
				++check_num;
			}
		}
		cout << endl;
	}
}