C++の練習を兼ねて, AtCoder Regular Contest 120 の 問題D (Bracket Score 2) を解いてみた.
■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 問題Dで, stack の 復習ができたので, 良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 120 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題D／AC版).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
// 解き直し. // https://atcoder.jp/contests/arc120/editorial/1567 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using P = pair<int, int>; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) #define pb push_back #define a first #define b second P a[404040]; int c[404040]; // 白色 … 0, 黒色 … 1. char ans[404040]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N * 2){ int x; scanf("%d", &x); P p; p.a = x; p.b = i; a[i] = p; } // 2. sort. sort(a, a + N * 2); // 3. 白黒で塗り分ける. repx(i, N, N * 2) c[a[i].b] = 1; // 4. 括弧列を生成. stack<P> st; // {色, 位置}. rep(i, N * 2){ if(st.empty()){ st.push({c[i], i}); continue; } P p = st.top(); if(p.a != c[i]){ st.pop(); ans[p.b] = '('; ans[i] = ')'; }else{ st.push({c[i], i}); } } // 5. 出力. rep(i, N * 2) printf("%c", ans[i]); return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
[入力例] 2 1 2 3 4 [出力例] (()) ※AtCoderテストケースより [入力例] 2 2 3 2 3 [出力例] ()() ※AtCoderテストケースより [入力例] 25 15 34 74 100 33 22 82 59 48 94 20 14 120 83 35 100 44 20 14 113 4 122 116 92 28 59 24 32 49 3 50 93 104 32 85 50 49 61 92 78 55 55 50 94 49 108 69 19 69 56 [出力例] (())(())()(())()((()()))()((((())()(()))()()())()) [入力例] 50 11641 11322 7163 7244 3976 7791 7281 699 3094 4504 202 8464 8790 794 4252 543 2151 2824 5560 8375 12278 4939 413 9317 9325 11267 95 11559 12048 5875 3671 5987 335 8900 2825 2480 8890 6940 1068 10774 4915 7193 2371 10944 2737 10753 9995 611 191 11053 3762 1512 1149 4373 10958 12226 4535 3183 2006 6402 2918 8013 10403 4542 7955 733 525 9262 11905 7275 11489 9912 5127 4503 12028 7866 7454 3260 3111 7735 4613 3454 2098 10405 2728 1536 8755 7409 4002 5896 965 7901 2502 2619 5937 2678 6457 3000 4962 7431 [出力例] (((()(())))(()))(())()()(()((()()())(()()()()(())())))(())()()()()()(((())((())()))())(()()())()()() |
■参照サイト
AtCoder Regular Contest 120