本番ではA~CまでACでした。D問題についてはアルゴリズムは思いつきましたが、イテレータの扱い方を知らなくて撃沈。いと悔し
ということで、C++でさっそく解説します。
A – Lexicographic Order
問題概要
問題文
相違なる二つの文字列\(S,T\)について\(S\)が\(T\)より辞書順で小さい場合はYes、大きい場合はNoを出力してください。
解説
std::stringに辞書順比較が実装されているのでそれを利用して、問題文の通りに実装します。
#include <bits/stdc++.h>
int main() {
std::string s, t; std::cin >> s >> t;
if (s < t) std::cout << "Yes" << std::endl;
else std::cout << "No" << std::endl;
return 0;
}B – AtCoder Quiz
問題概要
問題文
AtCoderではABC、ARC、AGC、AHCの4つのコンテストがある。\(S_1,S_2,S_3\)の内あと一つは何ですか？
制約
- \(S_1,S_2,S_3\)はそれぞれ、ABC,ARC,AGC,AHCのいずれかである。
- \(S_1,S_2,S_3\)は相異なる。
解説
予め4つのコンテストの文字列を配列でもっておき、入力されたすべてのコンテストを配列の要素と比較することで、入力されていないコンテストを判定します。
#include <bits/stdc++.h>
int main() {
std::vector<std::string> s(3);
for (int i = 0; i < 3; ++i) std::cin >> s[i];
std::vector<std::string> contests{"ABC", "ARC", "AGC", "AHC"};
for (int i = 0; i < 4; ++i) {
bool exists = false;
for (int j = 0; j < 3; ++j)
if (contests[i] == s[j])
exists = true;
if (!exists) {
std::cout << contests[i] << std::endl;
return 0;
}
}
}C – Inverse of Permutation
問題概要
問題文
長さ\(N\)の順列\(P=(p_1,,p_2, \ldots, p_N)\)が与えらるので、すべての\(i(1 \le i \le N)\)に対して\(p_i\)番目の要素が\(i\)である順列\(Q\)を出力してください。
制約
- \(1 \le N \le 2 \times 10^5\)
- \((p_1, p_2, \ldots, p_N)\)は長さ\(N\)の順列である。
- 入力はすべて整数である。
解説
\(p_i\)と\(i\)のpairを要素とする配列を用意して、\(p_i\)について昇順に並び替えることで答えを得られます。
この方法でもACだったのですが、公式の回答に載っている方法の方が計算量が少ないので、そちらの方が良い解答の気がします。
#include <bits/stdc++.h>
int main() {
int n; std::cin >> n;
std::vector<std::pair<int, int>> arr;
for (int i = 0; i < n; ++i) {
int p; std::cin >> p;
arr.push_back({p, i+1});
}
std::sort(arr.begin(), arr.end());
for (int i = 0; i < n; ++i)
std::cout << arr[i].second << " ";
return 0;
}D – Cutting Woods
問題概要
長さ\(L\)の棒がある。以下の\(Q\)個のクエリを処理せよ。\(i\)番目は\((c_i,x_i)\)によって表される。
- \(c_i=1\)のとき : 線\(x_i\)がある地点で木材を\(2\)つに切る。
- \(c_i=2\)のとき : 線\(x_i\)を含む木材を選び、その長さを出力する。
制約
- \(1 \le L \le 10^9\)
- \( 1 \le Q \le 2 \times 10^5\)
- \( c_i=1,2 ~ (1 \le i \le Q)\)
- \( 1 \le x_i \le L ~ – 1 ~ (1 \le i \le Q)\)
解説
カットされた木材の右端の位置をstd::setで管理します。std::setは順序付き集合と呼ばれるもので(コンテスト中に調べた)要素を自動的にソートして内部に格納してくれます。自動的にソートしてくれているので二分探索が使えて次のようにしてクエリに答えていきます。いずれのクエリも計算量は\(O(logN)\)で間に合います。
・\(c_i=1\)(木材カット)
setに\(x_i\)を挿入。
・\(c_i=2\)(長さ出力)
lower_boundで\(x_i\)以上になる最小のitr(イテレータ)、言い換えると地点\(x_i\)を含む木材の右端の値が得られます。地点\(x_i\)を含む木材の長さは次のようにして求めます。itrがsetの先頭要素と等しいときは*itr、そうでないときは\(x_i\)が属する木材の右端の値から、一つ前の木材の右端の値を引くことで木材の長さが求められます。二部探索のわかりやすい記事はこちら。
アルゴリズムをコンテストの入力例3を使って図解してみます。
100 10
1 31
2 41
1 59
2 26
1 53
2 58
1 97
2 93
1 23
2 84
#include <bits/stdc++.h>
int main() {
int l, q; std::cin >> l >> q;
std::set<int> woods{l}; // 木材の右端の値を格納
for (int i = 0; i < q; ++i) {
int c, x; std::cin >> c >> x;
if (c == 1) {
woods.insert(x);
}
else {
std::set<int>::iterator itr = woods.lower_bound(x); // x_iの地点がどの木材に属するか
if (itr == woods.begin()) std::cout << *itr << std::endl;
else std::cout << *itr - *(--itr)<< std::endl;
}
}
return 0;
}