ABC143
所要時間
- 30分4問完答
- 通常のABCと比べると異常なほど簡単だった
解答メモ
A - Curtain
問題文通りに実装すればよし.
#include <bits/stdc++.h> #define REP(i, x) for (int i = 0; i < (int)(x); i++) #define ALL(x) (x).begin(), (x).end() typedef long long ll; using namespace std; int main() { cin.tie(0); ios::sync_with_stdio(false); int A, B; cin >> A >> B; cout << max(A - 2 * B, 0) << endl; return 0; }
B - TAKOYAKI FESTIVAL 2019
ワークロードが小さいので何も考えずに時間計算量O(N^2)
のbrute forceで解を求めれば良い.
#include <bits/stdc++.h> #define REP(i, x) for (int i = 0; i < (int)(x); i++) #define ALL(x) (x).begin(), (x).end() typedef long long ll; using namespace std; int main() { cin.tie(0); ios::sync_with_stdio(false); int N; int d[100]; cin >> N; REP(i, N) { cin >> d[i]; } int result = 0; for (int i = 0; i < N; ++i) { for (int j = i + 1; j < N; ++j) { result += (d[i] * d[j]); } } cout << result << endl; return 0; }
C - Slimes
S[i] ≠ S[i+1]
となる箇所のカウント+1が解答.
#include <bits/stdc++.h> #define REP(i, x) for (int i = 0; i < (int)(x); i++) #define ALL(x) (x).begin(), (x).end() typedef long long ll; using namespace std; int main() { cin.tie(0); ios::sync_with_stdio(false); int N; string S; cin >> N >> S; if (N == 1) { cout << 1 << endl; return 0; } int result = 1; char prev = '\0'; REP(i, N) { if (prev == '\0') { prev = S[i]; } if (S[i] != prev) { ++result; prev = S[i]; } } cout << result << endl; return 0; }
D - Triangles
brute forceで解くと時間計算量がO(N^3)
のためTLEする(実際にやってみたらした).
しかし,O(N^3)
の実装で解いても最初に昇順ソートしてから枝刈りを入れるとACした(1744 ms).
多分これは嘘解答レベルの悪い解答.
#include <bits/stdc++.h> #define REP(i, x) for (int i = 0; i < (int)(x); i++) #define ALL(x) (x).begin(), (x).end() typedef long long ll; using namespace std; int main() { cin.tie(0); ios::sync_with_stdio(false); int N; int L[2000]; cin >> N; REP(i, N) { cin >> L[i]; } ll result = 0; sort(L, L + N); for (int i = 0; i < N - 2; ++i) { for (int j = i + 1; j < N - 1; ++j) { for (int k = j + 1; k < N; ++k) { if ((L[i] < L[j] + L[k]) && (L[j] < L[k] + L[i])) { if (L[k] < L[i] + L[j]) { ++result; } else { break; } } } } } cout << result; return 0; }
解説を読んで二分探索で条件を満たす3個目の辺のindexを探す方法を実装(54 ms).
Lを昇順ソートしてa<b<c
が保証されている時,aとbが決まるとa<b
が常に成り立つため最後の条件はc < a+b
なので,最後のcとなり得る要素の数の総和が解となる.
cとなり得る要素の個数は,a+b以上の要素を境界として, 境界のindex+1(lower_bound - Lすると境界のindex+1の値になる)- bのindex+1
で求められる.
#include <bits/stdc++.h> #define REP(i, x) for (int i = 0; i < (int)(x); i++) #define ALL(x) (x).begin(), (x).end() typedef long long ll; using namespace std; int main() { cin.tie(0); ios::sync_with_stdio(false); int N; int L[2000]; cin >> N; REP(i, N) { cin >> L[i]; } sort(L, L + N); int result = 0; int boundary; for (int i = 0; i < N; ++i) { for (int j = i + 1; j < N; ++j) { boundary = lower_bound(L, L + N, L[i] + L[j]) - L; result += max(boundary - (j + 1), 0); } } cout << result << endl; return 0; }