Parentheses [JAG Practice Contest for ACM-ICPC Asia Regional 2016 : D]

問題

http://jag2016autumn.contest.atcoder.jp/tasks/icpc2016autumn_d

「(」と「)」から構成された文字列があり、以下の条件を満たす文字列を答えよ

• A回隣接する文字をスワップすると括弧の対応が取れた文字列が作れる
• B(
• 複数回答があれば、その中で文字列長が最短で、かつ、辞書順最小
• ちなみに'(' < ')'

1 <= A <= 10^9

考察

1. Aがとても大きいので全探索とかDPとかそういう類じゃない
2. 恐らく実験ゲーだろう
3. まずは実験して規則性を見出す
4. 隣接する文字列をスワップする -> バブルソートっぽいアルゴリズムかな？
5. 部分問題に帰着できないか

6. 実験をひたすらすると以下のようなことが分かる

文字列長2 : A = 1
文字列長4 : A = 2-3
文字列長6 : A = 4-6
文字列長8 : A = 7-10
という感じに各変域でのAの最大値が+2,+3,+4,...されていってる
ということで、とりあえずAの値によって文字列長2nのnが導ける

文字列長6では、
A = 4 : ) ( ))((
A = 5 : )) ( )((
A = 6 : ))) ( ((
のように'('が1つだけ左に動くだけになってる。
なので、まずn個)を配置、n個(を配置して、Aの最大値との差だけ最も左の(を左にシフトすると答え

7. これを上手いことプログラムに落としこむ

実装

http://jag2016autumn.contest.atcoder.jp/submissions/863975

typedef long long ll;
int A;
//-----------------------------------------------------------------
int main() {
	cin >> A;
	ll a = 1, b = 2, n = 1;
	while (a < A) {
		a += b;
		b++;
		n++;
	}
 
	int d = a - A;
	string ans;
	rep(i, 0, n + 1) {
		if (i == n - d)
			ans += "(";
		else
			ans += ")";
	}
	rep(i, 0, n - 1) ans += "(";
	cout << ans << endl;
}