C++の練習を兼ねて, 競プロ典型 90 問 の 問題060 (Chimera) を解いてみた.
■感想.
1. 問題060は, 実装方針を決めることが出来たので, AC版に到達出来たと思う.
2. LIS(Longest increase subsequence) の 復習ができたので, 非常に良かったと思う.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.
詳細は, 本家のサイト(GitHub) 競プロ典型 90 問 の 問題060 を ご覧下さい.
■C++版プログラム(問題060／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 60 61 62 63 64 65 66 67 68 69 70 71 72 |
// 以下の過去問を参照. // https://atcoder.jp/contests/abc134/tasks/abc134_e // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vi = vector<int>; 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 #define all(x) x.begin(), x.end() int a[303030]; P dpL[303030], dpR[303030]; // {数列の長さ, 最大値} int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%d", &a[i]); // 2. 狭義単調増加な数列の長さの最大値は？ // -> LIS(Longest increase subsequence) を 利用. // 2-1. 左から右方向へチェック. vi lLis; rep(i, N){ // 数列を保存. if(lLis.size() == 0 || lLis.back() < a[i]){ lLis.pb(a[i]); }else{ int at = lower_bound(all(lLis), a[i]) - lLis.begin(); lLis[at] = a[i]; } // インデックス i における数列の長さ, 最大値 を 保存. dpL[i].a = lLis.size(); dpL[i].b = lLis.back(); } // 2-2. 右から左方向へチェック. vi rLis; repr(i, N - 1, 0){ // 数列を保存. if(rLis.size() == 0 || rLis.back() < a[i]){ rLis.pb(a[i]); }else{ int at = lower_bound(all(rLis), a[i]) - rLis.begin(); rLis[at] = a[i]; } // インデックス i における数列の長さ, 最大値 を 保存. dpR[i].a = rLis.size(); dpR[i].b = rLis.back(); } // 3. 最大個数を計算. int ans = 0; rep(i, N){ int t = dpL[i].a + dpR[i].a; if(dpL[i].b == dpR[i].b) t--; ans = max(ans, t); } // 4. 出力. printf("%d\n", ans); 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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
[入力例] 6 1 2 3 3 2 1 [出力例] 5 ※AtCoderテストケースより [入力例] 4 1 2 3 4 [出力例] 4 ※AtCoderテストケースより [入力例] 5 3 3 3 3 3 [出力例] 1 ※AtCoderテストケースより [入力例] 15 1 6 11 10 1 11 4 10 13 4 9 9 15 4 11 [出力例] 7 [入力例] 30 17 24 25 23 10 10 23 13 20 2 6 4 9 7 7 8 21 9 7 8 18 20 8 3 21 21 22 22 5 19 [出力例] 10 [入力例] 120 15 33 6 39 8 11 25 32 16 4 28 25 17 12 46 38 40 21 10 18 28 20 48 29 39 12 48 37 45 37 48 39 32 33 41 48 22 15 44 31 31 31 15 30 38 24 49 4 11 40 46 1 45 50 22 31 2 25 26 2 25 4 30 38 45 28 23 13 45 22 13 6 39 24 20 4 48 47 7 48 41 36 36 18 47 20 21 29 48 40 37 35 1 38 29 22 23 10 13 47 16 44 35 26 42 49 31 40 22 18 31 46 13 50 12 36 7 3 35 50 [出力例] 28 [入力例] 300 48 150 23 127 62 109 18 58 128 145 116 114 135 10 124 132 140 66 86 61 7 84 129 114 55 136 113 131 36 143 121 15 52 92 141 24 10 27 121 144 49 75 130 68 71 92 134 41 28 39 149 30 1 1 69 93 71 40 50 42 110 68 55 27 41 79 94 39 23 57 38 21 83 111 38 58 102 34 140 132 102 143 54 76 108 57 46 23 139 28 130 1 114 40 67 80 29 27 105 34 16 8 115 77 28 85 105 133 32 70 127 64 58 45 79 89 13 74 5 27 53 101 44 46 59 92 143 64 21 102 49 93 140 114 61 87 98 80 25 118 117 102 79 46 135 73 47 31 92 118 145 15 56 85 45 36 83 123 140 33 95 98 96 139 127 111 144 127 48 54 69 35 113 39 81 12 132 27 47 104 110 97 99 1 118 9 86 14 96 51 67 59 18 108 130 97 12 17 32 27 70 13 63 60 29 63 58 128 10 50 123 90 120 13 77 7 130 34 122 76 104 31 80 79 122 29 2 28 106 143 116 112 1 6 82 2 7 147 84 131 145 141 50 32 42 143 73 83 112 73 22 32 60 47 94 144 121 34 83 110 9 41 98 48 137 59 63 32 125 109 46 71 120 116 58 5 80 129 34 6 116 101 128 56 28 8 71 149 103 70 90 65 136 118 48 73 17 144 6 81 [出力例] 41 |
■参照サイト
060 – Chimera
AtCoder Beginner Contest 134(E – Sequence Decomposing)