今回、C問題から取り掛かったがめちゃめちゃ時間を消費して、あきらめて2，3分でA問題とB問題を解いた。
⇒
採点システム君「こいつは、A問題を解くまでに1時間以上かかるヤツか。低パフォ判定しとこ。」
私「え、なんでこんなにパフォ低いの、、、」
自分がAtCoderの採点方式を理解できていないこともあってレートが爆下がりした。
今度からはまっとうにA問題から解こう。（A、Bは絶対初めに解くとして、残りの問題はないよう見ながら臨機応変に）
A問題 Divisible
#include <iostream>
#include <vector>
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() {
int N, K;
std::cin >> N >> K;
//std::vector<int> A(N);
for (int n = 0; n < N; n++) {
int a;
std::cin >> a;
if ((a % K) == 0) std::cout << (a / K) << " ";
}
std::cout << std::endl;
}B問題 Substring
#include <iostream>
#include <vector>
#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;
}
int main() {
std::string S;
std::cin >> S;
std::map<std::string, int> mp;
for (int i = 0; i < (S.size()); i++) {
for (int e = 1; (i + e) <= S.size(); e++) {
mp[S.substr(i, e)] = 1;
}
}
std::cout << mp.size() << std::endl;
}C問題
「予定が全部A日以内に入るか」→「予定がない日が連続B日以上とれるか」に発想を転換したうえで、週をまたぐケースを考えて2週分探索することがPOINT！
#include <iostream>
#include <vector>
#include <algorithm>
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, A, B;
std::cin >> N >> A >> B;
std::vector<long long> D(N);
for (long long n = 0; n < N; n++) std::cin >> D[n];
long long cnt_week_days = (A + B);
std::vector<long long> DD(N);
for (long long n = 0; n < N; n++) DD[n] = (D[n] % cnt_week_days);
for (long long n = 0; n < N; n++) DD.push_back(DD[n] + cnt_week_days);
DD.erase(unique(begin(DD), end(DD)), end(DD));
std::sort(begin(DD), end(DD));
bool ans = false;
for (long long d = 1; d < DD.size(); d++) {
if ((DD[d] - DD[d - 1]) > B) {
ans = true;
break;
}
}
std::cout << (ans == true ? "Yes" : "No") << std::endl;
}
コメント