「AtCoder Beginner Contest 126」に参加しました

投稿日：2019年5月27日

結果

5完 [A(100), B(200), C(300), D(400), E(500)] 57:43 ペナルティ: 0
・順位: 662位 (Unrated)

各問題の解法

A問題 (100点)

提出詳細
SのK文字目がAだったらa、Bだったらb、Cだったらcにして出力する。
計算量 O(1)

int N, K;
string S;
cin >> N >> K >> S;
K--;
if (S[K] == 'A') S[K] = 'a';
else if (S[K] == 'B') S[K] = 'b';
else S[K] = 'c';
cout << S << endl;

B問題 (200点)

提出詳細
計算量 O(1)
上2桁をA、下2桁をB、isOK(X) = X > 0 && X < 12 とすると、 isOK(A) && isOK(B) : "AMBIGUOUS" isOK(A) && not isOK(B) : "MMYY" not isOK(A) && isOK(B) : "YYMM" not isOK(A) && not isOK(B) : "NA"

int tmp;
cin >> tmp;
int A = tmp / 100;
int B = tmp % 100;
if (A && A <= 12) {
 cout << (B && B <= 12 ? “AMBIGUOUS” : “MMYY”) << endl; 
} else {
  cout << (B && B <= 12 ? “YYMM” : “NA”) << endl;
}

C問題 (300点)

提出詳細
言われたことをそのまま実装するだけ

計算量 O(N log K)

int N, K;
cin >> N >> K;

double ans = 0;

for (int i = 0; i < N; i++) {
  int a = i + 1, cnt;
  for(cnt = 0; a < K; a *= 2, cnt++);
  ans += (1.0 / N) * pow(0.5, cnt);
}

cout << fixed << setprecision(12) << ans << endl;

D問題 (400点)

提出詳細
頂点からの距離が偶数の頂点を0、奇数の頂点を1にすればOK。実装重め？

int N;
cin >> N;
vector<vector<pair<int, bool>>> graph(N, vector<pair<int, bool>>());
for (int i = 0; i < N - 1; i++) {
  int u, v, w;
  cin >> u >> v >> w;
  u--; v--;
  graph[u].emplace_back(v, w & 1);
  graph[v].emplace_back(u, w & 1);
}

vector<int> ans(N, -1);
vector<bool> visited(N);
ans[0] = 0;
visited[0] = true;

queue<pair<int, bool>> que;
que.emplace(0, false);

while(!que.empty()) {
  pair<int, bool> p = que.front();
  que.pop();
  for (auto r : graph[p.first]) {
    if (visited[r.first]) continue;
    visited[r.first] = true;

    ans[r.first] = p.second != r.second;
    que.emplace(r.first, p.second != r.second);
  }
}

for (int i = 0; i < N; i++) cout << ans[i] << endl;

E問題 (500点)

提出詳細
Union-Findで、各X[i]・Y[i]を結合し、残った親ノードの個数が答えとなる。
※Union-FindはC#でしか実装していないため、サンプルコードは省略します。提出詳細をご覧ください。

感想

２週連続Unratedで、+32が失われてしまいました。結果としては500まで解けたので、それなりに順調だと思います。
推定パフォーマンスは1551でした。