結果
5完 [A(100), B(200), C(300), D(400), E(500)] 20:16 ペナルティ: 0
・順位: 84位 (Rated内39位) [ABC最高順位]
・パフォーマンス: 2395 (黄) [パフォーマンス最高値]
・Rating変化: 1291 -> 1463 (+172) [Rating最高値]
お知らせ
しばらく記事の更新をお休みしていましたが，ぼちぼち再開したいと思います。
今回から，main関数だけではなく，cppファイルのすべての内容を書く予定です。(意見があれば教えてください。)
また，各問題の解説等にご意見やご質問等がありましたら，Twitter等に気軽にお問い合わせください。
各問題の解法
A問題 “Red or Not” (100点)
if文などを使用して，問題文の通りの実装をします。
計算量 O(1)
#include <iostream>
using namespace std;
int main() {
int a;
string s;
cin >> a >> s;
cout << (a >= 3200 ? s : "red");
return 0;
}
B問題 “Resistors in Parallel” (200点)
問題文通りの実装をします。浮動小数点数を扱う場合は double 型を使います。逆数を求める場合は，1から割ればよいです。
なお，誤差が10^-5まで許容される場合は，出力精度の指定は不要です。
計算量 O(N)
#include <iostream>
using namespace std;
int main() {
int N; cin >> N;
double sum = 0;
for (int i = 0; i < N; ++i) {
int a; cin >> a;
sum += 1.0 / a;
}
cout << 1.0 / sum << endl;
return 0;
}
C問題 “Alchemist” (300点)
価値が小さい順に鍋に入れていけばよいです。小さい順か大きい順かはサンプル2からエスパーしましょう。
計算量 O(N log N)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int N; cin >> N;
vector<int> v(N);
for (int i = 0; i < N; ++i) cin >> v[i];
sort(v.begin(), v.end());
double ans = v[0];
for (int i = 1; i < N; ++i) {
ans = (ans + v[i]) / 2;
}
cout << ans << endl;
return 0;
}
D問題 “Ki” (400点)
各操作のxを配列に残しておいて，dfsやbfsによって根から順に探索していくことで答えを求めることができます。
各頂点の値は，親の値 + 配列の自分の頂点の値 となります。
計算量 O(N + Q)
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int main() {
int N, Q;
cin >> N >> Q;
vector<vector<int>> G(N);
for (int i = 0; i < N - 1; ++i) {
int a, b;
cin >> a >> b;
--a;
--b;
G[a].push_back(b);
G[b].push_back(a);
}
vector<int> add(N);
for (int i = 0; i < Q; ++i) {
int p, x;
cin >> p >> x;
add[--p] += x;
}
stack<int> stack;
stack.push(0);
vector<int> ans(N);
vector<bool> vis(N);
while (!stack.empty()) {
int now = stack.top();
vis[now] = true;
stack.pop();
ans[now] += add[now];
for (int next : G[now]) {
if (vis[next]) continue;
ans[next] += ans[now];
stack.push(next);
}
}
for (int i = 0; i < N; ++i) {
cout << ans[i];
cout << (i == N - 1 ? '\n' : ' ');
}
return 0;
}
この問題の解法について
コンテスト中は，a_iがb_iの親である(b_iがa_iの子である)という保証がされているという誤読をしていて，テストケースでもそのようなケースしか存在せず，この解法でもACすることができました。
そのため，コンテスト後に追加された “after_contest” のテストケースは通過せず，WAとなりました。
逆向きの辺を張った上で，無限ループ防止のために訪問済みのフラグをたてることで対策可能で，今回の解説に使用したコードでもその対策を使用しています。
E問題 “Strings of Impurity” (500点)
はじめに，’a’-‘z’の各文字が，sの何文字めに出現するかをメモします。(11-14行目)
tに出現するすべての文字がsにも出現しない場合は，題意を満たせないため -1 を出力して終了します。
まず， p = 0, q = -1 とおきます。
これは，i-1 文字めが，結合した文字列内で，(sの長さを基準に)何周めの何文字めに出現したかの値 (0-indexed) です。
たとえば， s = “abcd” であって，これを結合した文字列内から示すとき， “abcdabcdabcdabcd….” の下線で示した文字の場合は，p = 2, q = 1 となります。
続いて，各 i (0 <= i < |t|) に対して，以下の処理をします。
t[i] = s[j] (q < j < |s|) を満たす j が存在するならば，q を j の最小の値 にする。 (なお，この j は二分探索によって求めることができます。)
そうでないなら，pの値をインクリメントし，q を s[j] (0 <= j < |s|) を満たす j の最小の値にする。
以上の操作をすると，p * |s| + q + 1 が答えとなります。
計算量 O(|s| + |t| log |s|)
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
int main() {
string s, t; cin >> s >> t;
map<char, vector<int>> cnt;
for (int i = 0; i < s.size(); ++i) {
cnt[s[i]].push_back(i);
}
for (char c : t) {
if(cnt[c].empty()) {
cout << -1 << endl;
return 0;
}
}
int p = 0, q = -1;
for (char c : t) {
const auto& v = cnt[c];
int a = upper_bound(v.begin(), v.end(), q) - v.begin();
if (a != v.size()) {
//j = v[a]
q = v[a];
continue;
}
// 条件を満たす j が存在しない場合
p++;
q = v[0];
}
cout << long(p) * s.size() + q + 1 << endl;
return 0;
}
全体の感想
約20分で5完し，初めて黄色パフォを取ることができて，レートも爆上がりでした。(なお，順位があと1つ上であれば2400だったようです。ちょっと悔しい。)
新ABCに吸われたレートを取り戻すどころか，Highest を3か月以上ぶりに，109も更新することができました!
この調子で，次回の企業コンでもレートを上げたいなと思います。
