ABC352解説(A~C問題)
このコンテストの反省
今回、A・B・C問題は瞬殺、D問題に関して、見通しは立ったものの、実装ができずACならず。A・B・C問題は安定して解けるようになったので、アルゴリズムをもっと習得して、D問題も解けるようになりたい。
A問題解説・解答
↑問題はこちら
解説
これは、うーんX<YかY<Xで場合分けするかな。
あんまりNは関係ないことに注意しよう(え、N使わないじゃん、自分のコード間違ってる?なんてかんじになりそうだし…)。
解答
solve.cpp
#include <bits/stdc++.h>
using namespace std;
int N, X, Y, Z;
int main() {
cin >> N >> X >> Y >> Z;
if (X <= Z && Z <= Y) cout << "Yes" << endl;
else if (Y <= Z && Z <= X) cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}
要するに、ZがX~Yの中にあるか判定すればいいんですね。
B問題解説・解答
↑問題はこちら
解説
まず、打ち込む予定だった文字列SをキューQに入れてみる
そんで、文字列Tを一文字目から見ていって、Qの一番前の文字とその文字列T内の文字が一致したら、その文字のインデックスを答えを格納するvectorに追加して、Qを一回popする。これを最後までで繰り返す。(キューを使ったのは、普通に、S内のどの文字を入力する予定かっていう文字のインデックスを数値で管理するのがめんどくさかったからです)
解答
solve.cpp
#include <bits/stdc++.h>
using namespace std;
string S, T;
queue <int> Q;
vector <int> ans; //答えを格納するvector
int main() {
cin >> S >> T;
for (int i = 0; i < S.size(); i++) Q.push(S[i]); //文字列SをQに格納
//Tを一文字目から調べる
for (int i = 0; i < T.size(); i++) {
if (Q.empty()) break;
char C = Q.front();//Qの一番前の文字を取得
if (C == T.at(i)) {ans.push_back(i + 1); Q.pop();}//一致したらQから一番前の文字列を取り出す
}
for (int i = 0; i < ans.size(); i++) {
cout << ans[i];
if (i == ans.size() - 1) cout << endl;
else cout << " ";
}
return 0;
}
C問題解説・解答
↑問題はこちら
解説
C問題にしては簡単だったかな?
巨人が肩に乗る。一番上に乗る巨人以外の頭の高さは除外されるから、一番上に乗る巨人が一番頭が大きいように巨人を積めばいいね。
まず、全ての巨人の肩までの高さの総和を出して、それに一番大きい頭の高さを足せばいい。
解答
solve.cpp
#include <bits/stdc++.h>
using namespace std;
int N, A[200009], B[200009];
int main() {
//入力
cin >> N;
for (int i = 1; i <= N; i++) cin >> A[i] >> B[i];
//すべての巨人の肩の高さの総和を出す
long long sum = 0;
for (int i = 1; i <= N; i++) sum += A[i];
//一番大きい頭の高さを出す
int M = 0;
for (int i = 1; i <= N; i++) {
int head = B[i] - A[i];
if (M < head) M = head;
}
cout << sum + M << endl;
return 0;
}