C++の練習を兼ねて, AtCoder Regular Contest 126 の 問題A (Make 10) ~ 問題B (Cross-free Matching) を解いてみた.
■感想.
1. 問題B は, 方針が見えなかったので, 解説を参考に実装したところ AC版に到達できた.
2. 問題B で, LIS(Longest increase subsequence) の 復習ができたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 126 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題A/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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; #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--) int main(){ // 1. 入力情報. int T; scanf("%d", &T); // 2. クエリ回答. rep(i, T){ LL N2, N3, N4; scanf("%lld %lld %lld", &N2, &N3, &N4); // 長さ 10 の 棒 を 作成. // 長さ 3 の 棒が, 1本余る可能性あるが, 無視. LL ans= 0; LL n3 = N3 / 2; if(n3 <= N4){ // (3, 3, 4) ans += n3; N4 -= n3; // (2, 4, 4) LL n4 = N4 / 2; LL n24 = min(N2, n4); ans += n24; N2 -= n24; // (2, 2, 2, 4) if(N4 != n4 * 2){ if(N2 >= 3){ ans++; N2 -= 3; } } // (2, 2, 2, 2, 2) LL n2 = N2 / 5; ans += n2; }else{ // (3, 3, 4) ans += N4; N3 -= N4 * 2; // (3, 3, 2, 2) LL n23 = min(N2, N3) / 2; ans += n23; N2 -= n23 * 2; N3 -= n23 * 2; // (2, 2, 2, 2, 2) LL n2 = N2 / 5; ans += n2; } // 出力. printf("%lld\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 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 |
[入力例] 5 3 4 1 7 0 0 0 0 7 0 0 0 1000000000000000 1000000000000000 1000000000000000 [出力例] 2 1 0 0 900000000000000 ※AtCoderのテストケースより [入力例] 20 36 112 72 92 61 67 59 59 72 63 4 103 103 63 4 119 96 74 30 112 96 98 61 1 33 3 82 34 77 20 71 109 14 40 52 15 89 0 15 3 84 98 95 41 6 3 24 4 62 113 3 117 23 62 67 27 97 23 102 113 [出力例] 69 63 58 55 40 82 78 38 34 37 49 29 23 45 33 5 34 54 60 74 [入力例] 30 5321 7661 6793 4132 7399 8201 6164 11064 2291 11945 7434 3588 11106 797 12089 1298 7596 9460 11423 11121 4504 8614 7146 11395 6482 7458 7156 5325 5719 285 9070 2202 8960 12194 3869 8798 4770 8479 7498 12099 2499 8485 2690 10112 9743 2595 11087 1936 599 3992 1408 3370 6874 5128 10216 11395 1709 8586 7213 11453 3617 1863 11294 9373 6187 6843 2626 11253 9954 6650 1357 10072 7673 9727 3941 3705 1164 194 70 5032 4508 8848 6466 2153 4381 4286 4640 3875 3967 6781 [出力例] 6079 6326 5373 6054 7295 5096 7422 8424 6396 2894 6058 7118 6496 6563 7468 3233 1707 4787 6145 8462 4548 6467 7882 5765 6028 1167 2586 4570 4018 4677 |
■C++版プログラム(問題B/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 |
// 解き直し. // https://atcoder.jp/contests/arc126/editorial/2626 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vi = vector<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 all(x) x.begin(), x.end() struct line{ int a, b; // 座標 a, b. bool operator < (const line& rhs) const{ return (a == rhs.a) ? (b > rhs.b) : (a < rhs.a); } }; int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); vector<line> v; rep(i, M){ int a, b; scanf("%d %d", &a, &b); line l; l.a = a; l.b = b; v.pb(l); } // 2. sort. sort(all(v)); // 3. 狭義単調増加な数列の長さの最大値は? // 以下の問題を参照. // https://atcoder.jp/contests/typical90/tasks/typical90_bh // -> LIS(Longest increase subsequence) を 利用. vi dp; rep(i, M){ // 数列を保存. line l = v[i]; if(dp.size() == 0 || dp.back() < l.b){ dp.pb(l.b); }else{ int at = lower_bound(all(dp), l.b) - dp.begin(); dp[at] = l.b; } } // rep(i, dp.size()) printf("%d\n", dp[i]); // 4. 出力. 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 143 144 145 146 147 148 149 150 151 152 153 154 155 |
[入力例] 3 3 1 2 2 3 3 1 [出力例] 2 ※AtCoderのテストケースより [入力例] 3 5 1 1 2 1 2 2 3 2 3 3 [出力例] 3 ※AtCoderのテストケースより [入力例] 7 5 1 7 7 1 3 4 2 6 5 2 [出力例] 1 ※AtCoderのテストケースより [入力例] 1 1 1 1 [出力例] 1 [入力例] 5 6 1 3 4 1 4 5 5 3 3 2 3 4 [出力例] 3 [入力例] 8 15 2 1 2 3 3 4 3 2 1 1 4 4 4 5 5 7 5 4 5 8 6 5 6 6 7 6 7 8 8 8 [出力例] 6 [入力例] 15 20 9 8 1 3 5 4 10 1 10 11 7 7 9 7 4 2 8 14 7 14 5 12 8 11 10 13 15 14 2 10 13 8 4 11 12 4 2 12 5 3 [出力例] 6 [入力例] 25 50 25 16 6 19 22 14 10 21 6 20 7 20 12 3 8 13 19 23 13 21 8 16 1 22 4 1 14 18 11 9 23 2 13 19 4 10 5 7 1 15 24 1 5 11 3 10 5 4 15 20 17 22 24 16 25 11 10 15 7 6 14 16 8 11 11 13 6 7 15 8 6 9 6 18 8 25 15 12 14 7 16 2 22 6 3 13 10 10 20 4 16 23 9 10 16 20 5 12 12 14 [出力例] 10 |