AtCoder Beginner Contest 138 に参加した。今回は ABCD 4 完答 の 1978 位でパフォーマンスは 958 だった。
以下のコードは PyPy3 (2.4.0) と C++14 (GCC 5.4.1) で AC を確認している。
※ (2019/08/23) 問題 D の回答は正しくなかったので修正した。
問題 A
入力の \(a\) が \(3200\) 以上かどうかで出力を変える問題なので、そのまま実装した。
a = int(input())
s = input()
print(s) if a >= 3200 else print('red')
問題 B
計算式どおりに計算した。
N = int(input())
A = list(map(int, input().split()))
ans = 0
for a in A:
ans += 1/a
print(1/ans)
問題 C
計算の順番によって値にどのような影響が出るかを考えた。要素が 3 つの場合を考えればそれ以上にも適用できる。
とおき、両辺に 4 を掛けて展開すると
となり \(s\) への寄与率が最も高いのは \(v_k\) とわかる。従って \(v_1, v_2, \ldots, v_N\) を昇順に並び替えて、前から各具材を鍋に入れていけば良い。
N = int(input())
V = list(map(int, input().split()))
V.sort()
ans = V[0]
for i in range(1, N):
ans = (ans + V[i])/2
print(ans)
問題 D
\(p_i, x_i\) をその都度、カウンターに加算していくと、最大で \(NQ\) 回の処理が必要になり、間に合わないだろうと考えた。そのため
- 各 \(p_i\) の頂点のカウンタに \(x_i\) の値を加える
- \(1, 2, \ldots, N\) の頂点を渡り、自分の直属の子に自分のカウンタを足す
とすることで処理回数を \(N + Q\) 程度に抑えられるだろうと考えた。しかし PyPy3 (2.4.0) で実装したものの TLE を食らったので C++14 (GCC 5.4.1) に切り替えた。
※ (2019/08/23) 最初の記事では、根付き木をよく理解しておらず index に暗黙の仮定 (根本ほど index が小さい) をおいていたため、コンテスト後に追加されたテスト (after_contest_15, after_contest_16, after_contest_17) で WA していた。この問題の具体例については AtCoder Beginner Contest 138 D - Ki のテストケースがコンテスト後に増えている件について (修正版) が詳しい。
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
void AddScore(map<long long, vector<long long>>& C, long long* S, long long i, int* visited)
{
const auto r = C[i];
const auto s = S[i - 1];
visited[i - 1] = 1;
for (auto j : r) {
if (visited[j - 1] != 0) {
continue;
}
S[j - 1] += s;
AddScore(C, S, j, visited);
}
}
int main()
{
long long N, Q;
cin >> N >> Q;
map<long long, vector<long long>> C;
for (long long i = 0; i < N - 1; ++i) {
long long a, b;
cin >> a >> b;
C[a].push_back(b);
C[b].push_back(a);
}
vector<long long> S;
S.resize(N);
fill(S.begin(), S.end(), 0);
for (long long i = 0; i < Q; ++i) {
long long p, x;
cin >> p >> x;
S[p - 1] += x;
}
vector<int> visited;
visited.resize(N);
fill(visited.begin(), visited.end(), 0);
AddScore(C, S.data(), 1, visited.data());
for (long long i = 0; i < N; ++i) {
cout << S[i] << " ";
}
cout << endl;
return 0;
}
問題 E
問題 D の C++ への書き直しに手間取って 20 分くらいしか残っていなかったので十分に考察できず。