C++の練習を兼ねて, AtCoder Beginner Contest 134 の 問題E (E – Sequence Decomposing) を解いてみた.
■感想.
1. 問題E は, 解答方針が見えなかったので, 解説を参照して確認した.
2. LIS(Longest increase subsequence) の アルゴリズム を 使う必要があるとの指摘があったが, “広義”単調減少 と記載されていたので, プログラム上, 部分的に修正した.
本家のサイトABC 134解説をご覧下さい.
■C++版プログラム(問題E／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 |
// 解き直し. // ABC 134解説. // https://img.atcoder.jp/abc134/editorial.pdf #include <bits/stdc++.h> using namespace std; using LL = long long; int main() { // 1. 入力情報取得. int N; scanf("%d", &N); vector<LL> A(N); vector<LL> dp; // 解説通りだが, LIS使う必要があるため, 後ろ側から値を保存. for(int i = 0; i < N; i++) scanf("%lld", &A[N - i - 1]); // for(int i = 0; i < N; i++) printf("%lld ", A[i]); // 2. 解説通り. // -> LIS で 解く必要があるとのこと. // -> "広義"単調減少列 との 記載から, lower_bound を upper_bound に 変更. dp.push_back(A[0]); for(int i = 1; i < N; i++){ // 2-1. dpテーブル末尾 の 要素(last)以上 の 値(A[i])であれば, dpテーブル に 追加. int last = dp.back(); // if(last < A[i]) dp.push_back(A[i]); if(last <= A[i]) dp.push_back(A[i]); // "広義"用. // 2-2. dpテーブル末尾 の 要素(last) より小さな値(A[i])であれば, // dpテーブル上 の 更新場所 を 探索後, dpテーブル を 更新. if(last > A[i]){ // auto it = lower_bound(dp.begin(), dp.end(), A[i]); auto it = upper_bound(dp.begin(), dp.end(), A[i]); // "広義"用. int dist = it - dp.begin(); dp[dist] = A[i]; // for(int i = 0; i < dp.size(); i++) cout << dp[i] << " "; // cout << endl; } } // for(int i = 0; i < dp.size(); i++) cout << dp[i] << " "; // cout << endl; // 3. 出力 ～ 後処理. printf("%d\n", dp.size()); 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 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 |
[入力例] 5 2 1 4 5 3 [出力例] 2 ※AtCoderテストケースより [入力例] 4 0 0 0 0 [出力例] 4 ※AtCoderテストケースより [入力例] 8 1 2 5 4 3 7 3 2 [出力例] 5 [入力例] 100 14 13 66 96 30 78 79 29 84 22 91 29 12 77 78 59 97 17 91 57 78 59 61 78 0 93 8 60 28 12 37 12 80 34 5 63 3 14 22 92 6 19 60 58 18 37 95 2 41 49 14 62 20 75 56 78 13 47 69 66 77 71 33 67 13 1 83 31 47 85 51 78 32 42 17 48 35 26 77 80 44 46 30 58 85 4 40 15 78 79 10 0 95 6 63 87 63 1 54 54 [出力例] 18 |
■参照サイト
AtCoder Beginner Contest 134