ここ最近はプライベートでバタバタして忙しく、あまり競プロの練習ができていなかったこともあり成績は2完と振るいませんでした。
今回はABC問題までは難しくなかったはずなのに、頭固すぎてC問題すら解けず。
D問題はスルー。
E問題に手を出したがTLEで結局正解できず。
終了10秒後にC問題がACしたの悔しすぎる。
もともと高くないレートが少し溶けました。。
A問題
//#include<bits/stdc++.h>
//using namespace std;
#include <iostream>
#include <vector>
#include <atcoder/segtree>
template<class T> inline bool chmin(T& a, T b) {
if (a > b) { a = b; return true; }
else return false;
}
template<class T> inline bool chmax(T& a, T b) {
if (a < b) { a = b; return true; }
return false;
}
int main() {
std::string S, Ans;
std::cin >> S;
bool is_add = true;
for (int i = 0; i < S.size(); i++) {
if (S[i] == '|') {
is_add = !is_add;
continue;
}
if (is_add == true) Ans += S[i];
}
std::cout << Ans << std::endl;
}
B問題
//#include<bits/stdc++.h>
//using namespace std;
#include <iostream>
#include <vector>
#include <atcoder/segtree>
#include <stack>
template<class T> inline bool chmin(T& a, T b) {
if (a > b) { a = b; return true; }
else return false;
}
template<class T> inline bool chmax(T& a, T b) {
if (a < b) { a = b; return true; }
return false;
}
int main() {
std::stack<long long> s;
while (true) {
long long a;
std::cin >> a;
s.push(a);
if (a == 0) break;
}
while (0 < s.size()) {
std::cout << s.top() << std::endl;
s.pop();
}
}C問題
//#include<bits/stdc++.h>
//using namespace std;
#include <iostream>
#include <vector>
#include <atcoder/segtree>
#include <algorithm>
#include <set>
template<class T> inline bool chmin(T& a, T b) {
if (a > b) { a = b; return true; }
else return false;
}
template<class T> inline bool chmax(T& a, T b) {
if (a < b) { a = b; return true; }
return false;
}
int main() {
long long N, M, L, Q;
std::cin >> N;
std::vector<long long> A(N);
for (long long n = 0; n < N; n++) std::cin >> A[n];
std::cin >> M;
std::vector<long long> B(M);
for (long long m = 0; m < M; m++) std::cin >> B[m];
std::cin >> L;
std::vector<long long> C(L);
for (long long l = 0; l < L; l++) std::cin >> C[l];
std::cin >> Q;
std::vector<long long> X(Q);
for (long long q = 0; q < Q; q++) std::cin >> X[q];
std::sort(begin(A), end(A));
std::sort(begin(B), end(B));
std::sort(begin(C), end(C));
std::vector<long long> ABC;
//std::set<long long> ABC;
for (long long n = 0; n < N; n++) {
for (long long m = 0; m < M; m++) {
for (long long l = 0; l < L; l++) {
ABC.push_back(A[n] + B[m] + C[l]);
//ABC.insert(A[n] + B[m] + C[l]);
}
}
}
std::sort(begin(ABC), end(ABC));
for (long long q = 0; q < Q; q++) {
/*auto itr = ABC.find(X[q]);
std::cout << ((itr != ABC.end()) ? "Yes" : "No") << std::endl;*/
bool is_ok = std::binary_search(begin(ABC), end(ABC), X[q]);
std::cout << (is_ok == true ? "Yes" : "No") << std::endl;
}
//for (long long q = 0; q < Q; q++) {
// bool is_ok = false;
// auto itr_n = std::upper_bound(begin(A), end(A), X[q]);
// long long n_max = (itr_n - begin(A));
// for (long long n = 0; n < n_max; n++) {
// auto itr = std::upper_bound(begin(B), end(B), (X[q] - A[n]));
// //if (itr == end(B)) continue;
// long long m_max = (itr - begin(B));
// for (long long m = 0; m < m_max; m++) {
// long long tmp_target = (X[q] - A[n] - B[m]);
// if (tmp_target < 0) continue;
// is_ok = std::binary_search(begin(C), end(C), tmp_target);
// if (is_ok == true) break;
// }
// if (is_ok == true) break;
// }
// std::cout << (is_ok == true ? "Yes" : "No") << std::endl;
//}
}「最初にABCの合計値を全パターン計算しておいて、Xの値を2分探索する」なんともない問題。
計算量の見積もりをする力をきちんと身に着けていれば解法にはたどり着けたはず。本当に悔しいし情けないです、、
D問題
E問題
//#include<bits/stdc++.h>
//using namespace std;
#include <iostream>
#include <vector>
#include <atcoder/segtree>
#include <map>
template<class T> inline bool chmin(T& a, T b) {
if (a > b) { a = b; return true; }
else return false;
}
template<class T> inline bool chmax(T& a, T b) {
if (a < b) { a = b; return true; }
return false;
}
struct Node {
long long before;
long long after;
};
int main() {
int N, Q;
std::cin >> N;
std::vector<long long> A(N);
for (int n = 0; n < N; n++) std::cin >> A[n];
std::map<long long, Node> mp;
mp[0].before = -1;
mp[0].after = A[0];
for (int n = 0; n < N; n++) {
if (0 < n) mp[A[n]].before = A[n - 1];
else mp[A[n]].before = 0;
if ((n + 1) < N) mp[A[n]].after = A[n + 1];
else mp[A[n]].after = -1;
}
std::cin >> Q;
for (int q = 0; q < Q; q++) {
long long t, x, y;
std::cin >> t;
switch (t) {
case 1:
std::cin >> x >> y;
mp[y].before = x;
mp[mp[y].after].before = y;
mp[y].after = mp[x].after;
mp[x].after = y;
break;
case 2:
std::cin >> x;
mp[mp[x].after].before = mp[x].before;
mp[mp[x].before].after = mp[x].after;
mp.erase(x);
break;
}
}
long long now = 0;
while (0 < mp.size()) {
long long tmp_val = mp[now].after;
if (0 <= tmp_val) std::cout << tmp_val << " ";
mp.erase(now);
now = tmp_val;
}
std::cout << std::endl;
}
コメント